LeetCode #209 Minimum Size Subarray Sum

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:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

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

Solution — O(n)

Use two pointers i and j for tracking every subarray, j denotes to the head and i denotes to the tail.

1. When sum of current subarray is less than s, which means we have to put more item into this subarray, move i to next index so it be more larger.
2. When sum of current subarray is more then s, which means we have to remove items in this subarray, move j to next index so it be more smaller.
3. Every time we found sum of current subarray is more then s, recording current length and comparing with minimum length. Once it’s smaller than minimum length, update minimum length to be current length.

Complexity

Because both pointer i and j will iterate list only once, it takes O(n) times if n denotes to length of list. And it’s trivial that extra space is O(1).

Solution — O(nlogn)

In this solution, we will build a list with prefix sums of each index, i.e. prefix[i+1] = prefix [i] + i for each i in this list.

And then we will iterate this list once. At each iteration, we will try to find target = prefix[i]+s in rest subarray of this prefix list with binary search. Instead of matching target with every element in this subarray, we will be more focused on finding the leftist element that is larger than target. After search done, left will be the index what we want if it’s valid. Hence, left — i will be the minimum length of this iteration. So use a param to record minimum of these minimum length will be the answer.

Complexity

If n denotes length of nums. Building prefix list takes O(n) time. And we will traverse prefix list and do binary search in each iteration, which takes O(nlogn) time. Therefore, total time complexity is O(n + nlogn) = O(n).

For space complexity, prefix list needs O(n) space so it’s O(n) extra space.