Continuous Subarray Sum

How it works

The key insight is based on modular arithmetic. If the prefix sum up to index i has remainder r when divided by k, and the prefix sum up to index j also has remainder r, then the subarray from i+1 to j has a sum that is a multiple of k. This is because (prefixSum[j] - prefixSum[i]) % k = 0 when both have the same remainder. We use a hash map to store the first index where each remainder was seen.

Steps

1. Create a hash map to store remainder values and their first occurrence index. Initialize it with {0: -1} to handle cases where the prefix sum itself is divisible by k.
2. Maintain a running total as we iterate through the array.
3. For each element, add it to the total and compute the remainder (total % k).
4. If this remainder exists in the map and the subarray length is at least 2 (current index minus stored index > 1), return true.
5. If the remainder is not in the map, store it with the current index.
6. Return false if no valid subarray is found.

Complexity

• Time complexity: O(n)
• Space complexity: O(k)

Where n is the size of the array nums and k is the number that a subarray sum needs to be multiple of.

Things to watch for

Forgetting to Initialize Hash Map with {0: -1}

The hash map must be initialized with remainder 0 at index -1 to handle cases where the prefix sum itself (from index 0 to current) is divisible by k. Without this, you miss valid subarrays that start from index 0.

Not Enforcing Minimum Subarray Length of 2

The problem requires the subarray to have at least 2 elements. A common mistake is checking i - remainder[r] >= 1 instead of > 1, which would accept single-element subarrays.

Updating the Hash Map When Remainder Already Exists

When the same remainder is seen again, you should NOT update its index. We need the earliest index for each remainder to maximize the subarray length and correctly detect valid subarrays. Updating would shrink the window and potentially miss valid answers.

from typing import List

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        remainder = {0: -1}  # remainder -> end index
        total = 0

        for i, num in enumerate(nums):
            total += num
            r = total % k
            if r not in remainder:
                remainder[r] = i
            elif i - remainder[r] > 1:
                return True

        return False

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> remainder;
        remainder[0] = -1;
        int total = 0;

        for (int i = 0; i < nums.size(); i++) {
            total += nums[i];
            int r = total % k;
            if (remainder.find(r) == remainder.end()) {
                remainder[r] = i;
            } else if (i - remainder[r] > 1) {
                return true;
            }
        }

        return false;
    }
};