[Leetcode] Shortest Subarray with Sum at Least K

862. Shortest Subarray with Sum at Least K

Given an integer array numsand an integer k, return _the length of the shortest non-empty subarray of _nums_with a sum of at least _k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

1 <= nums.length <= 10``5

-10``5`` <= nums[i] <= 10``5

1 <= k <= 10``9

How to approach?

Brute Force

function shortestSubarray(nums: number[], k: number): number {
    let minLength = Number.POSITIVE_INFINITY;

    for (let start = 0; start < nums.length; start++) {
        let sum = 0;
        for (let end = start; end < nums.length; end++) {
            sum += nums[end]
            if (sum >= k) {
                minLength = Math.min(minLength, ans.length)
            }
        }
    }
    return minLength === Infinity ? -1 : minLength
};

Time Limit Exceeded Error

PrefixSum

function shortestSubarray(nums: number[], k: number): number {
    let prefix = []
    prefix[0] = 0;
    for (let i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i]
    }
    let minLength = Number.POSITIVE_INFINITY;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            let sum = prefix[j + 1] - prefix[i]
            if (sum >= k) {
                minLength = Math.min(minLength, j - i + 1)
            }
        }
    }
    return minLength != Infinity ? minLength : -1
};

Time Limit Exceeded Error

Deque

function shortestSubarray(nums: number[], k: number): number {
    let n = nums.length;
    let prefix = [0]

    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i]
    }

    let dq = []
    let min_length = Infinity

    for (let i = 0; i <= n; i++) {
        while (dq.length > 0 && prefix[i] - prefix[dq[0]] >= k) {
            min_length = Math.min(min_length, i - dq[0])
            dq.shift()
        }

        while (dq.length > 0 && prefix[dq[dq.length - 1]] >= prefix[i]) {
            dq.pop()
        }

        dq.push(i)
    }

    return min_length === Infinity ? -1 : min_length
}

1. purpose: find the shortest subarray that meets the condition which is that sum of the subarray is at least k.
2. n is nums array's length
3. prefix is array to save the sums from 0 to ith element.
4. set min_length as positive infinite value.
5. for loop to set prefix array's element using nums array's element.
6. create double ended queue to save the indices of prefix array.
7. create for loop starting from 0, including n.
8. now using dq to compare the other subarray's sum. use dq's first element for prefix array, and find the difference between current index's prefix element. while it is greater than or equal to k, compare min_length to i - dq[0] and remove the dq's first element.
9. why? i - dq[0] is the length of subarray that meets the condition. so compare the min_length of the subarray. while it meets the condition keep removing the first element in dq. because the index in dq for subarray is already used so it can be discarded.
10. another while loop will check the current index prefix element and last dq element index in prefix, if the later is greater or equal to the current element in prefix, then pop the last element in dq.
11. why? when the prefix value of dq's last element is bigger than current prefix value, that means dq's last element will give the useless value that always give the bigger value when it's calculated later in for loop. so it's useless.
12. lastly push the index into dq to use the current index later. why? it's possible to use this current index as optimal index to make the shortest subarray.
13. lastly return the min_length if it's not infinite value.

summary

Use the dq and prefix array to set the min_length in the possible subarrays. Time complexity is On since it's using n element to compare the optimal solution in subarray, and the space complexity is On, because it use the n elements deque.