Back to solutions

Continuous Subarray Sum

MediumArrays

Check for a length-2+ subarray whose sum is a multiple of k.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 1 <= k <= 2^31 - 1
  • 0 <= nums[i] <= 10^9

Prefix remainder map

Time O(n)Space O(min(n, k))

Two prefix sums with the same remainder modulo k bound a subarray whose sum is a multiple of k. Track the earliest index for each remainder; if the same remainder reappears at least two indices later, a valid subarray exists. Seed remainder 0 at index -1 to catch prefixes that are themselves multiples.

Key terms
prefix sum remainder:
The running total modulo k; equal remainders mean the gap between them is divisible by k.
earliest index:
Storing the first time a remainder is seen so the gap (subarray length) is maximised.
bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> seen; seen[0] = -1;
    long long sum = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        sum += nums[i];
        int r = (int)(sum % k);
        if (seen.count(r)) { if (i - seen[r] >= 2) return true; }
        else seen[r] = i;
    }
    return false;
}
Step by step
  1. Initialise a map with remainder 0 at index -1 and a running sum 0.
  2. For each index, add nums[i] and compute r = sum mod k.
  3. If r was seen before at index j and i - j >= 2, return true.
  4. Otherwise record the earliest index for r. Return false if no pair qualifies.