Continuous Subarray Sum

medium array hash map prefix sum

Problem

Return true iff nums has a contiguous subarray of length ≥ 2 whose sum is a multiple of k.

Inputnums = [23,2,4,6,7], k = 6

Outputtrue

Prefix mod sees the same remainder twice ≥ 2 apart → subarray sum is divisible by k.

nums

def check_subarray_sum(nums, k):
    seen = {0: -1}
    s = 0
    for i, x in enumerate(nums):
        s = (s + x) % k
        if s in seen:
            if i - seen[s] >= 2: return True
        else:
            seen[s] = i
    return False

function checkSubarraySum(nums, k) {
  const seen = new Map([[0, -1]]);
  let s = 0;
  for (let i = 0; i < nums.length; i++) {
    s = (s + nums[i]) % k;
    if (seen.has(s)) { if (i - seen.get(s) >= 2) return true; }
    else seen.set(s, i);
  }
  return false;
}

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, -1);
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            s = (s + nums[i]) % k;
            if (seen.containsKey(s)) { if (i - seen.get(s) >= 2) return true; }
            else seen.put(s, i);
        }
        return false;
    }
}

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> seen{{0, -1}};
    int s = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        s = (s + nums[i]) % k;
        if (seen.count(s)) { if (i - seen[s] >= 2) return true; }
        else seen[s] = i;
    }
    return false;
}

Explanation

We need a subarray of length at least 2 whose sum is a multiple of k. The key insight: a subarray sum is divisible by k exactly when the running prefix sum has the same remainder mod k at both ends.

So we keep a running sum and immediately take it mod k into s. We store each remainder's first index in a map seen. If we hit a remainder we have seen before, the elements between those two points sum to a multiple of k.

The length rule is handled by the index check i - seen[s] >= 2: we only return true when the matching remainder is at least two positions back, guaranteeing a subarray of length 2 or more. We seed {0: -1} so a valid run starting at index 0 still satisfies the length check.

Example: nums = [23,2,4,6,7], k = 6. Prefix mods are 5,1,5,... — remainder 5 appears at index 0 and again at index 2, which are more than one apart, so [2,4] sums to 6 and we return true.

Storing only the first index of each remainder keeps the gap as large as possible, and the whole scan is one pass.

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