Problem Description

You are given an array of positive integers nums and a positive integer target. Your task is to find the minimal length of a contiguous subarray whose sum is greater than or equal to target.

A subarray is a contiguous part of the array. For example, if nums = [1, 2, 3, 4], then [2, 3] is a subarray.

The problem asks you to:

• Find all possible contiguous subarrays of nums
• Check which ones have a sum that is at least target
• Return the length of the shortest such subarray
• If no subarray exists with sum ≥ target, return 0

For example:

• If nums = [2, 3, 1, 2, 4, 3] and target = 7, the subarray [4, 3] has sum = 7, which is the shortest subarray meeting the requirement, so the answer is 2
• If nums = [1, 1, 1, 1] and target = 10, no subarray can sum to at least 10, so the answer is 0

The key constraint is that all integers in nums are positive, which allows for certain optimization techniques in solving this problem efficiently.

Intuition

Since we're looking for the shortest subarray with sum ≥ target, we need to efficiently check all possible subarrays. A naive approach would check every subarray by computing its sum from scratch, but this would be inefficient.

The key insight is to use prefix sums to quickly calculate any subarray sum. If we precompute s[i] = sum of first i elements, then the sum of subarray from index i to j equals s[j] - s[i].

For a subarray starting at position i, we want to find the smallest position j where s[j] - s[i] >= target, which can be rewritten as s[j] >= s[i] + target.

Here's where the crucial observation comes in: since all numbers in nums are positive, the prefix sum array s is monotonically increasing. This means s[0] ≤ s[1] ≤ s[2] ≤ ... ≤ s[n].

Because of this monotonic property, for each starting position i, we can use binary search to find the smallest j where s[j] >= s[i] + target. Binary search works here precisely because the array is sorted.

The algorithm becomes:

1. Build the prefix sum array s where s[0] = 0 and s[i] = sum of first i elements
2. For each possible starting position i, use binary search to find the earliest ending position j where the subarray sum is at least target
3. Track the minimum length found across all valid subarrays

This approach reduces the time complexity from O(n²) (checking all subarrays) to O(n log n) (n iterations with binary search in each).

Solution Approach

Let's walk through the implementation step by step:

Step 1: Build the Prefix Sum Array

We use Python's accumulate function to create a prefix sum array s:

s = list(accumulate(nums, initial=0))

This creates an array where s[i] represents the sum of the first i elements. The initial=0 parameter ensures s[0] = 0, making our array have length n+1. For example, if nums = [2, 3, 1, 2], then s = [0, 2, 5, 6, 8].

Step 2: Initialize the Answer

We set ans = n + 1 as an initial value larger than any possible valid subarray length. This helps us identify if no valid subarray exists at the end.

Step 3: Iterate Through Starting Positions

For each position i in the prefix sum array s, we treat it as a potential starting point of our subarray:

for i, x in enumerate(s):

Here, x equals s[i], which is the cumulative sum up to position i.

Step 4: Binary Search for Ending Position

For each starting position i, we need to find the smallest index j where s[j] >= s[i] + target:

j = bisect_left(s, x + target)

The bisect_left function performs binary search on the sorted array s to find the leftmost position where we could insert x + target while maintaining sorted order. This gives us the smallest j where s[j] >= x + target.

Step 5: Update Minimum Length

If j <= n (meaning we found a valid ending position within the array bounds), we update our answer:

if j <= n:
    ans = min(ans, j - i)

The length of the subarray from position i to j is j - i.

Step 6: Return the Result

Finally, we check if we found any valid subarray:

return ans if ans <= n else 0

If ans is still greater than n, no valid subarray exists, so we return 0.

Time Complexity: O(n log n) - We iterate through n+1 positions and perform binary search for each. Space Complexity: O(n) - For storing the prefix sum array.

Example Walkthrough

Let's walk through a concrete example with nums = [2, 3, 1, 2, 4, 3] and target = 7.

Step 1: Build the Prefix Sum Array

Starting with nums = [2, 3, 1, 2, 4, 3], we create the prefix sum array:

• s[0] = 0 (initial value)
• s[1] = 0 + 2 = 2
• s[2] = 2 + 3 = 5
• s[3] = 5 + 1 = 6
• s[4] = 6 + 2 = 8
• s[5] = 8 + 4 = 12
• s[6] = 12 + 3 = 15

So s = [0, 2, 5, 6, 8, 12, 15]

Step 2: Initialize Answer

Set ans = 7 (which is n + 1, since n = 6)

Step 3-5: Iterate and Search

Now we iterate through each position in s and use binary search:

• i = 0, x = s[0] = 0:

  • Need to find smallest j where s[j] >= 0 + 7 = 7
  • Binary search finds j = 4 (since s[4] = 8 is the first value ≥ 7)
  • Subarray length = 4 - 0 = 4
  • Update: ans = min(7, 4) = 4

• i = 1, x = s[1] = 2:

  • Need to find smallest j where s[j] >= 2 + 7 = 9
  • Binary search finds j = 5 (since s[5] = 12 is the first value ≥ 9)
  • Subarray length = 5 - 1 = 4
  • Update: ans = min(4, 4) = 4

• i = 2, x = s[2] = 5:

  • Need to find smallest j where s[j] >= 5 + 7 = 12
  • Binary search finds j = 5 (since s[5] = 12 equals 12)
  • Subarray length = 5 - 2 = 3
  • Update: ans = min(4, 3) = 3

• i = 3, x = s[3] = 6:

  • Need to find smallest j where s[j] >= 6 + 7 = 13
  • Binary search finds j = 6 (since s[6] = 15 is the first value ≥ 13)
  • Subarray length = 6 - 3 = 3
  • Update: ans = min(3, 3) = 3

• i = 4, x = s[4] = 8:

  • Need to find smallest j where s[j] >= 8 + 7 = 15
  • Binary search finds j = 6 (since s[6] = 15 equals 15)
  • Subarray length = 6 - 4 = 2
  • Update: ans = min(3, 2) = 2

• i = 5, x = s[5] = 12:

  • Need to find smallest j where s[j] >= 12 + 7 = 19
  • Binary search finds j = 7 (which is beyond array bounds)
  • No valid subarray starting at position 5

• i = 6, x = s[6] = 15:

  • Need to find smallest j where s[j] >= 15 + 7 = 22
  • Binary search finds j = 7 (which is beyond array bounds)
  • No valid subarray starting at position 6

Step 6: Return Result

The minimum length found is 2, which corresponds to the subarray from index 4 to 5 in the original array: [4, 3] with sum = 7.

This matches our expected answer! The subarray [4, 3] has exactly the target sum of 7 and is the shortest possible.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm consists of two main operations:

• Creating the prefix sum array using accumulate(): O(n) time
• Iterating through each element in the prefix sum array: O(n) iterations
  • For each iteration, performing a binary search using bisect_left() on the prefix sum array of length n+1: O(log n) time per search
• Total time: O(n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

The algorithm uses additional space for:

• The prefix sum array s which stores n+1 elements (including the initial 0): O(n) space
• A few scalar variables (ans, i, j, x): O(1) space
• Total space: O(n) + O(1) = O(n)

Common Pitfalls

Pitfall 1: Misunderstanding the Binary Search Target

The Issue: A common mistake is searching for target directly instead of current_sum + target in the prefix sum array. This leads to incorrect results because we need to find where the cumulative sum reaches at least current_sum + target, not just target.

Incorrect Implementation:

# WRONG: This searches for target, not the required sum
j = bisect_left(prefix_sums, target)

Correct Implementation:

# CORRECT: Search for current_sum + target
j = bisect_left(prefix_sums, current_sum + target)

Pitfall 2: Off-by-One Errors with Array Indexing

The Issue: The prefix sum array has length n+1 while the original array has length n. This can cause confusion when checking bounds and calculating subarray lengths.

Common Mistakes:

# WRONG: Comparing with wrong bound
if j < n:  # Should be j <= n
    min_length = min(min_length, j - i)

# WRONG: Using wrong initial value
min_length = n  # Should be n + 1 to distinguish "not found" case

Correct Implementation:

# Initialize with n + 1 (impossible valid length)
min_length = n + 1

# Check if j is within valid bounds (can equal n)
if j <= n:
    min_length = min(min_length, j - i)

Pitfall 3: Inefficient O(n²) Solution Instead of O(n log n)

The Issue: Using nested loops to check all possible subarrays instead of leveraging binary search on the sorted prefix sum array.

Inefficient Approach:

# WRONG: O(n²) time complexity
min_length = float('inf')
for i in range(n):
    current_sum = 0
    for j in range(i, n):
        current_sum += nums[j]
        if current_sum >= target:
            min_length = min(min_length, j - i + 1)
            break

Optimized Solution: Use the binary search approach as shown in the original solution for O(n log n) complexity.

Pitfall 4: Not Handling Edge Cases Properly

The Issue: Forgetting to handle cases where no valid subarray exists or where the entire array sum is less than target.

Incomplete Solution:

# WRONG: Returns n + 1 instead of 0 when no valid subarray exists
return min_length  # Should check if min_length is still n + 1

Complete Solution:

# CORRECT: Properly handle the "no solution" case
return min_length if min_length <= n else 0