Intuition

We aim to find the maximum sum of a subarray whose length is divisible by k. Instead of examining all possible subarrays, which would be inefficient, we employ a snake-like sliding trick. This involves moving forward one step at a time, keeping track of the “weak front” numbers that might limit our sum, and extending the subarray only if the new number increases the total. Imagine it like a snake: the head moves forward, the tail (weak numbers) is dropped when necessary, and the sum grows as we progress.

Approach

1. Maintain a minPrefix array of size k to store the smallest running sums for each remainder modulo k.

   • Initialize with [0, ∞, ∞, …] (length k). The initial 0 represents an empty subarray with sum 0, while ∞ indicates that no valid subarray exists yet for other remainders.

2. Iterate through nums:

   • Update the running total.

   • Evaluate the current sum by subtracting the smallest prefix for the same remainder (total - minPrefix[length % k]). If this exceeds maxSum, update maxSum.

   • Update minPrefix for length % k with the smaller of itself or the running total, preserving the “weak front” numbers as candidates for future subarrays.

3. This method naturally handles subarrays of lengths k, 2k, 3k… without additional loops.

Example: nums = [-5,1,2,-3,4], k = 2

• Start: minPrefix = [0, ∞]

• Index 0 (-5) → only 1 item → invalid → shift → minPrefix = [0, -5]

• Index 1 (1) → running sum = -4 → better than -5 → update → minPrefix = [-4, -5]

  • We retain only the weakest numbers at the front; update index 0 from 0 → -4.

• Index 2 (2) → use minPrefix[1] = -5 → sum = 3 → maxSum updated

• Index 4 (4) → use minPrefix[0] = -4 → sum = 4 → maxSum updated

If the array is extended later (e.g., 10 at the end), we replace one of the weak numbers in minPrefix based on index % k and continue. The snake keeps moving forward, only discarding weak numbers that hinder the sum.

I watched NeetCode's approach on YouTube but wanted to explain it in my own terms here. You should definitely watch his video too! Watch NeetCode's Video

Complexity

• Time complexity: O(n) — we traverse the array once.

• Space complexity: O(k) — minPrefix array of size k.

Code

var maxSubarraySum = function(nums, k) {
    var minPrefix = new Array(k).fill(Infinity);
    minPrefix[0] = 0;

    var total = 0;      // running sum
    var maxSum = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        total += nums[i];
        let length = i + 1;
        let mod = length % k;

        // check if current subarray ending here gives a bigger sum
        let addSum = total - minPrefix[mod];
        if (addSum > maxSum) {
            maxSum = addSum;
        }

        // update the “weak front” for this modulo
        minPrefix[mod] = Math.min(minPrefix[mod], total);
    }

    return maxSum;
};