Leetcode 209 Minimum Size Subarray Sum

Leetcode 209 Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

This is quite an interesting problem since it has a couple of interesting solutions that can be extend to other problems and how you think about algorithms in general.

The most naive way of thinking is to just brute force it. We can used nested for loops to enumerate all possible subarrays and check if each of them meets the requirements then we update the result. Sounds simple enough but depends on how you implement it, the time complexity will be at least O(n^2). Not good for sure and I don’t think the interviewer will give you a pass at all!

So can we optimize the time complexity so it’s acceptable?

There are a couple of options that we can try:

• O(nLogn)
• O(n)

First option n(Logn)

Let’s first look at the first option of O(nLogn). It could mean there are in total O(n) operations and each operation cost O(Logn) to complete.

Let’s go even further, O(n) usually means we loop through the array once. Let’s say we have a left and right pointer to denote the boundaries of the subarray, we can iterate only the start pointer instead of the nested for loops.

At each iteration, we do a O(Logn) operation to find the smallest right pointer that meets the requirements for the subarray, that could mean, maybe binary search?

Yes!!! Binary search it is!!

Remember in the this post Lintcode 1844 subarray sum equals to k II we touched a little bit on a concept called prefixSum?

prefixSum[i] is the sum of the first i elements in the array (index from 0 to i - 1)

To get the sum up to the element that has a index of i from the prefixSum array, we simply get it by prefixSum[i + 1]

For the sum between index i to j we can use prefixSum[j+1] - prefixSum[i] to calculate

So the first element in prefixSum array prefixSum[0] should be 0 , which means the sum of the first 0 elements of the array is 0

array:     [2, 3, 1, 2, 4, 3]
prefixSum: [0, 2, 5, 6, 8, 12, 15]

We can generate the prefixSum array by looping through the array in O(n) time

Now let’s connect the dots here and see why we can utilize the prefixSum array to perform the O(Logn) operation at each iteration.

Let’s say the subarray has a left boundary of left and right boundary of right. The sum of this subarray would be prefixSum[right + 1] - prefixSum[left]. Now the question becomes: given an index in nums array, can I find another index so prefixSum[right + 1] - prefixSum[left] >= target? Remember prefixSum array is monotonically increasing, or in another word, sorted, we can basically use binary search to find the smallest index right that meets the requirement above. This is where the O(Logn) comes from.

Now let’s take a look at the solution

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */

// find the smallest index in nums that MIGHT meet the subarray sum requirement
// but it's not guaranteed that returned number will meet the requirement
// so we will need to check it again after calling this function
function binarySearch(i, prefixSum, target) {
    let left = i;
    let right = prefixSum.length - 2
    while(left + 1 < right) {
        const mid = Math.floor((left + right) / 2)
        if(prefixSum[mid + 1] >= target) {
            right = mid
        } else {
            left = mid
        }
    }

    if(prefixSum[left + 1] >= target) {
        return left
    } else {
        return right
    }
}

var minSubArrayLen = function(target, nums) {
    let prefixSum = [0];
    let result = Infinity
    for(let i = 0; i < nums.length; i++) {
        prefixSum.push(prefixSum[i] + nums[i])
    }

    for(let left = 0; left < nums.length; left++) {
        const t = prefixSum[left] + target
        const right = binarySearch(left, prefixSum, t)
        if(prefixSum[right + 1] >= t) {
            result = Math.min(result, right - left + 1)
        }
    }

    if(result === Infinity) {
        return 0;
    } else {
        return result
    }
};

Second option O(n)

The optimal solution uses a more common pattern called two pointers. For this particular problem we will use two pointers that goes at the same direction AND the pointers does NOT go backwards! This is the key to the O(n) complexity because we will only loop the array once without the need be nested. The reason why we can do this is because all the elements in the array are positive.

• We will have two pointers denoting the left and right boundaries of the subarray, they all start at the beginning of array.
• We iterate on left, at each iteration we move right until the requirement is met or out of boundary. Then we check if requirement is met and update the min length if needed.
• left will move to the next index, we go back to the beginning of the logic, move right until requirement is met etc.

This way will cover all possible subarrays that could meet the requirements.

Code:

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */

var minSubArrayLen = function(target, nums) {
    let right = 0;
    let subarraySum = 0;
    let result = Infinity;
    for(let left = 0; left < nums.length; left++) {
        while(right < nums.length && subarraySum < target) {
            subarraySum += nums[right]
            right++;
        }

        // need to check this again because right could be out of bound too
        if(subarraySum >= target) {
            result = Math.min(result, right - left)
            subarraySum -= nums[left]
        }
    }

    if(result === Infinity) {
        return 0
    } else {
        return result
    }
};