Reference: LeetCode

Difficulty: Medium

## Problem

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`

. If there isn’t one, return`0`

instead.

**Example:**

1 | Input: s = 7, nums = [2,3,1,2,4,3] |

**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})$.

## Analysis

### Brute-Force

**Note:** Be careful of the initialization.

1 | public int minSubArrayLen(int s, int[] nums) { |

**Time:** $O(N^2)$**Space:** $O(1)$

### TreeMap

My TreeMap Post: TreeSet/TreeMap Usage & binarySearch()

Based on the idea in `325. Maximum Size Subarray Sum Equals K`

, we can use a tree map for solving this problem.

**Modification:**

When we have duplicate prefix sums, we update the index. It is because in this problem we want the minimum size. **However**, since the problem statement says there are all positive integers, there won’t be duplicate prefix sums.

1 | x s |

Also, in this problem we want the sum greater than or equal to `s`

, so we cannot use hash map. Instead, we use a tree map. In the example above, when we have a prefix sum `sum`

, we check if there is an `x`

such that `sum - x >= s`

. In other words, we want `x <= sum - s`

. It is to find the greatest `x`

that satisfies the equation. This can be achieved by using `floorKey(K)`

in TreeMap.

**Try it by hand with an example!**

1 | public int minSubArrayLen(int s, int[] nums) { |

**Time:** $O(N\log{N})$**Space:** $O(N)$

### Binary Search

Based on the same idea, we can implement the binary search by ourselves. We don’t need a tree map here because we have positive elements such that prefix sums are always increasing; in other words, as we build the array, it is always sorted in ascending order.

In this solution, we apply upper-bound binary search (FYI: Binary Search Template Notes).

1 | public int minSubArrayLen(int s, int[] nums) { |

**Time:** $O(N\log{N})$**Space:** $O(N)$

### Two Pointers

1 | s = 0, nums = [0] // this is an invalid input |

Instead of having the starting index fixed, we update it when it no longer contributes to a solution.

1 | s = 7, nums = [2, 3, 1, 2, 4, 3] // output: 2 |

My Version: (initialize `sum`

as `nums[0]`

)

**Note:** The subarray is `[start, end]`

.

1 | public int minSubArrayLen(int s, int[] nums) { |

We can also use `while`

to update `start`

until it satisfies the condition:

1 | public int minSubArrayLen(int s, int[] nums) { |

Other:

**Note:** The subarray is `[start, end)`

.

1 | public int minSubArrayLen(int s, int[] nums) { |

Use `while`

:

1 | public int minSubArrayLen(int s, int[] nums) { |

**Time:** $O(N)$**Space:** $O(1)$