Watch 10 video solutions for Maximum Subarray Sum With Length Divisible by K, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by codestorywithMIK has 10,674 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |