FastPrepMinimum Increments for Stepwise Towers

Minimum Increments for Stepwise Towers

ZipRecruiter logoZipRecruiter● MediumNEW GRADFULLTIMEOA
Learn

Problem statement

You are given an integer array towers, where towers[i] is the height of the ith tower.

In one move, add exactly one block to any tower. Blocks cannot be removed.

Make the entire sequence stepwise in either direction:

  • increasing: every height is exactly one greater than the previous height; or
  • decreasing: every height is exactly one less than the previous height.

Return the minimum number of moves required.

Function

minimumStepwiseIncrements(towers: int[]) → long

Examples

Example 1

towers = [1,4,3,2]return = 4

Raise the first tower from 1 to 5. The result [5,4,3,2] is stepwise decreasing and costs four moves.

Example 2

towers = [5,7,9,4,11]return = 9

The cheapest target is [7,8,9,10,11], requiring 2 + 1 + 0 + 6 + 0 = 9 added blocks.

Constraints

  • 1 <= towers.length <= 100000
  • 0 <= towers[i] <= 1000000000
  • The answer fits in a signed 64-bit integer.

More ZipRecruiter problems

See ZipRecruiter hiring insights
public long minimumStepwiseIncrements(int[] towers) {
    // Write your code here.
}
towers[1,4,3,2]
expected4
Checking account…