Question

LeetCode Link | 209. Minimum Size Subarray Sum | Medium

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Constrains

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Examples

Example 1

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Solution Approach

Method: Sliding window

Constrains

  • Contiguous Subarray/Sequence
  • Constant Conditions

The sliding window technique is highly effective for certain types of problems, especially those that involve contiguous sequences or subarrays, but there are some constraints and considerations to keep in mind when deciding whether it’s the appropriate method to use.

  1. The sliding window technique is ideal for problems involving contiguous sequences of elements where you need to find a maximum, minimum, or specific condition within a subarray. It’s less suitable for non-contiguous or permutation-based problems.
  2. Sliding window excels when you’re checking conditions that can be updated incrementally (like sum, product, or count of elements) as the window expands or contracts.

Concept Explanation

To implement sliding window, you have to know the following things:

  • What’s inside the “window”?
  • How to move the start position of the “window”?
  • How to move the end position of the “window”?

Window is the smallest contiguous subarray where it satifies the sum is greater than or equal to target.

How to move the start position of the window: If the current window’s value is greater than or equal to target, the window should move forward (i.e., it needs to be reduced).

How to move the end position of the window: The end position of the window is the pointer that tranverses the array, which is the index in the for/while loop.

You need four variables to achieve this:

  • left and right are pointers used to maintain the boundaries of the sliding window. Initially, both are set to 0.
  • result stores the minimum length of the subarray found that meets the criteria. It starts with a value larger than the maximum possible subarray length (nums.length + 1), to ensure any valid subarray found will be shorter than this initial value.
  • sum holds the total of the elements within the windows defined by left and right.

The window is “sliding” because it can be expand and shrink, which like a caterpillar that shrinks as it moves forward.

Sliding Window Expansion: The window will keep expand until it meets the conditions which is the sum is greater and equal to target.

Sliding Window Expansion

Once it find a possible subarray that meets the conditions, it wil start to shrink window from left to try if a shorter length subarray that meets the conditions is possible in this subarray.

Sliding Window Shrink Failed

However, if the sum of subarray no longer meets the conditions after a shrink try like the figure above, it will stop shrink and expand window to next element since there is no need to keep check if inner subarray meets the conditions.

Sliding Window Shrink

As the figure shown above, the window will keep shrink from left to right if it keep meeting the conditions, and once it find a length no longer meet the conditions it expand the window to next element and do the same shrink try. Thus the window like in sliding by expand and shrink from left to right as shown below.

Sliding Window

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function minSubArrayLen(target: number, nums: number[]): number {
    let left: number = 0, right: number = 0;
    let result: number = nums.length + 1;
    let sum: number = 0;
    while (right < nums.length) {
        sum += nums[right];
        if (sum >= target) {
          	// Shrink if still meets condition
            while (sum - nums[left] >= target) {
                sum -= nums[left++];
            }
            result = Math.min(result, right - left + 1);
        }
      	// Window Expansion
        right++;
    }
    return result === nums.length + 1 ? 0 : result;
};

Conclusion

In summary, this function efficiently finds the smallest subarray with a sum at least equal to the target by dynamically adjusting a sliding window on the input array. This approach is optimal for this problem, allowing a solution in linear time, 𝑂(𝑛), since each element is processed at most twice (once when added to the sum and once when subtracted).