Skip to main content
Talentd

Make K-Subarray Sums Equal - Solution & Explanation

MediumArrayMathSortingNumber Theory8 min readAsked at: Morgan Stanley, Observeai
Practice this problem

Problem Statement

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:

  • Pick any element from 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 <= 105
  • 1 <= arr[i] <= 109

Approach Overview

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.

Approach 1: Median Based Optimization

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Strategy

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.

Code

C++

C++

Complexity

Time Complexity: O(n log n) for sorting during value group calculation.
Space Complexity: O(n) for auxiliary storage of elements per group.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Median Based Optimization

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.

Dynamic Programming Strategy

Time Complexity: O(n log n) for sorting during value group calculation.
Space Complexity: O(n) for auxiliary storage of elements per group.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Median Based OptimizationO(n log n)O(n)General optimal solution using cycle grouping and median minimization
Dynamic Programming StrategyO(n log n)O(n)Useful when explicitly modeling cost transitions with prefix sums

Video Solution

Leetcode Biweekly 101 Make K-subarray sums equal solution | Hindi explanation • Pawan Kumar Giri • 2,703 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Make K-Subarray Sums Equal easy or hard?
The problem is rated Medium on LeetCode. The main difficulty is discovering that equal k-subarray sums force equality along index cycles defined by k. Once that observation is made, the remaining step is a standard median-based minimization.
Make K-Subarray Sums Equal Python/Java solution
Python and Java implementations follow the same steps: compute gcd(n, k), iterate through cycles, collect values, sort them, and compute the cost relative to the median. The logic remains identical across languages with O(n log n) complexity.
How to solve Make K-Subarray Sums Equal in O(n log n)?
First compute g = gcd(n, k). For each of the g cycles formed by repeatedly adding k modulo n, gather the elements. Sort each group, choose the median, and sum absolute differences to that median. Adding costs across all cycles yields the minimal number of operations.
What is the best approach for Make K-Subarray Sums Equal?
The optimal approach groups indices into cycles using gcd(n, k). Elements in the same cycle must become equal because equal k-length subarray sums imply nums[i] = nums[i+k]. For each cycle, convert all values to the median to minimize the sum of absolute differences. This produces an O(n log n) time and O(n) space solution.
Is Make K-Subarray Sums Equal asked at Google/Amazon/Meta?
Problems involving cycle grouping, median minimization, and gcd-based partitioning appear frequently in interviews at companies like Google and Amazon. Variants of this problem test array manipulation, mathematical observations, and optimization using medians.
What data structure is used in Make K-Subarray Sums Equal?
The solution mainly uses arrays or lists to collect elements belonging to the same cycle. Sorting those lists is required to compute the median efficiently. The mathematical component relies on computing gcd(n, k).
What is the time complexity of Make K-Subarray Sums Equal?
The optimal solution runs in O(n log n) time. Each cycle of indices is collected and sorted to compute the median, which dominates the runtime. Space complexity is O(n) for storing cycle elements.

Ready to solve this problem?

Practice Make K-Subarray Sums Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rotate Array