LeetCode 862. Shortest Subarray with Sum at Least K

Question

Given an integer array nums and 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 <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

Source: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

Solution

We use prefix sum to simplify the sum of subarray. The sum of any subarray can be calculated from prefix sum. This idea is similar to the usage of common prefix/suffix in LeetCode 718. Maximum Length of Repeated Subarray.

We use a for loop to traverse ends of prefix sums prefixSums[y], a monotonic queue to maintain starts of prefix sums prefixSums[x]. For valid combinations of prefix sums (i.e. prefixSums[y]-prefixSums[x]>=k), smaller y, larger x and larger prefixSums[x] have advantage.

// 2D DP, O(n^2), Memory Limit Exceeded
// still has redundant computation
public int shortestSubarray(int[] nums, int k) {
    int len = nums.length;
    int minLen = len + 1;
    // dp[i][j] is the sum of subarray nums[i:j] (both ends are inclusive)
    int[][] dp = new int[len][len];
    for (int m = 0; m < len; m++) {
        dp[m][m] = nums[m];
        if (dp[m][m] >= k) {
            // can also return early
            minLen = Math.min(minLen, 1);
        }
    }
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            dp[i][j] = dp[i][j - 1] + nums[j]; // repeat same computation
            if (dp[i][j] >= k) {
                minLen = Math.min(minLen, j - i + 1);
            }
        }
    }
    return minLen == len + 1 ? -1 : minLen;
}

// monotonic queue, O(n)
public int shortestSubarray2(int[] nums, int k) {
    int len = nums.length;
    int minLen = len + 1;
    // prefixSums[i] is the sum of nums[:i] (exclusive)
    long[] prefixSums = new long[len + 1];
    // calculate prefix sum
    for (int i = 1; i <= len; i++) {
        prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
    }
    // mono-dequeue, each element is the index of prefixSums,
    // prefixSums[i] ascending
    Deque<Integer> monoDeque = new LinkedList<>();
    // sum of subarray nums[x:y] (x inclusive, y exclusive) = prefixSums[y] - prefixSums[x]
    for (int y = 0; y <= len; y++) {
        while (!monoDeque.isEmpty() && prefixSums[y] - prefixSums[monoDeque.getFirst()] >= k) {
            int x = monoDeque.removeFirst();
            minLen = Math.min(minLen, y - x);
        }
        while (!monoDeque.isEmpty() && prefixSums[y] <= prefixSums[monoDeque.getLast()]) {
            monoDeque.removeLast();
        }
        monoDeque.addLast(y);
    }
    return minLen == len + 1 ? -1 : minLen;
}