LC 862

Goal: find the size of shortest subarray in given array that sum up to at least K, where negative integer is allowed.
Reasoning for techniques used:
1. Prefix sum: Because negative number is allowed. This causes a problem that you don’t know when to stop expanding or shrinking the window. It’s difficult to do sliding window technique.
However, we know that prefix_sum[i] - prefix_sum[j] is a good choice of window representing sum of elements between [j]…[i-1].

2. Mono-Non-decreasing double-ended queue:
A mono increasing sequence have a trait that first and last elements has the longest distance and largest sum difference. In this problem, we are looking for shortest subarray and in the same time the sum must be at least K. Thus, mono-increasing sequence is chosen. On the other hand, the reason we use the double-ended queue is because we will frequently perform shrinking and expanding widow from both end, double-ended queue allow efficient way of doing so.

Addition Explanation:
The algorithm stores a pair , [number of elements being summed up from beginning of the array, sum], in the queue.
First loop for updating the shortest window. second is for maintaining non-decreasing queue.

Time: O(size of A)