Continuous Subarray Sum — Prefix Modulo and Remainder Collisions

Problem Statement#

Given an integer array nums and an integer k, return true if nums has a good subarray of length at least two whose sum is a multiple of k, or false otherwise. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= sum(nums[i]) <= 2^31 - 1
• 1 <= k <= 2^31 - 1

Example 1:
Input:  nums = [23, 2, 4, 6, 7], k = 6
Output: true
Explanation: [2, 4] is a subarray of length 2 whose sum is 6, a multiple of 6.

Example 2:
Input:  nums = [23, 2, 6, 4, 7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] sums to 42 = 7 × 6.

Example 3:
Input:  nums = [23, 2, 6, 4, 7], k = 13
Output: false
Explanation: No subarray of length >= 2 sums to a multiple of 13.

Why This Problem Matters#

Continuous Subarray Sum is the modular arithmetic cousin of Subarray Sum Equals K. While that problem asks for exact sum equality, this one asks for sum divisibility — a harder condition to reason about without the right mathematical insight. Google frequently uses this problem in phone screens because the modular prefix sum trick is non-obvious and reveals genuine number-theoretic understanding.

The key theorem underlying the solution — that (prefix[j] - prefix[i]) % k == 0 if and only if prefix[j] % k == prefix[i] % k — is a direct application of modular arithmetic. Candidates who know this theorem immediately recognize the right data structure (a map from remainder to first occurrence index). Candidates who do not know it will likely attempt a brute-force O(n^2) scan or incorrectly attempt a sliding window.

This problem is also important because it introduces the concept of "remainder collision detection" — the idea that two positions with the same prefix sum remainder define a valid subarray. This same concept appears in Subarray Sums Divisible by K (LC 974, which counts instead of just detecting), and in several graph and dynamic programming problems involving cyclic patterns.

The length constraint (subarray must have length at least 2) adds a subtle implementation challenge: you must store the first occurrence index of each remainder and verify that the current index is at least 2 positions after the stored index. This is the same challenge as Contains Duplicate II — storing first seen position and checking minimum distance.

The Core Insight#

The modular prefix sum theorem: If prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0, meaning the subarray from index i+1 to j sums to a multiple of k.

This is because: (prefix[j] - prefix[i]) % k == (prefix[j] % k - prefix[i] % k) % k == 0 when the two remainders are equal.

So instead of tracking prefix sums themselves, track their remainders modulo k. Use a HashMap from remainder to its first occurrence index. For each position j:

1. Compute remainder = prefix[j] % k.
2. If remainder was seen at index i, and j - i >= 2, return true.
3. If remainder was not seen, store remainder → j (first occurrence only).

Why store first occurrence only? The earlier the first occurrence, the larger the potential subarray. Storing only the first occurrence maximizes the chance of satisfying the length-2 constraint.

Initialization: Store {0: -1} — the "empty prefix" has remainder 0 and conceptually sits at index -1. This handles subarrays starting at index 0: if prefix[j] % k == 0, then j - (-1) = j + 1 >= 2 whenever j >= 1.

Visual Dry Run#

Input: nums = [23, 2, 4, 6, 7], k = 6

The subarray nums[1..2] = [2, 4] has sum 6, which is 1 × 6.

Input: nums = [23, 2, 6, 4, 7], k = 13

No remainder collision → return false.

Solution (Optimal)#

def checkSubarraySum(nums: list[int], k: int) -> bool:
    # Map from (prefix_sum % k) to first occurrence index
    # {0: -1} handles subarrays starting at index 0
    first_occurrence = {0: -1}
    prefix = 0
 
    for i, num in enumerate(nums):
        prefix += num
        remainder = prefix % k
 
        if remainder in first_occurrence:
            # Check that the subarray length is at least 2
            if i - first_occurrence[remainder] >= 2:
                return True
            # Do NOT update: keep the first (earliest) occurrence
        else:
            # Store first occurrence only
            first_occurrence[remainder] = i
 
    return False

var checkSubarraySum = function(nums, k) {
    // Map from (prefix % k) to first occurrence index
    const firstOccurrence = new Map([[0, -1]]);
    let prefix = 0;
 
    for (let i = 0; i < nums.length; i++) {
        prefix += nums[i];
        const remainder = prefix % k;
 
        if (firstOccurrence.has(remainder)) {
            // Subarray length must be at least 2
            if (i - firstOccurrence.get(remainder) >= 2) {
                return true;
            }
            // Keep first occurrence — do not overwrite
        } else {
            firstOccurrence.set(remainder, i);
        }
    }
 
    return false;
};

Complexity Analysis

The space is O(k) because there are at most k distinct remainders (0 through k-1). For large k, this is effectively O(n) since the number of distinct remainders cannot exceed n (you only have n prefix sums).

Common Mistakes#

• Updating the map for every occurrence instead of only the first. If you overwrite the stored index with the current index, you lose the ability to form long subarrays. Always keep the first occurrence.
• Forgetting the length constraint. Two consecutive elements can satisfy the remainder condition but form a length-1 "subarray" at a single index. The check i - first_occurrence[remainder] >= 2 enforces length ≥ 2.
• Initializing the map with {0: 0} instead of {0: -1}. The empty prefix is conceptually at index -1. If you start at 0, a subarray from index 0 to index 1 would give distance = 1 - 0 = 1, which is less than 2, incorrectly failing.
• Confusing this problem with Subarray Sum Equals K. That problem counts occurrences (so storing all occurrences is correct). This problem only needs to know whether any valid subarray exists, and uses first occurrence for the length constraint.
• Handling k == 1 incorrectly. Every integer is a multiple of 1, so any subarray of length ≥ 2 is a valid answer. The algorithm handles this correctly: remainder % 1 == 0 always, and {0: -1} is initialized, so i - (-1) = i + 1 >= 2 for any i >= 1.

Follow-up Questions#

What if you want the count of subarrays summing to a multiple of k (LC 974)? Instead of tracking first occurrence, count all occurrences of each remainder (like Subarray Sum Equals K). For each position j, add count[prefix[j] % k] to the answer. Initialize count[0] = 1.

What if the subarray length constraint is different (e.g., length >= m)? Change the check to i - first_occurrence[remainder] >= m. Everything else stays the same.

What if k can be 0? The problem constrains k >= 1. If k were 0, the problem would ask for subarrays summing to a multiple of 0, which is undefined (division by zero). Handle this edge case by returning false immediately or treating it as "sum == 0."

How does modular arithmetic make the HashMap key space bounded? Without modular reduction, prefix sums can grow unboundedly (up to 10^14 for this problem). The remainder is always in [0, k-1], so the HashMap has at most k entries. This is a significant memory optimization when k is small.

How would you find the actual subarray (not just detect existence)? Store (first occurrence index, current index) when a remainder collision is found. The subarray is nums[first_index + 1 .. current_index].

Key Takeaways#

• LC 523 Continuous Subarray Sum uses prefix-sum modulo K as the HashMap key — the modular twin of LC 560.
• If two prefix sums share the same % k remainder and are at least 2 apart, the subarray between them sums to a multiple of k.
• Seed the map with {0: -1} so a prefix that itself is divisible by k produces a length >= 2 subarray.
• Always store the FIRST occurrence index of each remainder; later collisions just need to check the gap.
• Time and space are O(n); avoids the O(n^2) brute force trap interviewers watch for.
• Edge case: when k is 0, fall back to checking adjacent zeros — modular logic does not apply.
• This modular prefix-sum trick generalizes to LC 974 (count divisible), LC 1590 (make sum divisible), and LC 1010 (pair-sum modular).

Related Problems#

• LC 523 — Continuous Subarray Sum: This problem.
• LC 974 — Subarray Sums Divisible by K: Count subarrays whose sum is divisible by k — same technique, count instead of detect.
• LC 560 — Subarray Sum Equals K: Exact sum version — stores occurrence counts instead of first index.
• LC 1590 — Make Sum Divisible by P (Premium): Find the shortest subarray to remove to make the whole array sum divisible by p.
• LC 325 — Maximum Size Subarray Sum Equals k (Premium): Longest subarray with exact sum — stores first occurrence of each prefix sum.
• LC 1010 — Pairs of Songs With Total Durations Divisible by 60: Pair-counting problem with the same modular arithmetic insight.