A Level Stretch of Fence

Medium

The heights of fence posts are stored in the array heights (they are measured from some reference level and may be negative). In one step you can raise or lower any post by 1. You want some width consecutive posts to end up at the same height. Return the minimum number of steps needed to achieve that.

Example 1

heights=[5, 1, 4, 2, 9], width=3 → 3

Take the window [1, 4, 2] and level it to 2: 1 step for the first column and 2 for the second, 3 in total. Every other window costs more.

Example 2

heights=[-3, 7, 7, 0], width=2 → 0

The two neighbouring 7s are already the same height.

Example 3

heights=[0, 10, -10], width=3 → 20

Constraints

2 ≤ len(heights) ≤ 10⁵
-10⁶ ≤ heights[i] ≤ 10⁶
2 ≤ width ≤ len(heights)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Math Sliding Window Heap (Priority Queue)

Similar problems

Stretches With k Odd Numbers Medium Moving Window Median Hard Narrowest Range Touching Every List Hard Cheapest Cut With Close Starts Hard Top-Frequency Window Sums Easy

Input

heights=[5, 1, 4, 2, 9], width=3

Expected

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