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.

A subarray is a contiguous non-empty sequence of elements within an array.

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

Constraints

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

Thinking Process

  1. Prefix Sum + Binary Search:
    • Good when you need to query multiple ranges
    • O(n log n) time, O(n) space
    • More complex but flexible
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(nums.empty()) return 0;
        const int N = nums.size();
        int rtn = INT_MAX;
        vector<int> sums(N + 1, 0);
        for(int i = 1; i <= N; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for(int i = 1; i <= N; i++) {
            int currTarget = target + sums[i - 1];
            auto it = lower_bound(sums.begin(), sums.end(), currTarget);
            if(it != sums.end()) {
                rtn = min(rtn, (int)(it - sums.begin()) - (i - 1));
            }
        }
        return rtn == INT_MAX? 0 : rtn;
    }
};

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. Prefix Sum + Binary Search:

How the code works:

  1. Prefix Sum + Binary Search:
    • Good when you need to query multiple ranges
    • O(n log n) time, O(n) space
    • More complex but flexible
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.

Walkthrough — input target = 7, nums = [2,3,1,2,4,3], expected output 2:

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

Common Mistakes

  1. Empty array: nums = [] → return 0
  2. No valid subarray: nums = [1,1,1], target = 10 → return 0
  3. Single element: nums = [5], target = 5 → return 1
  4. Entire array needed: nums = [1,2,3], target = 6 → return 3

  5. First element: nums = [10,1,1], target = 10 → return 1

  6. Wrong binary search target: Forgetting to add sums[i-1] to target
  7. Index calculation: Wrong length calculation (it - sums.begin()) - (i - 1)
  8. Not checking bounds: Not checking if it != sums.end()
  9. Sliding window: Not shrinking window when sum >= target
  10. Return value: Returning INT_MAX instead of 0 when no solution

Key Takeaways

  1. Prefix Sum + Binary Search:
    • Good when you need to query multiple ranges
    • O(n log n) time, O(n) space
    • More complex but flexible
  2. Sliding Window:
    • More intuitive and efficient
    • O(n) time, O(1) space
    • Preferred for single query problems

  3. Monotonic Property: Prefix sums are non-decreasing (all positive), enabling binary search

  4. Window Shrinking: Once sum >= target, shrink from left to find minimum length

References

Template Reference