Flat Runs of a Fixed Width

Hard

You are given an integer array values and two integers width and count. In one operation you may increase or decrease any element of the array by 1. The goal is for the array to contain at least count **non-overlapping** segments of exactly width consecutive elements, where all elements inside each segment are equal. Different segments may hold different values. Return the smallest number of operations that achieves this.

Example 1

values=[4, 10, 6, 5, 0, 2, 2, 9], width=2, count=2 → 1

Take [6, 5] at positions 2–3 and turn it into [5, 5] with 1 operation; the piece [2, 2] at positions 5–6 is already flat. 1 in total.

Example 2

values=[1, 7, 3, 3, 8], width=3, count=1 → 4

The best piece is [7, 3, 3]: lower 7 to 3 with 4 operations. The piece [3, 3, 8] would cost 5 and [1, 7, 3] would cost 6.

Example 3

values=[-2, 2, -2, 2], width=2, count=2 → 8

The pieces cannot overlap, so both [-2, 2] pairs must be used; each takes 4 operations to flatten, 8 in total.

Constraints

2 ≤ values.length ≤ 10⁵
-10⁶ ≤ values[i] ≤ 10⁶
2 ≤ width ≤ values.length
1 ≤ count ≤ 15
2 ≤ width · count ≤ values.length

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Input

values=[4, 10, 6, 5, 0, 2, 2, 9], width=2, count=2

Expected

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