Continuous Subarray Sum: Prefix Sums Meet Modular Arithmetic

LeetCode #523, Continuous Subarray Sum, is a medium-level problem that combines two powerful techniques: prefix sums and modular arithmetic. You are given an integer array nums and an integer k, and you need to determine whether nums contains a "good subarray." A good subarray has a length of at least two, and its elements sum to a multiple of k.

At first glance, this looks like it could require checking every possible subarray. But there is a clean O(n) solution hiding behind a single mathematical observation about remainders.

The problem

Given an integer array nums and an integer k, return true if nums has a good subarray. A subarray is good if:

• Its length is at least 2
• The sum of its elements is a multiple of k (i.e., the sum equals n * k for some integer n, including n = 0)

nums = [23, 2, 4, 6, 7], k = 6
# Subarray [2, 4] sums to 6, which is 1 * 6. Return True.

nums = [23, 2, 6, 4, 7], k = 6
# Subarray [23, 2, 6, 4, 7] sums to 42, which is 7 * 6. Return True.

nums = [23, 2, 6, 4, 7], k = 13
# Subarray [2, 6, 4] sums to 12? No. But [23, 2, 6, 4, 7] sums to 42? No. Return False.

The brute force approach would check every pair of indices and compute the subarray sum for each, giving O(n^2) time at best. We need something smarter.

The key insight: remainder repetition

Here is the idea that makes this problem click. Build a running prefix sum as you scan through the array. At each index, compute the prefix sum modulo k. If two prefix sums at indices i and j produce the same remainder when divided by k, then the subarray from i+1 to j has a sum that is divisible by k.

Why? Because prefix[j] - prefix[i] gives the subarray sum from i+1 to j. If both prefix[j] and prefix[i] leave the same remainder when divided by k, their difference is a multiple of k.

There is one extra requirement: the subarray must have length at least 2, which means j - i must be at least 2. So we store the first index where each remainder appears in a hash map. When we see a remainder that is already in the map, we check whether the gap between the current index and the stored index is at least 2.

The solution

def checkSubarraySum(nums, k):
    remainder_map = {0: -1}
    prefix_sum = 0

    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k

        if remainder in remainder_map:
            if i - remainder_map[remainder] >= 2:
                return True
        else:
            remainder_map[remainder] = i

    return False

Let us walk through how it works:

1. Initialize the map. We set remainder_map = {0: -1} so that a prefix sum divisible by k at index 1 or later triggers a match (since the gap from -1 is at least 2).
2. Accumulate the prefix sum. For each element, add it to the running total.
3. Compute the remainder. Take prefix_sum % k. This tells us the equivalence class of the current prefix sum.
4. Check the map. If this remainder was seen before, check whether the indices are far enough apart. If so, we found a valid subarray.
5. Store first occurrence only. If the remainder is new, record the current index. We deliberately skip updating the index when the remainder already exists, because we want the earliest occurrence to maximize the gap.

Step-by-step walkthrough

Let us trace through nums = [23, 2, 4, 6, 7] with k = 6.

The algorithm finds the answer at index 2. Both index 0 and index 2 have a prefix sum remainder of 5 when divided by 6. The gap is 2, which satisfies the length requirement. The subarray [2, 4] (indices 1 through 2) sums to 6, which is indeed a multiple of 6.

Complexity analysis

Time: O(n). We iterate through the array once. Each hash map lookup and insertion is O(1) on average.

Space: O(min(n, k)). The hash map stores at most k distinct remainders (since remainders range from 0 to k - 1). If n is smaller than k, we store at most n + 1 entries.

The building blocks

Prefix sum with modular arithmetic

prefix_sum = 0
for num in nums:
    prefix_sum += num
    remainder = prefix_sum % k

This is the standard prefix sum pattern, extended with a modulo operation. The prefix sum itself can grow large, but we only care about the remainder. Two prefix sums with the same remainder produce a subarray sum that is a multiple of k. This pattern shows up in any problem where you need to find subarrays whose sums satisfy a divisibility condition.

First-occurrence hash map

if remainder in remainder_map:
    check_gap()
else:
    remainder_map[remainder] = i

By storing only the first index where each remainder appears, we maximize the gap between occurrences. This is the key to satisfying the "length at least 2" constraint. If we stored the latest index instead, we might miss valid subarrays. This "store first, check later" pattern appears in many problems that need to find the longest or earliest occurrence of some property.

Edge cases

• Subarray of exactly length 2. If two consecutive elements sum to a multiple of k, the algorithm catches this. For nums = [0, 0] and k = 1, the prefix sum at index 1 has remainder 0, matching the seed at index -1 with a gap of 2.
• k = 1. Every integer is a multiple of 1, so any subarray of length 2 or more works. The algorithm handles this because every remainder is 0, and the seed at -1 ensures the first check at index 1 succeeds.
• All zeros. nums = [0, 0, 0] with any k. Every prefix sum is 0, every remainder is 0. The seed matches at index 1 with a gap of 2.
• Large values of k. If k is larger than the total sum of the array, remainders might still repeat. The algorithm does not assume anything about the relative sizes of k and the elements.
• Negative numbers. Python's modulo operator always returns a non-negative result for a positive divisor, so (-5) % 6 = 1 in Python. In other languages, you may need to handle negative remainders by adding k and taking modulo again.
• Single element array. No valid subarray exists (minimum length is 2). The loop finishes without finding a match, and we return False.

From understanding to recall

Continuous Subarray Sum teaches you to combine two fundamental techniques: prefix sums and modular arithmetic. The trick is not complicated once you see it, but it is the kind of insight that fades from memory if you only encounter it once. In an interview, you need to produce the connection between "same remainder means divisible difference" without anyone hinting at it.

Spaced repetition helps you lock in that connection. By revisiting this problem at increasing intervals, you train yourself to recognize when a problem is asking about divisibility of subarray sums. After a few review cycles, the modular prefix sum pattern becomes automatic. You see "subarray sum divisible by k" and your hands are already writing the hash map setup before your conscious mind catches up.

Related posts

• Two Sum - The foundational hash map lookup pattern that this problem builds on
• Range Sum Query - Immutable - The prefix sum technique in its purest form
• Product of Array Except Self - Another problem that uses prefix and suffix computations over arrays

The prefix sum plus hash map combination is one of the highest-leverage patterns you can learn. Master it here, and you will keep reaching for it across dozens of other problems.