Continuous Subarray Sum — DSA · Engineering Playbook

Problem#

Given an integer array nums and integer k, return true if there exists a contiguous subarray of length at least 2 whose sum is a multiple of k.

Examples#

nums = [23,2,4,6,7], k = 6 → true ([2,4]).
nums = [23,2,6,4,7], k = 6 → true ([23,2,6,4,7] sums to 42).
nums = [1,2,3], k = 5 → false.

Constraints#

1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^9, 1 <= k <= 2^31 - 1.

Hints#

Hint

If two prefix sums share the same residue mod k, the subarray between them sums to a multiple of k.

Approach#

Compute running prefix-sum mod k. Store firstIndex[residue] (init firstIndex[0] = -1 so a prefix that itself is a multiple of k counts). When we see a residue again with i - firstIndex >= 2, we have our subarray.

Solution#

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> firstIdx;
        firstIdx[0] = -1;
        int prefix = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            prefix = (prefix + nums[i]) % k;
            auto it = firstIdx.find(prefix);
            if (it != firstIdx.end()) {
                if (i - it->second >= 2) return true;
            } else {
                firstIdx[prefix] = i;
            }
        }
        return false;
    }
};

func checkSubarraySum(nums []int, k int) bool {
    firstIdx := map[int]int{0: -1}
    prefix := 0
    for i, v := range nums {
        prefix = (prefix + v) % k
        if j, ok := firstIdx[prefix]; ok {
            if i-j >= 2 {
                return true
            }
        } else {
            firstIdx[prefix] = i
        }
    }
    return false
}

from typing import List

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        first_idx = {0: -1}
        prefix = 0
        for i, v in enumerate(nums):
            prefix = (prefix + v) % k
            if prefix in first_idx:
                if i - first_idx[prefix] >= 2:
                    return True
            else:
                first_idx[prefix] = i
        return False

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

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

function checkSubarraySum(nums: number[], k: number): boolean {
    const firstIdx = new Map<number, number>();
    firstIdx.set(0, -1);
    let prefix = 0;
    for (let i = 0; i < nums.length; i++) {
        prefix = (prefix + nums[i]) % k;
        const j = firstIdx.get(prefix);
        if (j !== undefined) {
            if (i - j >= 2) return true;
        } else {
            firstIdx.set(prefix, i);
        }
    }
    return false;
}

Editorial#

Two prefix sums P[i] and P[j] share the same residue mod k iff (P[j] - P[i]) % k == 0 — and that difference is the sum of nums[i+1..j]. Keeping the first occurrence maximizes the window length, helping the >= 2 check. Initializing firstIdx[0] = -1 correctly handles the case where the prefix from index 0 is itself a multiple of k.

Complexity#

Time: O(N).
Space: O(N).

Concept revision#

Contiguous Array

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#