Smallest Subarray with a Given Sum | Coding Interview | Sliding-Window Pattern

If you are planning to perfect your skill to solve problems based on the sliding window pattern, In my opinion, this is the best starting point. It is also important as these tech companies (Goldman Sachs, Meta, Amazon, and Google) have asked this question.

The important thing to get out of this article is when we should use the sliding window pattern. We have already discussed a similar problem, Longest Repeating string after K replacements.

This article belongs to the interview preparation plan, which you can find here.

So Los Geht's.

Contents

1. Description
2. Brute Force Approach
3. Sliding Window Approach
4. Code
5. Time & Space Complexity

Description

You are given an array of integers A and an integer target, and you have to find the smallest Subarray of A such that the sum of its elements is greater or equal to the target.

If no such subarray exists, then output 0.

Example 1:

Input: [4, 1, 6, 2, 3] and target = 8
Output: 2

Explanation: The smallest subarray with sum greater or equal to 8 is [2, 6].

Example 2:

Input: [2, 2, 2, 2] and target = 10
Output: 0

Explanation: No subarray exists whose sum is greater or equal to 10.

Brute Force Approach

We can naively go through each Subarray, n being the size of the array, we will have n² subarrays. For each Subarray, we will find the sum of its elements and remember the size of the smallest Subarray with a total greater than or equal to our target.

The Naive Algorithm

• Use two for loops to traverse every Subarray, where the outer loop will point to the start, and the inner loop will point to the end of the subarrays.
• Use another loop, to sum up the elements of the current Subarray.
• If the sum is greater or equal to the target and the size of the current Subarray is smaller than our minimum size so far, then update the minimum size with the current subarray size.

Here the time complexity will be cubic, O(n³) in nature because we are using three nested loops, the outer two for loops are for traversing the subarrays, and the innermost loop is used to get the sum of the current Subarray.

While we are at it, let's look at its code. I have commented on the code well, so if c++ is not your primary language, you can still understand what is happening.

Code

Output:
The length of the smallest subarray with target 8 is 2

Of course, we can improve it from O(n³) to O(n²); if we preprocess the list and get the prefix sum array (O(n)), then getting the sum of any subarray will be a constant operation (the following figure).

Now let's see some magic and understand an easy solution with linear complexity.

Sliding window approach

The strategy to solve this problem is similar to the Maximum Sum Subarray of Size K and in this approach, as the name suggests, we slide a window from left to right and change the window's size suiting our needs. A window on an array can be controlled by using two variables, one pointing to the start and the other pointing to the end.

For this problem, our window will extend from the right side by adding new elements as long as the sum of its elements is less than the target. And since we need the smallest Subarray, once the sum of the window is greater than or equal to the target, we will start shrinking the window from the left.

At any point, if a window has a sum greater than or equal to the target and its size is smaller than what we have seen so far, we will remember this new size.

This process will end once the last element of the array has been added to the sliding window.

Let's see it using an example.

Its code is as simple as the solution itself. It's well commented (to make it language independent) and written in c++.

Code

Output:
The length of the smallest subarray with target 8 is 2

Time & Space complexity

Time: We can see that the outer for loop add each element only once, and the inner while removes (if it does) only once hence the given approach is linear, O(n) in nature.

Space: We are not using space for this algorithm, so its space complexity is constant, O(1).

Thanks for reading.

I hope this article was helpful to you.

If you liked what you just read, a clap 🤗🤗🤗would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn't like it? Please do comment😋!

P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and supports all the writers.

You can also follow me HERE to get updates on the stories that I write.