209. Minimum Size Subarray Sum

Problem Description

The problem is essentially about finding the shortest continuous sequence of elements within an array of positive integers such that the sum of that sequence is at least as large as a given target value. To clarify, a subarray is defined as a contiguous part of an array. The task is to find the length of the smallest subarray that meets or exceeds the target sum. If no such subarray exists, the function should return zero.

For example, if the input array is [2, 3, 1, 2, 4, 3] and the target is 7, the subarray [4, 3] has the smallest length that sums up to 7 or more, so the answer would be the length of this subarray, which is 2.

Intuition

To solve this problem efficiently, we need to avoid checking all possible subarrays one by one since doing so would result in a very slow solution when dealing with a large array. The intuitive insight here is that we can do much better by using a "sliding window" approach. This approach involves maintaining a window that expands and contracts as we iterate through the array to find the smallest window that satisfies the condition.

Here's the thought process behind the sliding window solution:

1. We start with two pointers, both at the beginning of the array. These pointers represent the margins of our current window.
2. We move the end pointer to the right, adding numbers to our current window's sum.
3. As soon as the window's sum becomes equal to or greater than the target, we attempt to shrink the window from the left to find smaller valid windows that still meet the sum criterion.
4. Each successful window gives us a potential answer (its size), we keep track of the minimum size found.
5. We continue this process until the end pointer reaches the end of the array, and there are no more subarrays to check.
6. If the minimum length of the window is never updated from the initial setting that is larger than the array length, it means no valid subarray has been found, and we should return 0.

By using this approach, we can ensure that we only traverse the array once, giving us an efficient solution with a time complexity of O(n), where n is the length of the input array.

Learn more about Binary Search, Prefix Sum and Sliding Window patterns.

Solution Approach

The provided solution uses the Sliding Window pattern to solve the problem efficiently. This approach is useful when you need to find a subarray that meets certain criteria, and the problem can be solved in linear time without the need to check every possible subarray individually.

Here's how the sliding window algorithm is implemented in the solution:

1. Initialize two pointers, j at 0 to represent the start of the window and i which will move through the array.
2. Maintain a running sum, s, of the values within the current window which starts at 0.
3. Iterate over the array using i and continuously add the value of nums[i] to s.
4. Inside the loop, use a while loop to check if the current sum s is greater than or equal to the target. If it is, attempt to shrink the window from the left by:
   • Updating the minimum length of the valid window if necessary using ans = min(ans, i - j + 1).
   • Subtracting nums[j] from the sum s since the left end of the window is moving to the right.
   • Incrementing j to actually move the window's start to the right.
5. Once the end of the array is reached and there are no more elements to add to the sum, check if ans was updated or not. If ans is still greater than the length of the array n, it means no valid subarray was found, so we return 0.
6. If ans was updated during the process (meaning a valid subarray was found), return the value of ans which holds the length of the smallest subarray with a sum of at least target.

The use of two pointers to create a window that slides over the array allows this algorithm to run in O(n) time, making it very efficient for this type of problem.

Please note that the Reference Solution Approach mentions another method which is using PreSum & Binary Search but the provided code doesn't implement this method. The PreSum & Binary Search method involves creating an array of prefix sums and then using binary search to find the smallest valid subarray for each element. This is a bit more complex and generally not as efficient as the Sliding Window method used here which requires only O(n) time and O(1) extra space.

Example Walkthrough

Let's use a small example to illustrate the sliding window approach described in the solution. Suppose we have the array [1, 2, 3, 4, 5] and our target sum is 11.

We want to find the smallest subarray whose sum is at least 11. We'll follow the steps of the sliding window algorithm:

1. Initialize the pointers i and j both to 0, and the running sum s also to 0.
2. Start iterating over the array with i. Our window size is currently 0.

First iteration (i = 0):

• Add nums[i] to s. Now, s is 1.
• It's less than the target (11), so we move on to the next number.

Second iteration (i = 1):

• Now, s is 1 + 2 = 3.
• Still less than the target.

Third iteration (i = 2):

• s becomes 1 + 2 + 3 = 6.
• Again, we continue since s is less than our target sum.

Fourth iteration (i = 3):

• s is now 1 + 2 + 3 + 4 = 10.
• It is still below the target sum of 11.

Fifth iteration (i = 4):

• s is now 1 + 2 + 3 + 4 + 5 = 15, which is greater than our target of 11. We've now found a subarray [1, 2, 3, 4, 5] with the sum greater than or equal to the target.
• Now we try to shrink the window from the left to see if there is a smaller subarray that still meets or exceeds the target sum.
• Before moving j, we update the answer ans to the current window size, which is i - j + 1 = 5 - 0 + 1 = 5.

Now we enter the while loop to shrink the window since s >= target:

• We reduce s by nums[j]. s becomes 15 - 1 = 14, and we increment j to 1. The window is now [2, 3, 4, 5].
• s is 14, which is still greater than 11, so we repeat the procedure.
• s becomes 14 - 2 = 12 after removing the next element and j goes to 2. The window is [3, 4, 5].
• With s at 12, it's still greater than 11, continue to shrink.
• We subtract 3 to get s = 12 - 3 = 9 and move j to 3. Now s is less than 11, so we stop shrinking the window.

Our smallest subarray that meets the requirement so far is [3, 4, 5] with a length of 3. Since we've already reached the end of the array, we're done iterating, and we can return the answer, which is 3.

This example successfully demonstrated the sliding window technique where we expanded the window until we exceeded the target sum, then shrank the window from the left to find the smallest subarray that still meets the sum condition. The array [3, 4, 5] is the smallest subarray with a sum greater than or equal to the target 11, so the result is the length of this subarray, which is 3.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because there are two pointers i and j, both of which travel across the list at most once. The inner while loop only increases j and decreases the sum s until the sum is less than the target, but j can never be increased more than n times throughout the execution of the algorithm. Therefore, each element is processed at most twice, once when it is added to s and once when it is subtracted, leading to a linear time complexity.

The space complexity of the code is O(1), which means it requires a constant amount of additional space. This is because the algorithm only uses a fixed number of single-value variables (n, ans, s, j, i, x) and does not utilize any data structures that grow with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.