Algorithm: how can't I use sliding window approach for this question?

Question

I encountered this question during an interview. It gives you an array and a threshold and the function should return the length of the shortest, non-empty, contiguous subarray of that array with sum at least past that threshold.

So if the array is [2,-1,2] and threshold is 3 then it should return 3 .

Here is my attempt written in JavaScript. I was taking a typical sliding window approach, where once the sum is bigger than threshold I will decrease the window size and I keep track of the window size during each iteration.

function(array, threshold) {
  let minWindowSize = Infinity
  let sum = 0
  for (let start = 0, end = 0; end < array.length; end++) {
    sum += array[end]
    if(sum >= threshold) minWindowSize = Math.min(minWindowSize, end - start + 1)
    while (sum > threshold) {
      sum -= array[start++]
    }
  }

  return minWindowSize === Infinity ? -1 : minWindowSize
};

However my solution is buggy for cases like

array = [17,85,93,-45,-21]
threshold = 150

I wanted to know what differentiates this question from a typical sliding window question and is there a way to implement a sliding window approach to solve this question? It seems pretty straightforward but it turned out to be a hard question on leetcode.

Answer 1

The issue with your implementation lies in the fact that the sliding window approach doesn't handle cases where negative numbers can influence the sum in unpredictable ways. This problem can't be solved with a pure sliding window technique due to the presence of negative numbers in the array, which can cause the sum to decrease unexpectedly and disrupt the "shrink window" logic.

Correct approach: Use a deque (monotonic queue) to solve this.

By using a deque, we can track indices of elements in a way that allows us to maintain a window where the sum of the subarray is at least k. This solution uses prefix sums, which help efficiently compute the sum of any subarray by subtracting two prefix sums.

function shortestSubarray(nums, k) {
    const n = nums.length;
    let prefixSum = Array(n + 1).fill(0);
    
    // Compute prefix sums
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    let deque = [];
    let minLength = Infinity;

    for (let i = 0; i <= n; i++) {
        // Try to find the smallest subarray with sum >= k
        while (deque.length > 0 && prefixSum[i] - prefixSum[deque[0]] >= k) {
            minLength = Math.min(minLength, i - deque.shift());
        }
        
        // Maintain the deque in increasing order of prefix sums
        while (deque.length > 0 && prefixSum[i] <= prefixSum[deque[deque.length - 1]]) {
            deque.pop();
        }

        // Add the current index to the deque
        deque.push(i);
    }

    return minLength === Infinity ? -1 : minLength;
}

Explanation:

Prefix sum: We calculate a running sum (prefixSum[i]) so that the sum of any subarray from i to j can be computed by prefixSum[j] - prefixSum[I].

Deque: This stores indices of the prefix sum in increasing order. It helps us efficiently find subarrays whose sums are greater than or equal to k.

Shrinking the window: Whenever the difference between the current prefix sum and the smallest prefix sum in the deque is greater than or equal to k, we shrink the window from the left by removing the leftmost index from the deque.

Time complexity:

O(n): Every element is added and removed from the deque at most once, making the solution linear in time complexity.

Answer 2

As David indicates, you can't use the sliding/stretching window technique when there are negative numbers in the array, because the sum doesn't grow monotonically with the window size.

You can still solve this in O(n log n) time, though, using a technique that is usually used for the "sliding window minimum/maximum" problem.

First, transform your array into a prefix sum array, by replacing each element with the sum of that element and all the previous ones. Now your problem changes to "find the closest pair of elements with difference >= X" (assuming array[-1]==0).

As you iterate though the array, you need to find, for each i, the latest index j such that j < i and array[j] <= array[i]-x.

In order to do that quickly, first note that array[j] will always be less than all the following elements up to i, because otherwise there would be a closer element to choose.

So, as you iterate through the array, maintain a stack of the indexes of all elements that are smaller than all the later elements you've seen. This is easy and takes O(n) time overall -- after processing each i, you just pop all the indexes with >= values, and then push i.

Then for each i, you can do a binary search in this stack to find the latest index with a small enough value. The binary search works, because the values for index in the stack increase monotonically -- each element must be less than all the following ones.

With the binary search, to total time increases to O(n log n).

In JavaScript, it looks like this:

var shortestSubarray = function(A, K) {
    //transform to prefix sum array
    let sum=0;
    const sums = A.map(val => {
        sum+=val;
        return sum;
    });
    const stack=[];
    let bestlen = -1;
    for(let i=0; i<A.length; ++i) {
        const targetVal = sums[i]-K;
        //binary search to find the shortest acceptable span
        //we will find the position in the stack *after* the
        //target value
        let minpos=0;
        let maxpos=stack.length;
        while(minpos < maxpos) {
            const testpos = Math.floor(minpos + (maxpos-minpos)/2);
            if (sums[stack[testpos]]<=targetVal) {
                //value is acceptable.
                minpos=testpos+1;
            } else {
                //need a smaller value - go left
                maxpos=testpos;
            }
        }
        if (minpos > 0) {
            //found a span
            const spanlen = i - stack[minpos-1];
            if (bestlen < 0 || spanlen < bestlen) {
                bestlen = spanlen;
            }
        } else if (bestlen < 0 && targetVal>=0) {
            // the whole prefix is a valid span
            bestlen = i+1;
        }
        // Add i to the stack
        while(stack.length && sums[stack[stack.length-1]] >= sums[i]) {
            stack.pop();
        }
        stack.push(i);
    }
    return bestlen;
};

Leetcode says:

SUCCESS:

Runtime: 216 ms, faster than 100.00% of JavaScript online submissions for Shortest Subarray with Sum at Least K.

Memory Usage: 50.1 MB, less than 37.37% of JavaScript online submissions for Shortest Subarray with Sum at Least K.

I guess most people used a slower algorithm.

Answer 3

You could use a sliding window if all of the array elements were nonnegative. The problem is that, with negative elements, it's possible for a subarray to be both shorter than and have a greater sum than another subarray.

I don't know how to solve this problem with a sliding window. The approach that I have in mind would be to loop over the prefix sums, inserting each into a segment tree after searching the segment tree for the most recent sum that was at least threshold smaller.