Maximum Subarray Sum With Length Divisible by K solution and explanation
Google
9 more videos on this problem
Maximum Subarray Sum With Length Divisible by K | Simplified Kadane's Algo | Leetcode 3381 | MIKcodestorywithMIK · 31:35 · 12K views
Maximum Subarray Sum With Length Divisible by K - Leetcode 3381 - PythonNeetCodeIO · 21:59 · 10K views
3381. Maximum Subarray Sum With Length Divisible by K | Prefix Sums | Arrays | Handling Mod & LengthAryan Mittal · 19:22 · 5K views
Maximum Subarray Sum With Length Divisible by K | LeetCode 3381 | Interesting ProblemSanyam IIT Guwahati · 19:52 · 2K views
3381. Maximum Subarray Sum With Length Divisible by K (Leetcode Medium)Programming Live with Larry · 18:34 · 869 views
Daily Leetcode #2067: Nov 27, 2025 - 3381. Maximum Subarray Sum With Length Divisible by KProgramming Live with Larry · 13:18 · 601 views
LeetCode 3381 🔥 Maximum Subarray Sum Divisible by K | Prefix Mod Trick + Optimal Solution Study Placement · 24:20 · 598 views
3381. Maximum Subarray Sum With Length Divisible by K | Leetcode Daily - PythonLeetcode Daily · 9:09 · 505 views
Maximum Subarray Sum With Length Divisible by K | Leetcode 3381 | Java HindiKernel Queen 👑 · 12:19 · 382 views
Leetcode Weekly Contest 427 || Problem C || 3381. Maximum Subarray Sum With Length Divisible by Ksollcode · 10:43 · 292 views
The problem
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] <= 109
Approach overview
Problem 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.
Solution
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.
class Solution:
def maxSubarraySum(self, nums: List[int], k: int) -> int:
f = [inf] * k
ans = -inf
s = f[-1] = 0
for i, x in enumerate(nums):
s += x
ans = max(ans, s - f[i % k])
f[i % k] = min(f[i % k], s)
return ansclass Solution {
public long maxSubarraySum(int[] nums, int k) {
long[] f = new long[k];
final long inf = 1L << 62;
Arrays.fill(f, inf);
f[k - 1] = 0;
long s = 0;
long ans = -inf;
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
ans = Math.max(ans, s - f[i % k]);
f[i % k] = Math.min(f[i % k], s);
}
return ans;
}
}class Solution {
public:
long long maxSubarraySum(vector<int>& nums, int k) {
using ll = long long;
ll inf = 1e18;
vector<ll> f(k, inf);
ll ans = -inf;
ll s = 0;
f[k - 1] = 0;
for (int i = 0; i < nums.size(); ++i) {
s += nums[i];
ans = max(ans, s - f[i % k]);
f[i % k] = min(f[i % k], s);
}
return ans;
}
};function maxSubarraySum(nums: number[], k: number): number {
const f: number[] = Array(k).fill(Infinity);
f[k - 1] = 0;
let ans = -Infinity;
let s = 0;
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
ans = Math.max(ans, s - f[i % k]);
f[i % k] = Math.min(f[i % k], s);
}
return ans;
}func maxSubarraySum(nums []int, k int) int64 {
inf := int64(1) << 62
f := make([]int64, k)
for i := range f {
f[i] = inf
}
f[k-1] = 0
var s, ans int64
ans = -inf
for i := 0; i < len(nums); i++ {
s += int64(nums[i])
ans = max(ans, s-f[i%k])
f[i%k] = min(f[i%k], s)
}
return ans
}impl Solution {
pub fn max_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
let k = k as usize;
let inf = 1i64 << 62;
let mut f = vec![inf; k];
f[k - 1] = 0;
let mut s = 0i64;
let mut ans = -inf;
for (i, &x) in nums.iter().enumerate() {
s += x as i64;
ans = ans.max(s - f[i % k]);
f[i % k] = f[i % k].min(s);
}
ans
}
}Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Subarray Sum With Length Divisible by K easy or hard?
The problem is generally rated Medium because the brute-force idea is straightforward but the optimal solution requires recognizing a prefix-sum and modulo pattern. Once the relationship between index remainders and valid subarray lengths is identified, the implementation becomes a linear-time scan.
Maximum Subarray Sum With Length Divisible by K Python/Java solution
Implement the prefix sum + modulo grouping approach. Maintain an array or map storing the minimum prefix sum for each remainder i % k. While iterating through the array, compute the current prefix sum, check the stored minimum for that remainder, update the maximum subarray sum, and refresh the minimum prefix if needed.
How to solve Maximum Subarray Sum With Length Divisible by K in O(n)?
Compute a running prefix sum while iterating through the array. For each index i, calculate r = i % k and maintain the smallest prefix sum previously seen with the same remainder. The candidate subarray sum becomes prefix[i] minus that stored minimum. Updating these values during a single traversal yields an O(n) solution.
What is the best approach for Maximum Subarray Sum With Length Divisible by K?
The most efficient approach uses prefix sums combined with grouping indices by their modulo k value. If two prefix indices share the same remainder i % k, the subarray between them has length divisible by k. By tracking the minimum prefix sum for each remainder, you can compute the maximum subarray sum in O(n) time and O(k) space.
Is Maximum Subarray Sum With Length Divisible by K asked at Google/Amazon/Meta?
Variants of prefix sum and subarray divisibility problems appear frequently in interviews at companies like Google, Amazon, and Meta. Problems involving prefix sums, modulo grouping, and maximum subarray calculations are common because they test pattern recognition and optimization skills.
What data structure is used in Maximum Subarray Sum With Length Divisible by K?
The solution primarily uses a prefix sum array and a structure to track the minimum prefix value for each remainder group. This structure is typically an array of size k or a hash table mapping remainder values to the smallest prefix sum seen so far.
What is the time complexity of Maximum Subarray Sum With Length Divisible by K?
The optimal solution runs in O(n) time using a single pass through the array with prefix sums and remainder tracking. Space complexity is O(k) because the algorithm stores the minimum prefix sum for each modulo class from 0 to k-1.