You are given an array of integers nums and an integer k.
Return the maximum sum of a subarray of nums, such that the size of the subarray is divisible by k.
Example 1:
Input: nums = [1,2], k = 1
Output: 3
Explanation:
The subarray [1, 2] with sum 3 has length equal to 2 which is divisible by 1.
Example 2:
Input: nums = [-1,-2,-3,-4,-5], k = 4
Output: -10
Explanation:
The maximum sum subarray is [-1, -2, -3, -4] which has length equal to 4 which is divisible by 4.
Example 3:
Input: nums = [-5,1,2,-3,4], k = 2
Output: 4
Explanation:
The maximum sum subarray is [1, 2, -3, 4] which has length equal to 4 which is divisible by 2.
Constraints:
1 <= k <= nums.length <= 2 * 105-109 <= nums[i] <= 109Problem Overview: Given an integer array and an integer k, compute the maximum possible sum of a subarray whose length is divisible by k. The constraint on length means if a subarray starts at index j and ends at i, the condition (i - j) % k == 0 must hold.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Enumerate every possible subarray and compute its sum. While expanding a subarray from index i to j, track the current length. Whenever the length satisfies (j - i + 1) % k == 0, update the maximum sum. Prefix sums can slightly simplify the sum calculation, but the algorithm still checks all O(n²) ranges. This approach demonstrates the core condition on subarray length but becomes too slow when n grows beyond a few thousand.
Approach 2: Prefix Sum + Modulo Enumeration (O(n) time, O(k) space)
The key observation: if a subarray from j to i-1 has length divisible by k, then i % k == j % k. Build a prefix sum array where prefix[i] is the sum of the first i elements. The subarray sum becomes prefix[i] - prefix[j]. For each remainder r = i % k, track the smallest prefix sum previously seen at an index with the same remainder. When you revisit that remainder, compute prefix[i] - minPrefix[r] to get the best subarray ending at i whose length is divisible by k. Update the maximum and refresh the stored minimum prefix if the current one is smaller. This turns the problem into a single pass over the array with constant-time updates.
The data structure holding the minimum prefix per remainder can be a simple array of size k or a hash table. Each iteration performs constant work: compute the new prefix sum, check the remainder group, update the answer, and maintain the minimum prefix value.
This technique relies on the interaction between index arithmetic and cumulative sums. Similar patterns appear in many array problems where constraints apply to subarray length, parity, or divisibility.
Recommended for interviews: Prefix Sum + Modulo Enumeration. Interviewers expect you to move from the quadratic enumeration idea to the prefix-sum observation that indices with the same i % k form valid boundaries. The optimized solution runs in O(n) time and uses only O(k) additional space, showing both algorithmic insight and familiarity with prefix sum patterns.
According to the problem description, for a subarray's length to be divisible by k, it is equivalent to requiring that for subarray nums[i+1 ldots j], we have i bmod k = j bmod k.
We can enumerate the right endpoint j of the subarray and use an array f of length k to record the minimum prefix sum for each modulo k. Initially, f[k-1] = 0, indicating that the prefix sum at index -1 is 0.
Then for the current right endpoint j with prefix sum s, we can calculate the maximum sum of subarrays ending at j with length divisible by k as s - f[j bmod k], and update the answer accordingly. At the same time, we need to update f[j bmod k] to be the minimum of the current prefix sum s and f[j bmod k].
After the enumeration is complete, return the answer.
The time complexity is O(n) and the space complexity is O(k), where n is the length of the array nums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n²) | O(1) | Understanding the problem constraint or when input size is very small |
| Prefix Sum + Modulo Grouping | O(n) | O(k) | Optimal solution for large arrays; standard interview approach |
| Prefix Sum + Hash Map | O(n) | O(k) | Useful when k is large or when implementing remainder tracking dynamically |
Maximum Subarray Sum With Length Divisible by K | Simplified Kadane's Algo | Leetcode 3381 | MIK • codestorywithMIK • 10,674 views views
Watch 9 more video solutions →Practice Maximum Subarray Sum With Length Divisible by K with our built-in code editor and test cases.
Practice on FleetCode