#209

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Size Subarray Sum

Find the minimal length of a subarray whose sum is greater than or equal to the target using efficient algorithms.

array binary search sliding window prefix sum

Problem Statement

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 no such subarray exists, return 0.

For example, if the input is target = 7, nums = [2, 3, 1, 2, 4, 3], the minimal subarray with a sum greater than or equal to 7 is [4, 3], which has length 2.

Examples

Example 1

Input: target = 7, nums = [2,3,1,2,4,3]

Output: 2

The subarray [4,3] has the minimal length under the problem constraint.

Example 2

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

Output: 1

Example details omitted.

Example 3

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

Output: 0

Example details omitted.

Constraints

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

Solution Approach

Sliding Window

A sliding window approach helps to dynamically adjust the subarray size, maintaining the sum of elements as you expand or shrink the window. This allows for efficient checking of potential subarrays that meet the sum condition.

Binary Search

Binary search is applied to optimize the search for the smallest subarray. By testing different lengths of subarrays and narrowing down the valid answer space, we can find the minimal length in O(log n) time.

Prefix Sum

Using a prefix sum array can help quickly compute the sum of any subarray by storing the cumulative sums up to each index. This minimizes repeated calculations when evaluating subarrays.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because we iterate through the array once. The space complexity is O(1) since we only use a few variables to track the window and the minimal length, without needing extra space for additional data structures like arrays or lists.

What Interviewers Usually Probe

The candidate demonstrates a solid understanding of sliding window techniques and can apply them to optimize the subarray sum problem.
The candidate is familiar with binary search and can leverage it effectively for narrowing the search space.
The candidate integrates prefix sums into their solution, showing they can optimize repetitive sum calculations.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the problem by trying to solve it without leveraging the sliding window or binary search techniques.
Failing to consider edge cases where no subarray satisfies the sum condition, leading to incorrect answers like returning a subarray length of zero when it should be zero.
Using brute force approaches that result in a time complexity of O(n^2) or worse, rather than utilizing O(n) algorithms.

Follow-up variants

Allowing negative numbers in the input array and adjusting the solution accordingly.
Modifying the problem to return the subarray itself, not just its length.
Changing the sum condition to be less than or equal to the target instead of greater than or equal to.

FAQ

What is the Minimum Size Subarray Sum problem?

The Minimum Size Subarray Sum problem asks you to find the minimal length of a contiguous subarray that has a sum greater than or equal to a given target.

How do you approach the Minimum Size Subarray Sum problem?

You can approach this problem using sliding window, binary search, and prefix sum techniques to efficiently find the smallest subarray that meets the target sum condition.

Why does binary search help in the Minimum Size Subarray Sum problem?

Binary search helps by narrowing down the search space for possible subarray lengths, allowing for faster optimization of the minimal subarray length.

What is the time complexity of the Minimum Size Subarray Sum solution?

The time complexity of the optimal solution is O(n), where n is the length of the input array.

How can GhostInterview assist in solving the Minimum Size Subarray Sum problem?

GhostInterview provides step-by-step guidance, highlights potential mistakes, and suggests efficient approaches like sliding window and binary search for solving this problem.

terminal

Solution

Solution 1: Prefix Sum + Binary Search

First, we preprocess the prefix sum array $s$ of the array $nums$, where $s[i]$ represents the sum of the first $i$ elements of the array $nums$. Since all elements in the array $nums$ are positive integers, the array $s$ is also monotonically increasing. Also, we initialize the answer $ans = n + 1$, where $n$ is the length of the array $nums$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = n + 1
        for i, x in enumerate(s):
            j = bisect_left(s, x + target)
            if j <= n:
                ans = min(ans, j - i)
        return ans if ans <= n else 0

Solution 2: Two Pointers

We can use two pointers $j$ and $i$ to maintain a window, where the sum of all elements in the window is less than $target$. Initially, $j = 0$, and the answer $ans = n + 1$, where $n$ is the length of the array $nums$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = n + 1
        for i, x in enumerate(s):
            j = bisect_left(s, x + target)
            if j <= n:
                ans = min(ans, j - i)
        return ans if ans <= n else 0

Continue Practicing

#713 subarray product less than k #862 shortest subarray with sum at least k #1004 max consecutive ones iii