# 209. Minimum Size Subarray Sum

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:

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.

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.

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!

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

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

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

### Two Pointers

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

My Version: (initialize sum as nums[0])

Note: The subarray is [start, end].

We can also use while to update start until it satisfies the condition:

Other:

Note: The subarray is [start, end).

Use while:

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

Comment
Junhao Wang
a software engineering cat