Minimal Size Subarray Sum

Problem Description

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

Brute Force Solution

A naive approach is to consider all possible subarrays and check if their sum is greater than or equal to the target. We keep track of the minimal length found so far.

Algorithm

1. Iterate through all possible starting positions i from 0 to n-1.
2. For each starting position, iterate through all possible ending positions j from i to n-1.
3. Calculate the sum of the subarray nums[i...j].
4. If the sum is greater than or equal to the target, update the minimal length if the current subarray's length is smaller.
5. If no valid subarray is found, return 0.

Code (Python)

def min_subarray_len_brute_force(target: int, nums: list[int]) -> int:
    min_len = float('inf')
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            sub_array_sum = sum(nums[i:j+1])
            if sub_array_sum >= target:
                min_len = min(min_len, j - i + 1)
    return min_len if min_len != float('inf') else 0

Time Complexity

O(n^2) due to the nested loops.

Space Complexity

O(1) as we only use a constant amount of extra space.

Optimal Solution (Sliding Window)

A more efficient approach is to use the sliding window technique. We maintain a window (subarray) and adjust its start and end to find the minimal length subarray that satisfies the condition.

Algorithm

1. Initialize two pointers, start and end, to 0.
2. Initialize current_sum to 0 and min_len to infinity.
3. Iterate while end is less than the length of the array.
4. Add nums[end] to current_sum.
5. While current_sum is greater than or equal to the target:
   • Update min_len with the minimum of min_len and end - start + 1.
   • Subtract nums[start] from current_sum.
   • Increment start.
6. Increment end.
7. If min_len is still infinity, return 0; otherwise, return min_len.

Code (Python)

def min_subarray_len_sliding_window(target: int, nums: list[int]) -> int:
    start = 0
    end = 0
    current_sum = 0
    min_len = float('inf')
    n = len(nums)

    while end < n:
        current_sum += nums[end]
        while current_sum >= target:
            min_len = min(min_len, end - start + 1)
            current_sum -= nums[start]
            start += 1
        end += 1

    return min_len if min_len != float('inf') else 0

Time Complexity

O(n) because each element is visited at most twice (once by start and once by end).

Space Complexity

O(1) as we only use a constant amount of extra space.

Edge Cases

• Empty input array: The problem statement says the array will have at least length 1, but it's good to consider this case.
• No subarray sums to at least target: Should return 0. Handled by the min_len check.
• All positive numbers: Problem statement specifies positive integers.
• Target is a very large number, larger than the sum of the entire array. This is implicitly handled. In this case, the function will just return 0, which satisfies the requirement.

Example

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

The sliding window expands and contracts:

• [2], sum = 2
• [2, 3], sum = 5
• [2, 3, 1], sum = 6
• [2, 3, 1, 2], sum = 8 >= 7. min_len = 4. Shrink.
• [3, 1, 2], sum = 6 < 7. Stop shrinking.
• [3, 1, 2, 4], sum = 10 >= 7. min_len = 4. Shrink.
• [1, 2, 4], sum = 7 >= 7. min_len = 3. Shrink.
• [2, 4], sum = 6 < 7. Stop shrinking.
• [2, 4, 3], sum = 9 >= 7. min_len = 3. Shrink.
• [4, 3], sum = 7 >= 7. min_len = 2. Shrink.
• [3], sum = 3 < 7. Stop shrinking.

Final Result: 2