Continuous Subarray Sum

Med

#0508Time: O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic time complexity. For each pair of `(i, j)`, we do a constant number of operations.Space: O(1). We only use a few variables to store the indices and the current sum, so the space used is constant.1 company

Patterns

Math Prefix Sum

Data structures

Array Hash Table

Companies

Yandex

Prompt

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

its length is at least two, and
the sum of the elements of the subarray is a multiple of k.

Note that:

A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

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

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible continuous subarray that has a length of at least two. We use two nested loops to define the start and end of each subarray. The outer loop selects the starting element, and the inner loop extends the subarray to the right. For each subarray, we calculate its sum and check if it's a multiple of k. To avoid re-calculating the sum from scratch for each subarray, we can maintain a running sum within the inner loop.

Algorithm

Iterate through the array with a starting index i from 0 to nums.length - 1.
For each i, initialize a currentSum with nums[i].
Start an inner loop with index j from i + 1 to nums.length - 1. This ensures the subarray has at least two elements.
In the inner loop, add nums[j] to currentSum.
Check if currentSum is a multiple of k. This is true if currentSum % k == 0.
If the condition is met, we have found a "good subarray" and can immediately return true.
If the loops complete without finding any such subarray, it means no "good subarray" exists, and we return false.

Walkthrough

We iterate through the array with a starting index i from 0 to nums.length - 1. For each i, we then start an inner loop with index j from i + 1 to nums.length - 1. This ensures the subarray has at least two elements. Inside the inner loop, we maintain a currentSum for the subarray nums[i...j]. We check if this currentSum is a multiple of k. If k is not zero and currentSum % k == 0, we have found a valid subarray and can immediately return true. If the loops complete without finding any such subarray, it means no "good subarray" exists, and we return false.

1public class Solution {2    public boolean checkSubarraySum(int[] nums, int k) {3        for (int i = 0; i < nums.length; i++) {4            int currentSum = 0;5            for (int j = i; j < nums.length; j++) {6                currentSum += nums[j];7                if (j - i + 1 >= 2) { // Check if length is at least 28                    if (currentSum % k == 0) {9                        return true;10                    }11                }12            }13        }14        return false;15    }16}

Complexity

Time

O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic time complexity. For each pair of `(i, j)`, we do a constant number of operations.

Space

O(1). We only use a few variables to store the indices and the current sum, so the space used is constant.

Trade-offs

Pros

It's simple to understand and implement.
It uses constant extra space.

Cons

This approach is too slow for large input arrays and will likely result in a 'Time Limit Exceeded' error on most coding platforms.

A more efficient approach uses the properties of modular arithmetic combined with prefix sums. The core idea is that if the sum of a subarray nums[i..j] is a multiple of k, then (prefixSum[j] - prefixSum[i-1]) % k == 0. This is equivalent to prefixSum[j] % k == prefixSum[i-1] % k. This means we are looking for two indices, p and q, such that the prefix sums up to these indices have the same remainder when divided by k. We can iterate through the array, calculate the running prefix sum, and use a HashMap to store the first index at which a particular remainder is seen.

Algorithm

Initialize a HashMap<Integer, Integer> named map to store (remainder, index).
Add an initial entry map.put(0, -1) to handle subarrays that start at index 0.
Initialize an integer runningSum = 0.
Iterate through the nums array with index i from 0 to n-1.
Update runningSum by adding nums[i].
Calculate remainder = runningSum % k.
Check if map contains the key remainder.
If it does, get the previous index prevIndex = map.get(remainder). If i - prevIndex >= 2, a valid subarray is found, so return true.
If map does not contain the key remainder, add the new pair to the map: map.put(remainder, i).
If the loop completes, return false.

Walkthrough

We use a HashMap to store the remainders of prefix sums modulo k and the index where that remainder was first encountered. We initialize the HashMap with a key-value pair (0, -1). This is a crucial step to handle cases where the subarray starts from index 0. A prefix sum sum(0, i) being a multiple of k means (sum(0, i) - 0) % k == 0. The 0 sum corresponds to a prefix before the array starts, which we can imagine at index -1.

We iterate through the array from i = 0 to n-1, maintaining a runningSum. In each iteration, we add nums[i] to runningSum and calculate the remainder = runningSum % k. We then check if this remainder already exists as a key in our HashMap. If it does, it means we have found two prefix sums (at the current index i and a previous index map.get(remainder)) that have the same remainder. The sum of the elements between these two indices is a multiple of k. Let the previous index be prevIndex. The subarray is from prevIndex + 1 to i, and its length is i - prevIndex. We must ensure the length is at least 2, so we check if i - prevIndex >= 2. If it is, we return true. If the remainder does not exist in the HashMap, we add it along with the current index i. We only add it if it's not present because we want the earliest index for a given remainder to maximize the length i - prevIndex.

1import java.util.HashMap;2import java.util.Map;3 4public class Solution {5    public boolean checkSubarraySum(int[] nums, int k) {6        // map: remainder -> first index7        Map<Integer, Integer> map = new HashMap<>();8        map.put(0, -1); // To handle subarrays starting from index 09        int runningSum = 0;10 11        for (int i = 0; i < nums.length; i++) {12            runningSum += nums[i];13            int remainder = runningSum % k;14 15            if (map.containsKey(remainder)) {16                int prevIndex = map.get(remainder);17                // Check if the subarray has at least length 218                if (i - prevIndex >= 2) {19                    return true;20                }21            } else {22                // Store the first time this remainder is seen23                map.put(remainder, i);24            }25        }26        return false;27    }28}

Complexity

Time

O(n), where n is the length of `nums`. We iterate through the array only once. The HashMap operations (insertion and lookup) take, on average, O(1) time.

Space

O(min(n, k)). In the worst case, the HashMap might store up to `n` entries if all prefix sum remainders are unique. However, there are only `k` possible remainders when dividing by `k`, so the space complexity is bounded by `k`.

Trade-offs

Pros

Highly efficient with linear time complexity.
Passes for large inputs where brute-force would fail.

Cons

Requires extra space for the HashMap.
The logic involving modular arithmetic and the initial (0, -1) entry can be less intuitive at first glance.

Solutions

Solution

1class Solution {2public3  boolean checkSubarraySum(int[] nums, int k) {4    Map<Integer, Integer> mp = new HashMap<>();5    mp.put(0, -1);6    int s = 0;7    for (int i = 0; i < nums.length; ++i) {8      s += nums[i];9      int r = s % k;10      if (mp.containsKey(r) && i - mp.get(r) >= 2) {11        return true;12      }13      if (!mp.containsKey(r)) {14        mp.put(r, i);15      }16    }17    return false;18  }19}

1class Solution {2public:3  bool checkSubarraySum(vector<int> &nums, int k) {4    unordered_map<int, int> mp;5    mp[0] = -1;6    int s = 0;7    for (int i = 0; i < nums.size(); ++i) {8      s += nums[i];9      int r = s % k;10      if (mp.count(r) && i - mp[r] >= 2)11        return true;12      if (!mp.count(r))13        mp[r] = i;14    }15    return false;16  }17};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem