Continuous Subarray Sum (LeetCode 523)

The problem

Given an array of non-negative integers nums and an integer k, return True if there is a contiguous subarray of length at least 2 whose sum is a multiple of k (0 counts as a multiple). Otherwise return False.

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

The subarray [2, 4] sums to 6, a multiple of 6, and has length 2.

How to think about it

Start with brute force. Check every subarray of length 2 or more with a running sum: O(n²). With n up to 10⁵ that is too slow.

The key insight: same remainder means divisible difference. The sum of nums[a+1..b] is pre[b] - pre[a], and that is a multiple of k exactly when both prefix sums have the same remainder mod k. So as you walk, compute r = s % k and ask “have I seen this remainder before?”

The length rule decides what to store. A repeat at indices a and b gives a subarray of length b - a. You need b - a >= 2, and the earlier a is, the more likely that holds. So store the first index of each remainder and never overwrite it. Seed with {0: -1} so a prefix that is itself a multiple of k (starting at index 0) counts.

Which pattern is this? Prefix sums plus a hash map. The tell is “subarray sum divisible by / multiple of k”. It is the remainder trick from Subarray Sums Divisible by K, with a first-index map instead of a count map because of the length condition.

Approach

1. Set rem = {0: -1} and s = 0.
2. For each index i and value x, add x to s and compute r = s % k.
3. If r is in rem and i - rem[r] >= 2, return True.
4. If r is not in rem, store rem[r] = i. If it is there but too close, keep the older index.
5. After the loop, return False.

Solution

def check_subarray_sum(nums, k):
    rem = {0: -1}; s = 0                       # remainder 0 seen before the array starts
    for i, x in enumerate(nums):
        s += x; r = s % k
        if r in rem:
            if i - rem[r] >= 2: return True    # same remainder, gap of 2+ elements
        else:
            rem[r] = i                         # store only the first index
    return False
# check_subarray_sum([23,2,4,6,7], 6) -> True

Dry run

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

The subarray found is indices 1 to 2, [2, 4].

Complexity

• Time: O(n). One pass with O(1) average map work per element.
• Space: O(min(n, k)). At most k distinct remainders, and at most one new key per element.

Edge cases and pitfalls

• A single element that is a multiple of k does not count: [6] with k = 6 returns False because the length is 1.
• Two zeros in a row ([0, 0]) return True for any k, since 0 is a multiple of every k.
• Overwriting the stored index is the classic bug: [5, 0, 0] with k = 3 needs the first index of remainder 2 to see the gap of 2.
• Using a count map (as in LeetCode 974) loses the index information you need for the length check.
• k = 0 would make s % k raise ZeroDivisionError. The constraints guarantee k >= 1, but say so out loud in an interview.

Related problems

• Subarray Sums Divisible by K (LeetCode 974): the same remainder idea, counting every divisible subarray.
• Contiguous Array (LeetCode 525): the same first-index map, on a ±1 running sum.
• Maximum Size Subarray Sum Equals k (LeetCode 325): first index of each prefix sum, for the longest match.