# Minimum Size Subarray Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-size-subarray-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-size-subarray-sum
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Yandex](https://scaleengineer.com/companies/yandex), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Darwinbox](https://scaleengineer.com/companies/darwinbox)
---
## Problem
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.

**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 <= 109`
* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 104`

**Follow up:** If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`.

# Approaches
## Brute Force Approach
Check all possible subarrays and find the minimum length subarray with sum greater than or equal to target.
**Time:** O(n²) where n is the length of the array as we need to check all possible subarrays · **Space:** O(1) as we only use a constant amount of extra space
**Pros:** Simple to understand and implement; Works for all test cases
**Cons:** Very inefficient for large arrays; Time complexity is quadratic
### Explanation
For each index i, we try all possible subarrays starting from i and calculate their sum. If we find a sum that is greater than or equal to target, we update the minimum length if the current subarray length is smaller.

```java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    minLength = Math.min(minLength, j - i + 1);
                    break;
                }
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}
```
### Algorithm
1. Initialize minLength as Integer.MAX_VALUE
2. For each index i from 0 to n-1:
   - Initialize sum as 0
   - For each index j from i to n-1:
     - Add nums[j] to sum
     - If sum >= target:
       - Update minLength if current length (j-i+1) is smaller
       - Break inner loop
3. Return 0 if minLength is still Integer.MAX_VALUE, else return minLength

## Binary Search with Prefix Sum Approach
Use prefix sum array and binary search to find the minimum length subarray.
**Time:** O(n log n) where n is the length of the array as we perform binary search for each index · **Space:** O(n) to store the prefix sum array
**Pros:** More efficient than brute force approach; Works well for sorted prefix sums
**Cons:** Requires extra space for prefix sum array; Not as efficient as the sliding window approach
### Explanation
We first create a prefix sum array. For each index i, we use binary search to find the smallest index j where the sum of subarray from i to j is greater than or equal to target.

```java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];
        
        // Calculate prefix sum
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i-1];
        }
        
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int toFind = target + prefixSum[i];
            int index = binarySearch(prefixSum, toFind, i+1, n);
            if (index != -1) {
                minLength = Math.min(minLength, index - i);
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
    
    private int binarySearch(int[] prefixSum, int target, int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left <= prefixSum.length - 1 ? left : -1;
    }
}
```
### Algorithm
1. Create prefix sum array
2. For each index i from 0 to n-1:
   - Use binary search to find smallest index j where sum[i:j] >= target
   - Update minLength if current length is smaller
3. Return 0 if minLength is still Integer.MAX_VALUE, else return minLength

## Sliding Window Approach
Use two pointers to maintain a sliding window and find the minimum length subarray.
**Time:** O(n) where n is the length of the array as we traverse the array once with two pointers · **Space:** O(1) as we only use a constant amount of extra space
**Pros:** Most efficient solution with linear time complexity; Uses constant extra space; Single pass through the array
**Cons:** Might be slightly harder to understand compared to brute force; Both pointers only move forward, so we might miss some edge cases if not implemented carefully
### Explanation
We use two pointers, left and right, to maintain a window. We expand the window by moving right pointer when sum < target and shrink it by moving left pointer when sum >= target.

```java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}
```
### Algorithm
1. Initialize left pointer, sum and minLength
2. For each right pointer from 0 to n-1:
   - Add nums[right] to sum
   - While sum >= target:
     - Update minLength if current length is smaller
     - Subtract nums[left] from sum
     - Increment left pointer
3. Return 0 if minLength is still Integer.MAX_VALUE, else return minLength

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        long s = 0;
        int ans = n + 1;
        for (int i = 0, j = 0; i < n; ++i) {
            s += nums[i];
            while (s >= target) {
                ans = Math.Min(ans, i - j + 1);
                s -= nums[j++];
            }
        }
        return ans == n + 1 ? 0 : ans;
    }
}
```

### Java

```java
class Solution {
public
  int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    long s = 0;
    int ans = n + 1;
    for (int i = 0, j = 0; i < n; ++i) {
      s += nums[i];
      while (j < n && s >= target) {
        ans = Math.min(ans, i - j + 1);
        s -= nums[j++];
      }
    }
    return ans <= n ? ans : 0;
  }
}

```

### Python

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

```

### CPP

```cpp
class Solution {
public:
  int minSubArrayLen(int target, vector<int> &nums) {
    int n = nums.size();
    long long s = 0;
    int ans = n + 1;
    for (int i = 0, j = 0; i < n; ++i) {
      s += nums[i];
      while (j < n && s >= target) {
        ans = min(ans, i - j + 1);
        s -= nums[j++];
      }
    }
    return ans == n + 1 ? 0 : ans;
  }
};

```