DSA sheet · Arrays · Prefix sum pattern

Continuous Subarray Sum

The fourth prefix sum problem, and the trickiest so far. We must find a piece of the array whose sum is a multiple of k and whose length is at least 2. The teacher starts with the obvious two-loop solution, shows it gets TLE, explains why sliding window can't help when the rule is "divisible by k", and then builds the real trick step by step: store the remainder of each prefix sum (not the sum itself) in a hashmap, together with the index where it first appeared. If the same remainder shows up again, the piece in between is a multiple of k. She also shows two traps along the way: plain subtraction misses multiples like 12 and 18, and forgetting {0: -1} in the map misses answers that start at index 0.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every subarray of length ≥ 2
• Part B · Optimal: prefix sum remainders in a hashmap
• Part C · Revision page

Part 0 · Before starting

Subarray

A subarray is a continuous piece of the array: you pick a start index and an end index and take everything in between, without skipping. In [23, 2, 4, 6, 7], [2, 4] and [2, 4, 6] are subarrays; [2, 6] is not (it skips the 4). Its length is how many numbers it holds.

What is a prefix sum?

The prefix sum at index i is the total of everything from index 0 up to and including i. Each cell is built from the one before: prefix[i] = prefix[i-1] + nums[i], so we never re-add the whole piece.

Why sum(l..r) = prefix[r] − prefix[l−1]

prefix[r] covers 0…r. prefix[l−1] covers 0…l−1. Subtracting removes the common part 0…l−1 and leaves exactly l…r. Example: sum of [2, 4] (indexes 1..2) = prefix[2] − prefix[0] = 29 − 23 = 6 ✓.

The "−1 / empty prefix" trick: if the subarray starts at index 0 (l = 0), we need prefix[-1], which doesn't exist. We pretend there is an empty prefix before index 0 with sum 0, sitting at index −1. Then sum(0..r) = prefix[r] − 0. This little "0 at index −1" will be the key fix in Part B.

Remainder (modulo, %)

a % k is what is left over after taking out as many whole k's as possible from a. 29 % 6 = 5, because 29 = 4 × 6 + 5. A number is a multiple of k (divisible by k) exactly when its remainder is 0: 42 % 6 = 0, and 0 % 6 = 0 too, so 0 counts as a multiple of k (0 = 0 × k).

Hashmap

A hashmap (Python dict) stores key → value pairs and can answer "do you have this key, and what is its value?" in about O(1) time. Here the key will be a remainder and the value an index.

The four array patterns (the teacher's checklist)

Part A · Brute force: try every subarray of length ≥ 2

LeetCode 523

1The question in simple words

You get an integer array nums and an integer k. Return True if there is a good subarray, else False. A subarray is good when both are true:

• its length is at least 2, and
• its sum is a multiple of k (sum % k == 0).

The single number 6 is also a multiple of 6, but it is not good because its length is only 1. Also, we only need to know whether a good subarray exists. As soon as we find one, we can return True; no counting.

2What the constraints tell us

• 1 <= nums.length <= 10⁵ → an O(n²) solution is about 10¹⁰ steps; beyond ~10⁸ we get TLE. We'll have to optimise. A length-1 array can never have a good subarray → False.
• 0 <= nums[i] <= 10⁹ → no negative numbers. The teacher stresses this because it helps pick the pattern later (it rules out Kadane).
• 1 <= k → k is never 0, so % k never divides by zero.
• The total sum fits in a 32-bit int (LeetCode promises sum ≤ 2³¹ − 1). Python doesn't care either way.

3Intuition

List every subarray, add it up, and test "% k == 0". To list subarrays, fix a start i, then let a second pointer j walk forward, growing the piece one number at a time: [23], [23, 2], [23, 2, 4], [23, 2, 4, 6], [23, 2, 4, 6, 7]. Then move i forward and repeat.

4Building the logic from examples

Length ≥ 2 → start j at i + 1

The first piece in the list above, [23], has length 1, so it is never allowed. If j starts at i + 1, the very first piece we look at is already [nums[i], nums[i+1]], length 2. That way the length rule is satisfied automatically and we don't need a separate length check.

i only needs to go up to n − 2

If i stood on the last index, j = i + 1 would be past the end; there's no pair to make. So i runs from 0 to n − 2 (in Python, range(n - 1)).

Where should the running sum start?

When to check

Add nums[j] first, then check sum % k == 0. Starting at i = 0 with k = 6: 25 → no, 29 → no, 35 → no, 42 → 42 % 6 = 0 yes → return True right there. If both loops finish without returning, no good subarray exists → return False.

5Approach steps

1. For each start i from 0 to n − 2: total = nums[i].
2. For each j from i + 1 to n − 1: total += nums[j].
3. If total % k == 0 → return True (length is already ≥ 2).
4. After both loops → return False.

6Code (Python)

class Solution:
    def checkSubarraySum(self, nums, k):
        n = len(nums)
        for i in range(n - 1):              # start; last index can't start a pair
            total = nums[i]                 # j never visits i, so include it here
            for j in range(i + 1, n):       # j = i + 1 -> length is at least 2
                total += nums[j]
                if total % k == 0:          # multiple of k
                    return True
        return False

7Code line by line

8Dry run (hand table)

nums = [23, 2, 4, 6, 7], k = 6.

With i = 1 we would also have found [2, 4] = 6, but we already returned at i = 0.

9Complexity & remember

• Time O(n²): the outer loop runs about n − 1 times, the inner one up to n − 1 times. (n − 1)(n − 1) = n² − 2n + 1; the biggest term is n², so O(n²). For n = 10⁵ → 10¹⁰ → TLE (the teacher submits it and gets TLE, as expected).
• Space O(1).

Part B · Optimal: prefix sum remainders in a hashmap

1The question

Same question. We want one pass over the array: O(n).

2Constraints → which pattern?

• Kadane's ✗: it's for max sums with negative numbers. Our numbers are all ≥ 0 and we don't want a max.
• Two pointers ✗: we need a whole subarray (everything in between), not just two numbers.
• Sliding window ✗ (the interesting one, see below).
• Prefix sum ✓.

Why sliding window fails here

The teacher explains how a window works with a target of 12 and numbers 3, 5, 5, 2: take 3 (sum 3, need more → grow), add 5 (8, still short → grow), add 5 (13, too much → shrink from the left, drop the 3 → 10), add 2 (12 → found). The window can move because there is a clear rule: too small → grow, too big → shrink.

"Multiple of k" has no such rule. With k = 12, the sums 12, 24, 36, … are all good. A sum bigger than 12 isn't "too big"; it might be 24. So the window has no idea when to stop growing or when to shrink. Whenever the condition is "divisible by" / "multiple of", sliding window is out.

3Intuition: same remainder ⇒ the gap is a multiple of k

From Part 0, the sum of a piece is a difference of two prefix sums. In [23, 2, 4, 6, 7], prefix[0] = 23 and prefix[2] = 29; the piece between them, [2, 4], has sum 29 − 23 = 6, which is a multiple of 6.

But "difference exactly k" is not enough (the piece could sum to 2k or 3k). The real question is: when is the difference of two numbers a multiple of k? Answer: when both numbers leave the same remainder after dividing by k.

Drawn example: 11 and 23 with k = 6

multiples of 6:  0     6     12    18    24
                 |-----|-----|-----|-----|
prefix 11:       |-----|---- 11              11 = 6 + 5      → remainder 5
prefix 23:       |-----|-----|-----|---- 23  23 = 18 + 5     → remainder 5
                             \___________/
                    23 - 11 = 12 = two full jumps of 6       → multiple of 6 ✓

Both numbers are "5 steps past some multiple of 6". When you subtract them, the two "+5" leftovers cancel, and only whole jumps of 6 remain. In general: if a = q₁·k + r and b = q₂·k + r (same r), then b − a = (q₂ − q₁)·k, a multiple of k. And if the remainders were different, the leftovers wouldn't cancel, so the gap would not be a multiple.

So we don't store prefix sums; we store their remainders. The moment a remainder repeats, we have found a subarray whose sum is a multiple of k.

4Building the logic from examples

Step 1: prefix sums alone don't tell us the length → we need indexes

The teacher's first worry: suppose we find two prefix sums that differ by a multiple of k. How do we know the piece between them has length ≥ 2? Look at [23, 2, 4, 6, 7]: prefix 29 (index 2) and prefix 35 (index 3) differ by 6, but that piece is just [6], length 1. Not allowed.

If we know the index where each earlier prefix ended, the length is easy: the piece runs from (earlier index + 1) to (current index), so length = current index − earlier index. E.g. prefix 23 at index 0 and prefix 29 at index 2 → length 2 − 0 = 2 ✓ (the piece [2, 4]).

So we need a structure that stores "value → index" and finds a value in O(1): a hashmap.

Step 2: first try, search for prefix − k (and why it fails)

A first idea (like Subarray Sum Equals K): at prefix 23, look up 23 − 6 = 17 in the map. If 17 was a prefix earlier, the gap between them is exactly 6. With [17, 2, 4] the prefixes are 17, 19, 23, and at 23 we would find 17 ✓.

Now the teacher's counter-example, nums = [11, 5, 7, 6], k = 6:

Searching 29 − 6 = 23 finds index 2, but that piece is just [6] (length 1) → rejected. Searching for "exactly k" finds nothing else, so we'd wrongly say False. Yet [5, 7] sums to 12, a multiple of 6, length 2! A gap of 12 (or 18, 24…) is just as good as 6, and subtracting k only catches 6. Replace subtraction with the remainder.

Step 3: store remainders, look for a repeat

Same array, remainders 5, 4, 5, 5:

• index 0: prefix 11, remainder 5. Not in the map → store 5 → 0.
• index 1: prefix 16, remainder 4. Not in the map → store 4 → 1.
• index 2: prefix 23, remainder 5. Seen before, at index 0! Length = 2 − 0 = 2 ≥ 2 ✓. The piece is indexes 1..2 = [5, 7] = 12 = 2 × 6. Return True.

Step 4: why the map keeps the first index (never overwrite)

The teacher's code only stores a remainder when it is not already in the map. If the remainder is found but the piece is too short, she does not replace the old index. Why does that matter?

We want the longest possible piece for each remainder, so the length test has the best chance to pass. The earliest index gives the longest piece. Example: nums = [1, 0, 0], k = 2.

The good subarray [0, 0] (sum 0 = 0 × 2, a multiple) is missed if we overwrite. So: store a remainder only the first time you see it.

Step 5: the {0: -1} fix, for pieces that start at index 0

The teacher's last example: nums = [2, 4], k = 6. The whole array, 2 + 4 = 6, is good. Run the rules on an empty map:

• index 0: prefix 2, remainder 2 → not seen → store 2 → 0.
• index 1: prefix 6, remainder 0 → not seen → store 0 → 1. Loop ends → False. Wrong!

What went wrong: at prefix 6 we needed an earlier prefix with remainder 0. That earlier prefix is the empty prefix from Part 0 (sum 0, before index 0). So we put it in the map at the start: {0: -1}. Its index is −1 (not 0, which is a real element).

• Now at index 1: remainder 0 is in the map at index −1 → length = 1 − (−1) = 2 ✓ → True. The piece is indexes 0..1 = [2, 4].

5Approach steps

1. seen = {0: -1} (remainder → first index; the empty prefix).
2. prefix = 0. For each index i: prefix += nums[i], rem = prefix % k.
3. If rem is in seen: if i - seen[rem] >= 2 → return True (otherwise do nothing; keep the older index).
4. Else: seen[rem] = i.
5. After the loop → return False.

6Code (Python)

class Solution:
    def checkSubarraySum(self, nums, k):
        seen = {0: -1}                      # remainder -> FIRST index; empty prefix at -1
        prefix = 0
        for i in range(len(nums)):
            prefix += nums[i]
            rem = prefix % k
            if rem in seen:
                if i - seen[rem] >= 2:      # piece seen[rem]+1 .. i has length >= 2
                    return True
                # too short: do NOT overwrite, the older index gives a longer piece
            else:
                seen[rem] = i               # first time we meet this remainder
        return False

7Code line by line

8Dry run (hand tables)

Example 1: nums = [23, 2, 4, 6, 7], k = 6 → True

The piece is indexes 1..2 = [2, 4] = 6 ✓.

Example 2: nums = [23, 2, 6, 4, 7], k = 13 → False

Example 3: nums = [2, 4], k = 6 (the {0: −1} case)

9Complexity & remember

• Time O(n): one pass; each map lookup/insert is O(1). (The teacher's submission beat about 94% of solutions.)
• Space O(k), the teacher's point: the keys are remainders, and a remainder can only be 0 … k−1, so there are at most k different keys. More precisely it's O(min(n, k)), since we add at most one key per index.

Part C · Revision page

s = Solution()
print(s.checkSubarraySum([23, 2, 4, 6, 7], 6))    # True  ([2, 4])
print(s.checkSubarraySum([23, 2, 6, 4, 7], 6))    # True  (whole array = 42)
print(s.checkSubarraySum([23, 2, 6, 4, 7], 13))   # False
print(s.checkSubarraySum([11, 5, 7, 6], 6))       # True  ([5, 7] = 12)
print(s.checkSubarraySum([2, 4], 6))              # True  (needs {0: -1})
print(s.checkSubarraySum([1, 0, 0], 2))           # True  (needs the FIRST index)
print(s.checkSubarraySum([6], 6))                 # False (length 1)
print(s.checkSubarraySum([5, 0, 0, 0], 3))        # True  ([0, 0])

Based on this video: Continuous Subarray Sum | Prefix Sum pattern