Continuous Subarray Sum
Problem Description:
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.
Examples:
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.
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is a 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.
Input: nums = [23,2,6,4,7], k = 13
Output: false
Explanation: No subarray of nums = [23, 2, 6, 4, 7] has a sum that is a multiple of k = 13
Constraints
1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1
Brute Force Approach
When we read the problem statement, the first idea that comes to mind is simple:
We need to check all possible subarrays of the given array and calculate their sums and determine if the sum is divisible by k, ensuring the subarray length is at least 2. If we find such a subarray, we return true immediately. If no subarray of length at least 2 has a sum divisible by k, we return false at the end.
How can we do it?
We can use a brute-force solution by traversing through the array.
- For each element in the array, calculate the sum of all subarrays starting from that element by adding subsequent elements one by one.
- While calculating the sum, check:If the sum is divisible by k, andIf the subarray length is at least 2.
- If both conditions are met, return true immediately.
- If no subarray of length at least 2 has a sum divisible by k, return false at the end.
Let's understand with an example:
Here’s a concise dry run for nums = [23, 2, 4, 6, 7], k = 6 using the brute force approach:
- Start with nums[0] = 23:
- Subarray [23, 2]: Sum = 25 → Not divisible by 6.
- Subarray [23, 2, 4]: Sum = 29 → Not divisible by 6.
- Subarray [23, 2, 4, 6]: Sum = 35 → Not divisible by 6.
- Subarray [23, 2, 4, 6, 7]: Sum = 42 → Divisible by 6, length ≥ 2 → Return true.
Since we found a valid subarray, the output is true, and we stop further calculations.
How to implement it in code:
- Get the size of the array and store it in n.
- Outer loop: Iterate through the array using i from 0 to n-1.
- Inner loop: For each i, iterate with j from i to n-1, calculating the sum of subarrays starting at i.
- Check conditions: If the sum of the subarray is divisible by k and the length of the subarray is at least 2, return true.
- Return false if no valid subarray is found after both loops.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
// Get the size of the input array
int n = nums.size();
// Iterate over each possible starting point of the subarray
for (int i = 0; i < n; i++) {
// Initialize current_sum to accumulate the sum of subarrays starting at index i
int current_sum = 0;
// Iterate through the array from index i to n
for (int j = i; j < n; j++) {
// Add the current element to the running sum
current_sum += nums[j];
// Check if the current sum is divisible by k and if the subarray length is at least 2
if (current_sum % k == 0 && j - i + 1 >= 2) {
// If conditions are met, return true
return true;
}
}
}
// If no valid subarray is found, return false
return false;
}
};
2. Java Try on Compiler
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
// Get the size of the input array
int n = nums.length;
// Iterate over each possible starting point of the subarray
for (int i = 0; i < n; i++) {
// Initialize current_sum to accumulate the sum of subarrays starting at index i
int current_sum = 0;
// Iterate through the array from index i to n
for (int j = i; j < n; j++) {
// Add the current element to the running sum
current_sum += nums[j];
// Check if the current sum is divisible by k and if the subarray length is at least 2
if (current_sum % k == 0 && j - i + 1 >= 2) {
// If conditions are met, return true
return true;
}
}
}
// If no valid subarray is found, return false
return false;
}
}
3. Python Try on Compiler
class Solution:
def checkSubarraySum(self, nums, k):
# Get the size of the input array
n = len(nums)
# Iterate over each possible starting point of the subarray
for i in range(n):
# Initialize current_sum to accumulate the sum of subarrays starting at index i
current_sum = 0
# Iterate through the array from index i to n
for j in range(i, n):
# Add the current element to the running sum
current_sum += nums[j]
# Check if the current sum is divisible by k and if the subarray length is at least 2
if current_sum % k == 0 and j - i + 1 >= 2:
# If conditions are met, return true
return True
# If no valid subarray is found, return false
return False
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var checkSubarraySum = function(nums, k) {
// Get the size of the input array
let n = nums.length;
// Iterate over each possible starting point of the subarray
for (let i = 0; i < n; i++) {
// Initialize current_sum to accumulate the sum of subarrays starting at index i
let current_sum = 0;
// Iterate through the array from index i to n
for (let j = i; j < n; j++) {
// Add the current element to the running sum
current_sum += nums[j];
// Check if the current sum is divisible by k and if the subarray length is at least 2
if (current_sum % k === 0 && j - i + 1 >= 2) {
// If conditions are met, return true
return true;
}
}
}
// If no valid subarray is found, return false
return false;
};Time Complexity: O(n²)
This approach runs two nested loops to find all subarrays, one inside another, where the outer loop runs n times
(i.e. i ranges from 0 to n), and for each iteration of the outer loop, the inner loop(i.e. j ranges from i to n) also runs n-i times.
Analyzing the Loops:
Outer Loop (indexed by i):
It runs from 0 to n-1. So, it iterates n times.
Inner Loop (indexed by j):
For each fixed i, j runs from i to n-1.
When i = 0, j runs n times.
When i = 1, j runs n-1 times.
When i = 2, j runs n-2 times.
…
When i = n-1, j runs 1 time.
Total Iterations:
To find the total number of iterations of the inner loop across all iterations of the outer loop,
we sum up the iterations for each value of i: ∑(i=0 to n−1) (n−i)
This is the sum of an arithmetic series: n+(n−1)+(n−2)+…+1.
If we closely observe and reverse the series
we get 1 + 2 + 3 + … + (n-2) + (n-1) + n.
That is nothing but the sum of n terms.
So the sum of n numbers from 1 to n is (n*(n+1))/2.
Thus, the total number of operations is (n*(n+1))/2.
Simplifying to Big-O Notation:
In Big-O notation, we focus on the term that grows the fastest as n increases, and we ignore constant factors and lower-order terms.
Therefore: O((n*(n+1))/2) ≈ O(n²)
Conclusion: The time complexity of the given code is O(n²).
This is because the nested loops result in a quadratic number of total operations, which dominate the runtime as the input size n becomes large.
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
The solution uses only a few variables (current_sum, loop counter) are used, which require O(1) space.
Total Space Complexity: O(n)
The input array nums is given, which requires O(n) space.
Adding this to the auxiliary space gives: Total Space = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the size of the array is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes, of course!
We can definitely optimize it—let's do it!
In the previous approach, we checked all possible subarrays, calculated their sums, and then checked if they were divisible by k and has a size of greater than or equal to 2. While it worked, it wasn't feasible because it gave us an O(n²) solution.
But don't worry—here’s how we can make it efficient!
Now, let’s analyze the drawbacks in our previous approach.
The issue was that we calculated the sum of every possible subarray. That’s where we lost efficiency—doing redundant work over and over.
Let’s fix this by eliminating the need to recompute sums repeatedly.
Yes, exactly! Let’s break it down step by step.
What do we do to get the sum of a subarray from index 0 to i?
We just calculate the sum of all elements from the start to index i, right?
But what if there’s an index j somewhere between 0 and i, and now you need the sum of the subarray from j to i?
Simple! You calculate the sum from 0 to i and subtract the sum from 0 to j-1. Easy, right?
Now, to make it efficient, we can precompute and store the sum up to each index in an array. This allows us to quickly get the sum of any subarray by subtracting one precomputed value from another.
Got it? Great! But wait... how does this help us determine how many subarray sums are divisible by k?
Let’s think about it with an example.
Suppose we have a sequence :
5, 10, 15, 20..., and let’s say k = 5.
What’s common here?
If we take these elements modulo k, they all become 0:
5 % 5 = 0, 10 % 5 = 0, 15 % 5 = 0...
So, whenever we add k (or a multiple of k) to an element that’s already divisible by k, the new element will also be divisible by k.
For example:
- Starting with 5, we add 5 (k) to get 10, which is also divisible by k.
- Adding 10 (2*k) gives 15, which is still divisible.
Now observe the pattern:
If you previously encountered a 0 in element % k and encounter it again later, there’s a subarray between these two occurrences whose sum is a multiple of k!
In general, if you add any multiple of k to a number divisible by k, it will also be divisible by k.
Let’s take another example:
Sequence: 8, 13, 18..., and k = 5.
- 13 - 8 = 5, divisible by 5.
- 18 - 13 = 5, divisible by 5.
- 18 - 8 = 10, divisible by 5.
Now, if we take the modulo k of each sum:
8 % 5 = 3, 13 % 5 = 3, 18 % 5 = 3.
Notice something?
Here, too, if you encounter the same remainder (like 3) more than once, it means there’s a subarray between these occurrences whose sum is divisible by k.
In general, if you encounter the same remainder more than once, it means there is a subarray whose sum is a multiple of k between the two occurrences of that remainder.
So, the observation is clear:
- Instead of storing the entire sum, store the modulo k of each sum.
- If the same remainder is encountered again, there’s a subarray in between whose sum is a multiple of k.
Now that was how to find a subarray with a sum divisible by k, but how to find its length? Well, that's simple.
To determine the length of the subarray, we just need to know its endpoints. This can be achieved using the same prefix sum modulo k logic. If we find the same remainder at two different indices, it means the subarray between these indices has a sum divisible by k.
As we iterate through the array, we store the first occurrence of each prefix sum modulo k in a hashmap (or dictionary). This allows us to efficiently track where a remainder was last seen.
Why first occurrence?
Since we are required to make the array length greater than or equal to 2, storing the first occurrence of the index of each sum modulo k helps to ensure that the subarray is long enough. By keeping the first occurrence, we maximize the length of the subarray, as any subsequent occurrence of the same sum modulo k will give us the longest possible subarray between the two indices. This approach ensures that we are working with the largest valid subarray for a given sum modulo k.
When the same remainder is encountered again:
- The start index of the subarray is the value stored in the hashmap for that remainder.
- The end index is the current index.
The length of the subarray is simply:
length = currentIndex − storedIndex
This insight helps us optimize the problem significantly! Let’s build on this idea to create an efficient solution.
Steps to do it:
- As you iterate through the array, keep a running sum of the elements. This allows you to calculate the sum of subarrays efficiently.
- Store {0: -1} in the hashmap to handle cases where a valid subarray starts from the very beginning of the array, ensuring that when the prefix sum modulo k equals 0, the length of the subarray can be correctly calculated using currentIndex - storedIndex, where storedIndex is -1.
- For each prefix sum, take the modulo of the sum with k to reduce it into manageable ranges, i.e., between 0 and k - 1.
- Store the index of each remainder (result of prefix_sum % k) in the hashmap. This helps track the position of previously seen remainders.
- For each remainder of the current prefix sum, check if it has been seen before. If so, it means a subarray exists between the previous occurrence and the current index whose sum is divisible by k.
- If a remainder has been seen before, calculate the length of the subarray. If the length (current index - stored index) is at least 2, return true.
- If the remainder is not found in the hashmap, store the current index of the remainder in the hashmap for future reference.
- If no valid subarray is found after checking all elements, return false.
Let's understand with an example:
Input: nums = [23, 2, 4, 6, 7], k = 6
Initialization: prefix_sum = 0, hashmap = {0: -1}
Iterating over the array:
- i = 0 (nums[0] = 23):
- prefix_sum = 23
- remainder = 23 % 6 = 5
- hashmap = {0: -1, 5: 0} (store the remainder and index)
- No subarray found, move to the next index.
- i = 1 (nums[1] = 2):
- prefix_sum = 23 + 2 = 25
- remainder = 25 % 6 = 1
- hashmap = {0: -1, 5: 0, 1: 1} (store the remainder and index)
- No subarray found, move to the next index.
- i = 2 (nums[2] = 4):
- prefix_sum = 25 + 4 = 29
- remainder = 29 % 6 = 5
- hashmap[5] is found at index 0.
- Subarray sum between index 0 and 2 ([ 2, 4]) is divisible by 6.
- Subarray length = 2 - 0 = 2 (valid, return true).
Output: true
The subarray [2, 4] (from index 1 to 2) has a sum of 6, which is divisible by 6. Hence, the function returns true immediately.
How to code it up:
- Initialize the hashmap prefixSum = {0: -1} to handle subarrays starting from index 0.
- Initialize preSum = 0 to track the running sum modulo k.
- Iterate through the array:
- Update the running prefix sum with preSum = (preSum + nums[i]) % k.
- If preSum is found in prefixSum:
- Check if the subarray length i - prefixSum[preSum] is at least 2.
- If true, return true (valid subarray found).
- Store the first occurrence of preSum in prefixSum if not already present.
- After the loop, return false if no valid subarray is found.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
// Initialize a hashmap to store the first occurrence of each prefix sum modulo k
unordered_map<int, int> prefixSum;
// Initialize the prefix sum map with 0 mapped to -1. This helps handle subarrays starting from index 0.
prefixSum[0] = -1;
// Initialize the variable to keep track of the running prefix sum modulo k
int preSum = 0;
// Loop through the array to calculate the prefix sum
for(int i = 0; i < nums.size(); i++) {
// Update the prefix sum modulo k
preSum = (preSum + nums[i]) % k;
// Check if this remainder has been encountered before
if(prefixSum.find(preSum) != prefixSum.end()) {
// If the subarray length is greater than or equal to 2, return true
if(i - prefixSum[preSum] >= 2) return true;
} else {
// If this remainder hasn't been seen before, store the index
prefixSum[preSum] = i;
}
}
// Return false if no valid subarray is found
return false;
}
};
2. Java Try on Compiler
import java.util.HashMap;
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
// Initialize a hashmap to store the first occurrence of each prefix sum modulo k
HashMap<Integer, Integer> prefixSum = new HashMap<>();
// Initialize the prefix sum map with 0 mapped to -1. This helps handle subarrays starting from index 0.
prefixSum.put(0, -1);
// Initialize the variable to keep track of the running prefix sum modulo k
int preSum = 0;
// Loop through the array to calculate the prefix sum
for (int i = 0; i < nums.length; i++) {
// Update the prefix sum modulo k
preSum = (preSum + nums[i]) % k;
// Check if this remainder has been encountered before
if (prefixSum.containsKey(preSum)) {
// If the subarray length is greater than or equal to 2, return true
if (i - prefixSum.get(preSum) >= 2) return true;
} else {
// If this remainder hasn't been seen before, store the index
prefixSum.put(preSum, i);
}
}
// Return false if no valid subarray is found
return false;
}
}
3. Python Try on Compiler
class Solution:
def checkSubarraySum(self, nums, k):
# Initialize a hashmap to store the first occurrence of each prefix sum modulo k
prefixSum = {0: -1}
# Initialize the variable to keep track of the running prefix sum modulo k
preSum = 0
# Loop through the array to calculate the prefix sum
for i in range(len(nums)):
# Update the prefix sum modulo k
preSum = (preSum + nums[i]) % k
# Check if this remainder has been encountered before
if preSum in prefixSum:
# If the subarray length is greater than or equal to 2, return true
if i - prefixSum[preSum] >= 2:
return True
else:
# If this remainder hasn't been seen before, store the index
prefixSum[preSum] = i
# Return false if no valid subarray is found
return False
4. Javascript Try on Compiler
var checkSubarraySum = function(nums, k) {
// Initialize a hashmap to store the first occurrence of each prefix sum modulo k
let prefixSum = new Map();
// Initialize the prefix sum map with 0 mapped to -1. This helps handle subarrays starting from index 0.
prefixSum.set(0, -1);
// Initialize the variable to keep track of the running prefix sum modulo k
let preSum = 0;
// Loop through the array to calculate the prefix sum
for (let i = 0; i < nums.length; i++) {
// Update the prefix sum modulo k
preSum = (preSum + nums[i]) % k;
// Check if this remainder has been encountered before
if (prefixSum.has(preSum)) {
// If the subarray length is greater than or equal to 2, return true
if (i - prefixSum.get(preSum) >= 2) return true;
} else {
// If this remainder hasn't been seen before, store the index
prefixSum.set(preSum, i);
}
}
// Return false if no valid subarray is found
return false;
};
Time Complexity: O(n)
The loop runs once for each element in the array (nums), so the time complexity for this part is O(n).
Calculating the prefix sum is done in constant time, i.e., O(1).
The hashmap operations (checking if a remainder exists and updating it) are O(1) on average, since unordered_map (C++), HashMap (Java), and objects/dictionaries (Python, JavaScript) provide constant-time lookups and insertions on average.
Therefore, the overall time complexity is O(n).
Space Complexity: O(n+k)
- Auxiliary Space Complexity: O(k)
The main auxiliary space comes from the hashmap, which stores the index of each remainder encountered during the iteration.
In the worst case, there could be k different remainders (ranging from 0 to k-1), so the space used by hashmap is O(k). - Total Space Complexity: O(n)
The input array nums is of size n, which requires O(n) space.
Thus, the total space complexity is O(n) for the input array plus O(k) for the remainder map, Therefore, the total space complexity is O(n+k).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.