Continuous Subarray Sum

Medium Arrays & Hashing Prefix Sum Strategy Original on LeetCode

Continuous Subarray Sum is a medium arrays & hashing problem solved with the prefix sum strategy pattern. The best approach, optimal (prefix remainders in a hash map), runs in O(n) time and O(min(n, k)) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (all subarrays with prefix sums) up.

Problem

Given an integer array nums and an integer k, return true if some contiguous subarray of length at least 2 has a sum that is a multiple of k, and false otherwise.

A number x is a multiple of k when x = n · k for some integer n; in particular 0 is a multiple of every k.

Examples

Example 1

Input: nums = [4, 1, 6, 3], k = 5
Output: true
Why: The first two numbers add up to 5, which is a multiple of 5.

Example 2

Input: nums = [2, 5, 8], k = 4
Output: false
Why: The subarrays of length at least 2 sum to 7, 13 and 15, and none of them divides evenly by 4.

Example 3

Input: nums = [0, 0], k = 9
Output: true
Why: 0 counts as a multiple of every k, and [0, 0] has length 2.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (all subarrays with prefix sums)	`O(n²)`	`O(n)`
Optimal (prefix remainders in a hash map)	`O(n)`	`O(min(n, k))`

1Brute force (all subarrays with prefix sums)

TimeO(n²)There are about n² / 2 boundary pairs, each checked in O(1).

SpaceO(n)The prefix-sum array.

Build prefix sums so any subarray sum costs O(1), then check every pair of boundaries that are at least two elements apart.

prefix[0] = 0, prefix[i + 1] = prefix[i] + nums[i] (64-bit).
For every i < j with j - i >= 2, test (prefix[j] - prefix[i]) % k == 0.
Return true on the first hit, false at the end.

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        for (int i = 0; i < n; i++)
            for (int j = i + 2; j <= n; j++)
                if ((prefix[j] - prefix[i]) % k == 0) return true;
        return false;
    }
}

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, x in enumerate(nums):
            prefix[i + 1] = prefix[i] + x
        for i in range(n):
            for j in range(i + 2, n + 1):
                if (prefix[j] - prefix[i]) % k == 0:
                    return True
        return False

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        for (int i = 0; i < n; i++)
            for (int j = i + 2; j <= n; j++)
                if ((prefix[j] - prefix[i]) % k == 0) return true;
        return false;
    }
};

function checkSubarraySum(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    for (let i = 0; i < n; i++)
        for (let j = i + 2; j <= n; j++)
            if ((prefix[j] - prefix[i]) % k === 0) return true;
    return false;
}

2Optimal (prefix remainders in a hash map)

TimeO(n)One pass with O(1) average map operations.

SpaceO(min(n, k))The map holds at most one entry per distinct remainder, and there are at most min(n + 1, k) of them.

Walk the array keeping the running sum modulo k. Two prefixes with the same remainder enclose a subarray whose sum is a multiple of k. Store only the first index of each remainder (seeded with remainder 0 at index -1), so the gap is as long as possible; succeed when the gap is at least 2.

first = {0: -1}, rem = 0.
For each i: rem = (rem + nums[i]) % k.
If rem is in first and i - first[rem] >= 2, return true.
If rem is not in first, store first[rem] = i.
Return false.

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

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

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

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

Edge cases to test

A single element, even one divisible by k (answer false)
Two adjacent zeros (always true)
k = 1 with at least two elements (always true)
Sums that overflow a 32-bit integer

Hints

Hint 1

The sum of nums[i..j] is prefix[j + 1] - prefix[i]. When is that difference a multiple of k?

Hint 2

Exactly when the two prefix sums leave the same remainder modulo k.

Hint 3

Remember the earliest index where each remainder appeared; you need two positions at least 2 apart.

FAQ

What is the best time complexity for Continuous Subarray Sum?

Optimal (prefix remainders in a hash map) runs in O(n) time and O(min(n, k)) extra space. One pass with O(1) average map operations.

Which pattern does Continuous Subarray Sum use?

It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.

Is there a brute force solution for Continuous Subarray Sum?

Yes. Brute force (all subarrays with prefix sums) takes O(n²) time and O(n) space. Build prefix sums so any subarray sum costs O(1), then check every pair of boundaries that are at least two elements apart.

Which edge cases should I test for Continuous Subarray Sum?

A single element, even one divisible by k (answer false); Two adjacent zeros (always true); k = 1 with at least two elements (always true); Sums that overflow a 32-bit integer.