> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/two-pointers/window/minimum-size-subarray-sum.md).

# Minimum Size Subarray Sum

## Question ([LC.209](https://leetcode.com/problems/minimum-size-subarray-sum/))

> Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s.

## Example

```
I: nums = [2,3,1,2,4,3], s = 7
O: 7 because [4,3]
```

## Analysis

The brute force approach is just to try all possible subarrays then keep the shortest length.

## Code

```java
public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int currentSum = 0;
    int minLength = Integer.MAX_VALUE;

    // from this number the smallest window
    for (int i = 0; i < nums.length; i++) {
        currentSum = 0;
        for (int j = i; j < nums.length; j++) {
            currentSum += nums[j];
            if (currentSum >= s) {
                minLength = Math.min(minLength, j - i + 1);
                break;
            }
        }
    }
    return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
```

## Optimization

The brute force solution is `O(n^2)` because the pointer `j` will go back to where `i` is for every nested loop. The best way to see the overlapping subproblems is to run through some examples.

```
[2,3,1,2,4,3], 7

A   2  3  1  2  4  3

L1  i        j
L2     i  j   <--we already know this won't be a solution
                -j should at least start from index 3
```

`j` doesn't have to go back to `i` every time. Instead of scanning every window, we "shrink" the window then extend it on the other end.

```
A   2  3  1  2  4  3

L1  i------->j
L2     i------->j
L3        i---->j
L4           i---->j
L5              i->j
```

## Optimized Code

We want to shrink then extend but this won't work for the first iteration. So instead we want to shrink before we get to the next iteration.

```java
public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int currentSum = 0;
    int minLength = Integer.MAX_VALUE;
    int j = 0;
    // from this number the smallest window
    for (int i = 0; i < nums.length; i++) {
        // extend the window
        while (j < nums.length && currentSum < s) {
            currentSum += nums[j++];
        }
        // check the window sum
        if (currentSum >= s) {
            int windowSize = j - i; // no +1 b/c j++ after fit window
            minLength = Math.min(minLength, windowSize);
        }
        // shrink before next iteration
        currentSum -= nums[i];
    }
    return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
```

This gives `O(n)` time complexity.