You are given a 0-indexed integer array arr and an integer k. The array arr is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element.
You can do the following operation any number of times:
arr and increase or decrease it by 1.Return the minimum number of operations such that the sum of each subarray of length k is equal.
A subarray is a contiguous part of the array.
Example 1:
Input: arr = [1,4,1,3], k = 2 Output: 1 Explanation: we can do one operation on index 1 to make its value equal to 3. The array after the operation is [1,3,1,3] - Subarray starts at index 0 is [1, 3], and its sum is 4 - Subarray starts at index 1 is [3, 1], and its sum is 4 - Subarray starts at index 2 is [1, 3], and its sum is 4 - Subarray starts at index 3 is [3, 1], and its sum is 4
Example 2:
Input: arr = [2,5,5,7], k = 3 Output: 5 Explanation: we can do three operations on index 0 to make its value equal to 5 and two operations on index 3 to make its value equal to 5. The array after the operations is [5,5,5,5] - Subarray starts at index 0 is [5, 5, 5], and its sum is 15 - Subarray starts at index 1 is [5, 5, 5], and its sum is 15 - Subarray starts at index 2 is [5, 5, 5], and its sum is 15 - Subarray starts at index 3 is [5, 5, 5], and its sum is 15
Constraints:
1 <= k <= arr.length <= 1051 <= arr[i] <= 109Problem 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.
Group elements by their indices modulo k to form independent equivalence classes. To equalize each group, transform them to their median value to minimize the number of operations needed.
The idea behind using median is that it minimizes the sum of absolute deviations from a central point.
In this solution, we group the elements by their indices modulo k. For each group, we calculate the median and convert all elements in that group to the median, summing the operations.
Time Complexity: O(n log n) due to sorting when computing the median for each group.
Space Complexity: O(n) to store the intermediate groups.
This approach uses dynamic programming to maintain a cost structure as we equalize values effectively. By tracking the cost of bringing elements closer together, we manage the transitions efficiently while minimizing operations across different subarrays.
This solution uses dynamic programming to implicitly keep track of the costs as we compute the optimal transformation by groups using sorting.
C++
Time Complexity: O(n log n) for sorting during value group calculation.
Space Complexity: O(n) for auxiliary storage of elements per group.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Median Based Optimization | Time Complexity: O(n log n) due to sorting when computing the median for each group. |
| Dynamic Programming Strategy | Time Complexity: O(n log n) for sorting during value group calculation. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Median Based Optimization | O(n log n) | O(n) | General optimal solution using cycle grouping and median minimization |
| Dynamic Programming Strategy | O(n log n) | O(n) | Useful when explicitly modeling cost transitions with prefix sums |
Leetcode Biweekly 101 Make K-subarray sums equal solution | Hindi explanation • Pawan Kumar Giri • 2,594 views views
Watch 9 more video solutions →Practice Make K-Subarray Sums Equal with our built-in code editor and test cases.
Practice on FleetCode