Leetcode 209. Minimum Size Subarray Sum

Clarification

Okay, so first I’ll restate the problem. We are given a positive integer target and a positive integer array nums. We need to find the minimum length of a subarray whose sum is greater than or equal to target. If no such subarray exists, we return 0.

Are all numbers in nums positive?
Will there be an integer overflow?

Brute-force Approach

A brute force solution would be to try every starting index, then extend the subarray until the sum reaches the target. That works, but in the worst case it is O(n²).

Optimized Approach

Since this is a subarray problem, we can consider to use sliding window approach trying to optimize it.

What I’ll do is to maintain a window [left, right] to calculate the sum of the subarray. I'll expand the right pointer to increase the sum. Once the sum is at least target, shrink from the left to find the smallest valid window.

So why does it work? There are three most important things for a sliding window: when to increase the window; when to shrink the window; when to update the result. The key observation for this question is that all numbers are positive. So when I move the right pointer, the sum can only increase. Once it is at least the target, there is no point to keep increasing the window since it only increases sum. So the best thing to do is to move the left pointer as much as possible to decrease the sum while keeping the window valid. And then we update the result. This guarantees that for every right pointer, we find the minimum valid window.

Since both pointers only move forward and never backward, each number enters and leaves the window at most once, this gives us O(n) time. We don't need extra space so the space complexity is O(1).

Code

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum += nums[right++];

            while (left < right && sum >= target) {
                minLen = Math.min(minLen, right - left);
                sum -= nums[left++];
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

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)). The solution would be a prefix sum + binary search.