Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Continuous Subarray Sum

Try it yourself
MediumProblemExternal link

Description

You get an array of non-negative integers nums and an integer k.

Return true if nums has a contiguous subarray of at least two values whose sum is a multiple of k, and false otherwise. A sum of 0 counts: 0 is a multiple of every k.

Examples

Example 1

Input: nums = [23, 2, 4, 6, 7], k = 6

Output: true

Explanation: [2, 4] adds up to 6, a multiple of 6, and has two values.

Example 2

Input: nums = [23, 2, 6, 4, 7], k = 6

Output: true

Explanation: The whole array adds up to 42, which is 7 times 6.

Example 3

Input: nums = [23, 2, 6, 4, 7], k = 13

Output: false

Explanation: No subarray of two or more values adds up to a multiple of 13.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • 0 ≤ nums[i] ≤ 10^9
  • 0 ≤ sum(nums) ≤ 2^31 - 1
  • 1 ≤ k ≤ 2^31 - 1

Editorial

Brute Force

Intuition

Try every start, extend it one value at a time from the second value on, and test each sum. Stop at the first one that is a multiple of k.

Step-by-Step Explanation

For nums = [23, 2, 6, 4, 7] and k = 6:

  1. Start at index 0 and extend one value at a time, testing every sum of two or more values against 6.
  2. nums[0..1] adds up to 25, not a multiple of 6.
  3. nums[0..2] adds up to 31, not a multiple of 6.
  4. nums[0..3] adds up to 35, not a multiple of 6.
  5. nums[0..4] adds up to 42, which is 7 times 6. The answer is true.

Test Every Subarray — The shaded cells are the subarray being tested; green marks the one whose sum is a multiple of k.

Algorithm

  1. For each start s, set a running sum to nums[s].
  2. For each end e after s: add nums[e]; if the sum is a multiple of k, return true.
  3. Return false.

Code

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        for (int s = 0; s < n; s++) {
            long long total = nums[s];
            for (int e = s + 1; e < n; e++) {   // every subarray of two or more values from s
                total += nums[e];
                if (total % k == 0) return true;
            }
        }
        return false;
    }
};

class Solution:
    def checkSubarraySum(self, nums: list[int], k: int) -> bool:
        n = len(nums)
        for s in range(n):
            total = nums[s]
            for e in range(s + 1, n):           # every subarray of two or more values from s
                total += nums[e]
                if total % k == 0:
                    return True
        return False

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        for (int s = 0; s < n; s++) {
            long total = nums[s];
            for (int e = s + 1; e < n; e++) {   // every subarray of two or more values from s
                total += nums[e];
                if (total % k == 0) return true;
            }
        }
        return false;
    }
}

var checkSubarraySum = function(nums, k) {
    const n = nums.length;
    for (let s = 0; s < n; s++) {
        let total = nums[s];
        for (let e = s + 1; e < n; e++) {       // every subarray of two or more values from s
            total += nums[e];
            if (total % k === 0) return true;
        }
    }
    return false;
};

Complexity Analysis

Time Complexity: O(n²)

When the answer is false, every subarray gets tested.

Space Complexity: O(1)

Why This Approach Is Not Efficient

With 10^5 values and no answer, that's about 5 · 10^9 sums (over the time limit in cpp and Python and java and javascript).

A subarray's sum is the difference of two running totals, and that difference is a multiple of k exactly when the two totals leave the same remainder mod k. So look for a remainder that comes back.

Optimal Approach - First Index of Each Remainder

Intuition

Walk once, keeping the running total's remainder mod k. If the same remainder showed up at an earlier index j, then nums[j + 1..i] adds up to a multiple of k. It has i − j values, so it counts when i − j ≥ 2.

Keep the first index of each remainder and never move it: the earliest j gives the longest subarray, so if any match is long enough, the first one is. And start the map with remainder 0 at index −1, the point before any value, so a subarray that starts at index 0 is found too.

Step-by-Step Explanation

For nums = [23, 2, 6, 4, 7] and k = 6:

  1. The map holds the first index where each remainder mod 6 appeared. Remainder 0 starts at index −1, the point before any value.
  2. Add 23, and the remainder is 5. It's new, so the map records index 0.
  3. Add 2, and the remainder is 1. It's new, so the map records index 1.
  4. Add 6, and the remainder is 1 again, but only 1 value after index 1: a single value doesn't count. Keep index 1, since a later match is longer from there.
  5. Add 4, and the remainder is 5 again. It first appeared at index 0, 3 values back, so nums[1..3] adds up to a multiple of 6. The answer is true.

A Remainder Comes Back — Top: nums and the running total's remainder after each value. Bottom: the first index of each remainder.

Algorithm

  1. first = {0: -1}, r = 0.
  2. For each index i: r = (r + nums[i]) mod k.
    • If r is in first and i − first[r] ≥ 2, return true.
    • If r isn't in first, record first[r] = i.
  3. Return false.

Every value is at least 0, so r + nums[i] is never more than the running total, which fits in a 32-bit int here.

Code

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> first;          // remainder -> the first index that reached it
        first[0] = -1;
        int r = 0;                              // r + nums[i] is at most the running total: fits an int
        for (int i = 0; i < (int)nums.size(); i++) {
            r = (r + nums[i]) % k;
            auto it = first.find(r);
            if (it != first.end()) {
                if (i - it->second >= 2) return true;   // at least two values between the two totals
            } else {
                first[r] = i;                   // keep the first: never move it later
            }
        }
        return false;
    }
};

class Solution:
    def checkSubarraySum(self, nums: list[int], k: int) -> bool:
        first = {0: -1}                         # remainder -> the first index that reached it
        r = 0
        for i, x in enumerate(nums):
            r = (r + x) % k
            if r in first:
                if i - first[r] >= 2:           # at least two values between the two totals
                    return True
            else:
                first[r] = i                    # keep the first: never move it later
        return False

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> first = new HashMap<>();  // remainder -> the first index that reached it
        first.put(0, -1);
        int r = 0;                              // r + nums[i] is at most the running total: fits an int
        for (int i = 0; i < nums.length; i++) {
            r = (r + nums[i]) % k;
            Integer at = first.get(r);
            if (at != null) {
                if (i - at >= 2) return true;   // at least two values between the two totals
            } else {
                first.put(r, i);                // keep the first: never move it later
            }
        }
        return false;
    }
}

var checkSubarraySum = function(nums, k) {
    const first = new Map([[0, -1]]);           // remainder -> the first index that reached it
    let r = 0;
    for (let i = 0; i < nums.length; i++) {
        r = (r + nums[i]) % k;                  // never negative here: every value is at least 0
        if (first.has(r)) {
            if (i - first.get(r) >= 2) return true;     // at least two values between the two totals
        } else {
            first.set(r, i);                    // keep the first: never move it later
        }
    }
    return false;
};

Complexity Analysis

Time Complexity: O(n)

One pass, one lookup per value.

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

At most one entry per different remainder.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Moving the first index. first[r] = i # on every step

On nums = [1, 0, 0], k = 2, it returns false; the answer is true. When a remainder comes back only one value later, that pair is too short, but the first index is still the best start for later. Overwriting it with the newer index shrinks every later distance by one: on [1, 0, 0] with k = 2 the remainder 1 sits at indexes 0, 1 and 2, and moving it to 1 leaves the pair [0, 0] looking too short.

Starting with an empty map. first = {}

On nums = [2, 4], k = 6, it returns false; the answer is true. A subarray that starts at index 0 pairs with the running total before any value, which is 0. Without {0: -1} in the map it's never found: [2, 4] with k = 6 adds up to 6, yet the answer comes out false.

Letting one value count. if i - first[r] >= 1:

On nums = [6, 1], k = 6, it returns true; the answer is false. The subarray needs at least two values. Checking i - first[r] >= 1 lets one value that is itself a multiple of k count: on [6, 1] with k = 6 it says true, but [6, 1] adds up to 7.

Checking only pairs of neighbours. if (nums[i] + nums[i + 1]) % k == 0:

On nums = [4, 1, 1, 3], k = 9, it returns false; the answer is true. Two neighbours are the shortest allowed subarray, not the only one. [4, 1, 1, 3] with k = 9 has no pair of neighbours adding to a multiple of 9, but all four values add up to 9.

Where This Pattern Is Taught

This problem practises running totals and a hash map, with remainders and a first index. It's taught in Prefix Sums with a Hash Map.