# 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/two-pointers/window/minimum-size-subarray-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.