Maximum Subarray Sum With Length Divisible by K

Introduction

Kadane's algorithm is one of the first "aha" moments most people have with dynamic programming — a single pass, a running max, and suddenly you can find the maximum sum subarray in linear time. It's elegant, it's fast, and it's also completely useless the moment someone adds one extra constraint: the subarray's length has to be divisible by some number K.

This is exactly the kind of twist interviewers love. It's not a harder version of the same problem — it's a different problem wearing the same clothes. The array is the same, the word "subarray" is the same, but the tool that solved it a minute ago no longer applies. What interviewers are actually testing here is whether you can recognize why a familiar algorithm breaks, and whether you can rebuild the right structure from first principles instead of forcing Kadane's algorithm to do something it was never designed to do.

If you're preparing for interviews, this problem is worth sitting with. It teaches a pattern — prefix sums bucketed by index remainder — that shows up again and again anywhere a constraint depends on position rather than value.

Problem Overview

You're given an array of integers and an integer K. Your job is to find the maximum possible sum of a contiguous subarray, but with one restriction: the length of that subarray must be a multiple of K. So valid lengths are K, 2K, 3K, and so on — never anything in between.

Return the maximum sum achievable under that restriction. It's guaranteed (or you should explicitly handle the case) that the array is at least K elements long, since no valid subarray can exist otherwise.

The core difficulty is that the constraint isn't on the values in the subarray — it's on the distance between its two endpoints. That distinction is what makes this problem different from anything Kadane's algorithm was built to solve.

Example

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

Valid subarray lengths are 2 or 4. Let's check the candidates:

• Length 2: [-5,1]=-4, [1,2]=3, [2,-3]=-1, [-3,4]=1
• Length 4: [-5,1,2,-3]=-5, [1,2,-3,4]=4

The best value across all valid-length subarrays is 4, coming from [1, 2, -3, 4] — the last four numbers. Notice this subarray has length 4, which is 2 × k, not k itself. The maximum doesn't always come from the smallest valid length, which is exactly why you can't just check length-k windows and call it done.

Intuition

Start with the obvious approach: try every subarray, check if its length divides by K, and keep the best sum. That's correct, but it's O(n²) because you're recomputing sums for overlapping ranges over and over.

The standard fix for "sum of a range" problems is prefix sums. Define prefix[i] as the sum of the first i elements. Then the sum of any subarray from index j to i-1 is just:

prefix[i] - prefix[j]

That turns the whole problem into: find two prefix-sum indices whose difference in value is as large as possible, subject to a constraint on the difference in their index.

Here's the key realization: for prefix[i] - prefix[j] to represent a subarray of length divisible by K, the indices i and j must be exactly K, 2K, 3K, ... apart. And two numbers differ by a multiple of K if and only if they leave the same remainder when divided by K. So instead of thinking about which pairs of indices are "far enough apart," you can just group indices by i % K — every index in the same group is automatically a valid partner for every other index in that group.

Within a group, since you're computing prefix[i] - prefix[j] and want to maximize it, you want the smallest prefix[j] seen so far in that group. That's the whole strategy: bucket prefix sums by index modulo K, track a running minimum per bucket, and compare against it as you go.

One subtlety trips people up: you can't let a bucket's minimum include the current index or anything less than K steps in the past — otherwise you'd be allowing a subarray of length less than K (like length 0) to sneak in. The fix is to delay: before using bucket r's minimum at index i, only fold in the prefix sum from index i - K once you've actually reached it. That guarantees every pairing respects the minimum length requirement.

Brute Force Solution

Idea: Check every subarray, compute its sum directly, and only consider it if its length is divisible by K.

Algorithm:

1. For every start index i, for every end index j >= i, compute the sum of nums[i:j+1].
2. If (j - i + 1) % k == 0, compare the sum against the running best.

Advantages: Trivial to write correctly, easy to verify, no edge cases to reason about.

Disadvantages: Recomputes overlapping sums repeatedly; scales terribly as n grows.

Time complexity: O(n²) if you maintain a running sum per start index (or O(n³) with naive resummation). Space complexity: O(1) beyond the input.

For n = 100,000, that's on the order of billions of additions — measurably too slow for any reasonable time limit.

Optimal Solution

The optimal approach has two passes, both linear:

Pass 1 — build prefix sums. prefix[0] = 0, and prefix[i+1] = prefix[i] + nums[i]. This one array lets you compute any subarray sum in constant time afterward.

Pass 2 — bucket by remainder, track minimums, maximize the difference. Walk through indices 0 to n. At each index i:

1. Compute r = i % k.
2. Check whether i - k is a valid, already-processed index. If so, fold prefix[i - k] into bucket r's running minimum.
3. If bucket r has a valid minimum recorded, compare prefix[i] - min_in_bucket[r] against the best answer seen so far.

The delay in step 2 is what enforces the minimum-length-K constraint — a bucket's minimum only becomes "eligible" for comparison once you're at least K indices past it.

Index i	prefix[i]	i % k	Bucket ready?	Best sum so far
0	0	0	no (nothing k back yet)	—
1	-5	1	no	—
2	-4	0	yes (prefix[0]=0 folds in)	-4
3	-2	1	yes (prefix[1]=-5 folds in)	3
4	0	0	bucket 0 min now min(0,-4)=-4	4
5	4	1	bucket 1 min now min(-5,-2)=-5	4

Final answer: 4 — matching the expected result.

Python Code

def max_subarray_sum_divisible_by_k(nums: list[int], k: int) -> int:
    n = len(nums)
    if n < k:
        raise ValueError("No subarray of valid length exists")

    # Prefix sums: prefix[i] = sum of nums[0:i]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    # One running minimum per remainder bucket
    bucket_min = [None] * k
    best = float("-inf")

    for i in range(n + 1):
        r = i % k
        back = i - k
        if back >= 0:
            # This prefix sum is now old enough to pair with
            if bucket_min[r] is None or prefix[back] < bucket_min[r]:
                bucket_min[r] = prefix[back]

        if bucket_min[r] is not None:
            best = max(best, prefix[i] - bucket_min[r])

    return best

Code Walkthrough

• prefix = [0] * (n + 1) — a size n+1 array so prefix[i] always represents "sum of the first i elements," with prefix[0] = 0 as the empty-prefix base case.
• The first loop fills in prefix sums in one linear pass — nothing clever, just running accumulation.
• bucket_min holds one slot per remainder class 0..k-1. None means "no eligible prefix sum yet" — using None instead of float('inf') avoids accidentally treating an uninitialized bucket as usable.
• Inside the main loop, back = i - k is the index that just became "old enough" to serve as a valid left endpoint for a subarray ending at i. If it's non-negative, we fold prefix[back] into that bucket's minimum.
• We only compare against bucket_min[r] after trying to update it, so best never uses a prefix sum from less than k steps back.

Dry Run

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

• prefix = [0, -5, -4, -2, -5, -1] — wait, let's compute carefully: prefix[0]=0, prefix[1]=-5, prefix[2]=-4, prefix[3]=-2, prefix[4]=-5, prefix[5]=-1.

Walking i = 0 to 5:

• i=0: r=0, back=-2 (skip). bucket_min[0] still None.
• i=1: r=1, back=-1 (skip). bucket_min[1] still None.
• i=2: r=0, back=0 → fold prefix[0]=0 into bucket 0. bucket_min[0]=0. Compare: prefix[2] - 0 = -4 - 0 = -4. best=-4.
• i=3: r=1, back=1 → fold prefix[1]=-5. bucket_min[1]=-5. Compare: prefix[3] - (-5) = -2 + 5 = 3. best=3.
• i=4: r=0, back=2 → fold prefix[2]=-4, so bucket_min[0]=min(0,-4)=-4. Compare: prefix[4] - (-4) = -5 + 4 = -1. best stays 3.
• i=5: r=1, back=3 → fold prefix[3]=-2, so bucket_min[1]=min(-5,-2)=-5. Compare: prefix[5] - (-5) = -1 + 5 = 4. best=4.

Final answer: 4, matching the expected output — corresponding to the subarray [1, 2, -3, 4] (prefix[5] - prefix[1]).

Complexity Analysis

Time: O(n). Building prefix sums is one linear pass. The bucket pass is also linear — every index does constant work (one bucket lookup, one possible update, one comparison), regardless of k.

Space: O(n + k). The prefix array is O(n), and the bucket array is O(k). If you're willing to overwrite nums in place or stream prefix sums without storing them all, you can trim this, but O(n) is already optimal since you need to read every element at least once.

This is correct because every subarray whose length divides K corresponds to exactly one pair of same-remainder prefix indices at least K apart, and the bucket-minimum strategy guarantees we always compare against the best possible left endpoint for each right endpoint, in the order the constraint allows.

Alternative Solutions

A sliding-window variant exists for the special case where you only care about subarrays of length exactly K (not multiples of K) — that reduces to a fixed-size window sum, solvable in O(n) without buckets at all. But it doesn't generalize to "any multiple of K," which is why the prefix-sum-bucket approach is necessary here.

You could also solve this with dynamic programming, defining dp[i][r] as the best sum ending at index i for subarrays whose length is congruent to r — but this collapses to the same bucket-based logic with extra bookkeeping, so it offers no real advantage over the direct prefix-sum method.

Edge Cases

• Array shorter than k: No valid subarray exists. Raise an error or return a sentinel value depending on the problem's contract — don't silently return 0, which could be mistaken for a real answer.
• All negative numbers: The algorithm still works — best will correctly settle on the least-negative valid subarray, since it's tracking maximum difference, not assuming positivity.
• k == 1: Every subarray length qualifies, and the problem reduces to standard Kadane's-style maximum subarray sum. The bucket approach still works correctly with a single bucket.
• Array length exactly k: Only one valid subarray exists — the whole array. The algorithm should return its total sum.
• Duplicate values or all-zero array: No special handling needed; prefix sums and comparisons behave normally.

Common Mistakes

1. Applying Kadane's algorithm directly. It has no concept of length constraints, so it will happily return a subarray whose length doesn't divide by K.
2. Bucketing by prefix sum value instead of index. That's the strategy for "Subarray Sums Divisible By K," a different problem where the sum must be divisible. Here, it's the length — so you must bucket by index modulo K, not value modulo K.
3. Updating a bucket's minimum before checking eligibility. If you let prefix[i] update bucket i % k immediately, you can end up pairing an index with itself or with something less than K steps away, silently allowing invalid short subarrays.
4. Forgetting the delay-by-K step entirely. Without it, the algorithm looks correct on some inputs by coincidence but fails whenever the true best pairing depends on strict minimum spacing.
5. Not handling the case where n < k. This produces either an index error or a wrong default sum instead of a clear signal that no valid subarray exists.

Interview Questions

• Why doesn't Kadane's algorithm work here, precisely?
• What's the time and space complexity, and why is space O(n + k) rather than O(n)?
• Can you reduce space to O(k) by not storing the full prefix array?
• How would the solution change if the constraint were "length exactly K" instead of "any multiple of K"?
• How does this differ from "Subarray Sums Divisible By K," and why does that difference change what you bucket by?

Similar Problems

• Subarray Sums Divisible By K — nearly identical mechanics, but buckets by prefix sum value mod K instead of index, since the constraint is on the sum, not the length.
• Maximum Subarray (Kadane's classic) — the unconstrained version; useful baseline for understanding what changes when a length constraint is added.
• Continuous Subarray Sum — another prefix-sum-and-remainder problem, checking for a subarray summing to a multiple of K.
• Maximum Size Subarray Sum Equals K — uses prefix sums with a hash map to find the longest subarray summing to an exact target, a close cousin in technique.

Key Takeaways

Prefix sums turn subarray sum problems into simple subtraction between two points. When a constraint is about position (like length divisible by K), bucket by index, not value. When a constraint is about the sum itself, bucket by value instead. And whenever a "must be spaced at least this far apart" rule shows up, look for a delay mechanism — update the eligible pool one step behind where you're reading from it. Get those three ideas straight and this whole class of problem becomes a single clean linear pass.

Watch the Video

Watching this one explained end to end — including the two pop quiz questions and the actual timed benchmark — makes the bucket-delay trick click faster than reading alone. Catch the full walkthrough here: {LINK}

About the Series

This is part of Fun with Learning Technology, a series that takes coding interview problems apart the way you'd actually think through them at a whiteboard — not the polished answer, but the false starts, the "wait, why doesn't that work," and the moment the right structure clicks into place. New drops land regularly, covering algorithms, data structures, and the kind of intuition-building that makes the next unfamiliar problem feel a little less unfamiliar.

Call To Action

If this walkthrough helped the bucket-and-delay trick click for you, drop a like on the video and subscribe on YouTube so the next daily problem lands in your feed. For deeper write-ups like this one delivered straight to your inbox, subscribe to the Substack. And if you've got a cleaner way to think about the delay step, or a problem you'd like tackled next, leave a comment — the best future episodes usually start there.

---

class Solution:
    def maxSubarraySum(self, nums, k):
        n = len(nums); prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        min_prefix = [float('inf')] * k
        best = float('-inf')
        for i in range(n + 1):
            r = i % k
            if i - k >= 0:
                min_prefix[r] = min(min_prefix[r], prefix[i - k])
            if min_prefix[r] != float('inf'):
                best = max(best, prefix[i] - min_prefix[r])
        return best