# How to Solve Leetcode 3381: Maximum Subarray Sum with Length Divisible by k

# 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](https://www.youtube.com/watch?v=8rwW3iKqP34)

# Complexity

* Time complexity: O(n) — we traverse the array once.
    
* Space complexity: O(k) — minPrefix array of size k.
    

# Code

```javascript
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;
};
```