Make K-Subarray Sums Equal - Video Solutions

Problem Overview: You are given a circular array nums and an integer k. You may increment or decrement any element by 1 per operation. The goal is to make the sum of every length-k subarray equal while minimizing the total number of operations.

Key Insight

If two consecutive k-length subarrays have equal sums, the difference between them must be zero. That difference equals nums[i+k] - nums[i], which forces nums[i] = nums[i+k]. Because the array is circular, repeatedly jumping by k forms cycles. All elements in the same cycle must become equal. The number of independent cycles is determined by gcd(n, k), a classic observation from number theory.

Approach 1: Median Based Optimization (O(n log n) time, O(n) space)

Group indices that belong to the same cycle formed by repeatedly adding k modulo n. For each cycle, collect the corresponding values from the array. All numbers in that group must become the same value. The cost to convert a set of numbers into a single value is minimized when you choose the median. Sort the group using a sorting step, pick the median, and sum the absolute differences between each element and the median. Repeat for every cycle and accumulate the total cost. This works because the median minimizes the sum of absolute deviations, which directly matches the operation cost.

Approach 2: Dynamic Programming Strategy (O(n log n) time, O(n) space)

Another way to reason about the same cycle structure is to treat each cycle as an optimization problem. After extracting the elements of a cycle, sort them and use dynamic programming to compute the minimal cost of transforming all values to a common target among the sorted candidates. Prefix sums help evaluate cost transitions efficiently: the cost of converting elements on the left and right sides of a candidate target can be computed in constant time. While the DP formulation is more explicit about cost transitions, it ultimately reaches the same optimal target value that the median approach identifies.

Recommended for interviews: The median-based cycle solution is the expected approach. Interviewers want to see the observation that equal k-subarray sums force nums[i] = nums[i+k] and that cycles are defined by gcd(n, k). Once you group elements by cycle, applying the median trick shows strong algorithmic intuition and reduces the problem to a clean O(n log n) solution.