Ctrl K

Raising by Ranges

Hard
A row of len(heights) columns starts at height zero. In one operation you pick any contiguous range of columns and raise each of them by 1. Return the smallest number of operations after which column i has height exactly heights[i] for every i.
Example 1
heights=[2, 4, 1, 3] → 6

Raise all four columns by 1, then columns 0–1 by 1 more, then column 1 twice and column 3 twice: 1 + 1 + 2 + 2 = 6.

Example 2
heights=[5, 5, 5] → 5

Raise the whole row five times.

Constraints
  • 1 ≤ len(heights) ≤ 10⁵
  • 1 ≤ heights[i] ≤ 10⁵
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsEqualizer Sliders to a Preset HardTree of Leaf Products MediumHopping Along the Stones MediumWater Between Walls HardBiggest Solid Panel Block Hard
loading Python…
Input
heights=[2, 4, 1, 3]
Expected
6

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.