Subarray With Given Sum

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.