This week, we’re going to talk about a popular question that seems simple at first glance, but can be quite difficult by removing particular restrictions. This type of question is very common in coding interviews as interviewers like to use the easy version as a warm-up question and if there’s still time remained, the follow-up question will be asked.
Also, in our previous posts, we didn’t cover much about array problems. So it’s definitely worth to analyze this problem in depth. In this article, we will talk about topics including array, sliding window, recursion and DP (dynamic programming).
Question
Given an array of non-negative numbers, find continuous subarray with sum to S.
Not only has this question been asked by Facebook recently, but it can be extended with different follow-up questions. I’m pretty sure you’re going to learn a lot from this post. Again, the goal is not providing “standard answers”. Instead, we want to show you how you can come up with the right approach and how to analyze the problem from scratch.
Analyze
After reading the description, there are two keywords that should catch your attention – “non-negative” and “continuous”.
When all the numbers are non-negative and the problem is about the sum of subarrays, one common idea is that adding more numbers to the subarray can only increase the current sum. In other words, if you already had a subarray with sum larger than S, you don’t need to consider including more numbers, which will significantly simplify the problem and make the algorithm faster. Keyword “continuous” is even easier to understand. It tremendously reduces the possible subarray candidates to consider.
Solution
Again, think about the problem by yourself before reading the rest of this post.
The most naive solution is obvious. You can use 2 loops to check all continuous subarrays and see if any of them sum up to S. The time complexity is O(N^2) and apparently is not ideal.
Let’s talk about how to optimize it. As analyzed above, we should take advantage of non-negative numbers. If the analysis doesn’t sound familiar to you, I highly recommend you check If a String Contains an Anagram of Another String. You’ll see how similar the approach is, although it’s a string problem.
We’ll use the same technique – sliding window.
- Start with two pointers that represent the subarray.
- If the sum of current subarray is smaller than S, move the end pointer one step forward.
- If the sum is larger than S, move the start pointer one step forward.
- Once the current sum equals to S, we found the target.
The reason we can use sliding window here is that adding more numbers can only increase the current sum and the two pointers never need to go back to search candidates. This makes the algorithm has O(N) time complexity with no extra memory used.
Follow-up
What if we remove the two restrictions, so the problem becomes – Given an array of numbers, find subarray with sum to S.
Again, let’s start with the most naive approach – check all subarray candidates. As you can see, even this approach is not easy to implement. First, you can’t use 2 or more loops to get all subarrays. Second, there are totally 2^N subarrays. The most important lesson here – whenever you see issues like this (can’t use loops to check all possibilities or an exponential number of candidates), you should immediately think of recursion or dynamic programming.
Another reason you should think of recursion is that the problem can be divided into sub-problems. Suppose you want to include the first element a[0], then the problem becomes to find subarray from a[1:N] with sum to S-a[0]. Similarly, if a[0] is not included, we just need to solve the problem from a[1:N] with sum to S.
This should be very straightforward to you and it shouldn’t be hard to implement the code.
DP (dynamic programming)
The downside of the above recursive solution is time efficiency. As you can see that many subarrays have been calculated for multiple times. Thus, the most common way to optimize this is to save temporary results into memory, which is so-called dynamic programming. Check A Step by Step Guide to Dynamic Programming if you want to know more.
The first step is to figure out how to denote a sub-problem. The sub-problem here is to find subarray from a[i:N] with sum to M. Therefore, we can use (i, M) to denote a sub-problem and the result can be saved in a 2D array. The high-level pseudo code is like this:
In a nutshell, if the sub-problem has been solved, return directly. Otherwise, solve the two sub-problem (with and without a[i]). The last step is to store the result back to memory.
Takeaways
- I hope you can be very sensitive to words like “non-negative” and “continuous”.
- This is at least the 4th time we’ve seen sliding window technique, although previously we were using in string problems.
- whenever you see issues like (can’t use loops to check all possibilities or an exponential number of candidates), you should immediately think of recursion or dynamic programming.
- The dynamic programming solution can be optional.
The post is written by
Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..
I'd like to learn more
The last question , i think its not “subarray” , it should be subset …!! please correct that .
Hi Ajit,
Thanks for pointing this out. You are correct. It should be subset.
Algirht alright alright that’s exactly what I needed!
When a[i] is not included should not the code be
res = subarray(i + 1, M)
if res != null
mem[i+1][M] = res
return res
Hi Swarup,
You are completely correct. It’s a typo in the pseudo code.
Thanks alot – your answer solved all my problems after several days stgnurligg
Fixed in the post 🙂
Hi swarup
this solution not work if M is -ve number.
Having a hard time putting the code together – does that look correct or am I missing something? Thanks!
(javascript):
function getSum(arr, sum, start, res, memo){
if (start >= arr.length) return false;
if (memo[start] && memo[start][sum]) return memo[start][sum];
res.push(arr[start]);
if (arr[start] == sum || getSum(arr, sum – arr[start], start + 1, res, memo)){
memo[start] = memo[start] || [];
memo[start][sum] = res;
return res;
} else {
res.pop();
}
if (getSum(arr, sum, start + 1, res, memo)){
memo[start] = memo[start] || [];
memo[start][sum] = res;
return res;
}
return false;
}
var res2 = [];
getSum([2, 2, 3, 4, 5], 9, 0, res2, []);
alert(res2);
Where is the terminating condition in the DP code ?
When there’s no element in the array, it should be terminated. The pseudo code is only used to illustrate the core idea.
Solution for subarray with given sum:
// C++ program to print subarray with sum as given sum
#include
using namespace std;
// Function to print subarray with sum as given sum
void subArraySum(int arr[], int n, int sum)
{
// create an empty map
unordered_map map;
// Maintains sum of elements so far
int curr_sum = 0;
for (int i = 0; i < n; i++)
{
// add current element to curr_sum
curr_sum = curr_sum + arr[i];
// if curr_sum is equal to target sum
// we found a subarray starting from index 0
// and ending at index i
if (curr_sum == sum)
{
cout << "Sum found between indexes "
<< 0 << " to " << i << endl;
return;
}
// If curr_sum – sum already exists in map
// we have found a subarray with target sum
if (map.find(curr_sum – sum) != map.end())
{
cout << "Sum found between indexes "
<< map[curr_sum – sum] + 1
<< " to " << i << endl;
return;
}
map[curr_sum] = i;
}
// If we reach here, then no subarray exists
cout << "No subarray with given sum exists";
}
// Driver program to test above function
int main()
{
int arr[] = {10, 2, -2, -20, 10};
int n = sizeof(arr)/sizeof(arr[0]);
int sum = -10;
subArraySum(arr, n, sum);
return 0;
}
please help !wrtting example with python code thanks!
Using sliding window for this question is WRONG.
sliding window requires sorted (or sortable) sequence. We can’t use sorting here because we’ll change the order of the element of the correct subset
Also, how are you going to use sliding window (2 indexes) to sum without nesting loops? sounds like you’re going to reinvent the brute force approach which you described as naive