# Continuous Subarray Sum **Difficulty:** MEDIUM [External](https://leetcode.com/problems/continuous-subarray-sum) Canonical: https://scaleengineer.com/dsa/problems/continuous-subarray-sum **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array, Hash Table **Companies:** [Yandex](https://scaleengineer.com/companies/yandex) --- ## Problem 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 <= 105` * `0 <= nums[i] <= 109` * `0 <= sum(nums[i]) <= 231 - 1` * `1 <= k <= 231 - 1` # Approaches ## Brute Force 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. **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. **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. ### Explanation 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`. ```java public class Solution { public boolean checkSubarraySum(int[] nums, int k) { for (int i = 0; i < nums.length; i++) { int currentSum = 0; for (int j = i; j < nums.length; j++) { currentSum += nums[j]; if (j - i + 1 >= 2) { // Check if length is at least 2 if (currentSum % k == 0) { return true; } } } } return false; } } ``` ### 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`. ## Prefix Sum and HashMap 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. **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`. **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. ### Explanation 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`. ```java import java.util.HashMap; import java.util.Map; public class Solution { public boolean checkSubarraySum(int[] nums, int k) { // map: remainder -> first index Map map = new HashMap<>(); map.put(0, -1); // To handle subarrays starting from index 0 int runningSum = 0; for (int i = 0; i < nums.length; i++) { runningSum += nums[i]; int remainder = runningSum % k; if (map.containsKey(remainder)) { int prevIndex = map.get(remainder); // Check if the subarray has at least length 2 if (i - prevIndex >= 2) { return true; } } else { // Store the first time this remainder is seen map.put(remainder, i); } } return false; } } ``` ### Algorithm - Initialize a `HashMap` 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`. # Solutions ### Java ```java class Solution { public boolean checkSubarraySum(int[] nums, int k) { Map mp = new HashMap<>(); mp.put(0, -1); int s = 0; for (int i = 0; i < nums.length; ++i) { s += nums[i]; int r = s % k; if (mp.containsKey(r) && i - mp.get(r) >= 2) { return true; } if (!mp.containsKey(r)) { mp.put(r, i); } } return false; } } ``` ### CPP ```cpp class Solution { public: bool checkSubarraySum(vector &nums, int k) { unordered_map mp; mp[0] = -1; int s = 0; for (int i = 0; i < nums.size(); ++i) { s += nums[i]; int r = s % k; if (mp.count(r) && i - mp[r] >= 2) return true; if (!mp.count(r)) mp[r] = i; } return false; } }; ``` ### Python ```python class Solution: 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 ```