Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
[1,2] 1
[-1,-2,-3,-4,-5] 4
[-5,1,2,-3,4] 2
subarray-sums-divisible-by-k)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3381: Maximum Subarray Sum With Length Divisible by K
class 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;
}
}
// Accepted solution for LeetCode #3381: Maximum Subarray Sum With Length Divisible by K
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
}
# Accepted solution for LeetCode #3381: Maximum Subarray Sum With Length Divisible by K
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 ans
// Accepted solution for LeetCode #3381: Maximum Subarray Sum With Length Divisible by K
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
}
}
// Accepted solution for LeetCode #3381: Maximum Subarray Sum With Length Divisible by K
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.