The sliding window problem commonly presents a sequence and asks a property a subsequence that satisfied certain restrictions. The subsequence can be consecutive or non-consecutive. The unknown property could be size, sum, max/min, etc. Similarly, the known restriction could be size, sum, max/min, etc. One important character of the sliding window problem is that the subsequence is in order.

Most sliding window problems can be solved using a deque, using two pointers or using a dynamic programming approach.

Besides, taking accumulative sums of the input sequence is a common preprocessing step, changing the problem of sums into the problem of differences.

• Two pointers: Keep two pointers that mark the start and the end of the sliding window. All elements in the current subsequence are candidates for future start points. This is applied when both sides of the sliding window matter.
• Deque: Keep a deque that is the curial elements that could be both the start/end of the sliding window. Compared to the two-pointers method, not all elements in the current subsequence are candidates for future start points. This is applied when both sides of the sliding window matter.
• Dynamic programming: Keep a 1d array that marks the end of the sliding window and a specific summary of all the subsequences ends with the specific element. This is applied when only one side of the sliding window matter.

862. Shortest Subarray with Sum at Least K (Hard)

This problem uses a deque. The deque maintains the possible locations of the start/end of the subsequence. The mechanism to determine a node is no longer good for a start is that

1. The current subsequence already has a sum larger or equal to K, leaving it as a candidate cannot find a shorter subsequence.
2. The current visiting node is smaller or equal to an old node. The old node cannot do better than the new node.

With the restriction of rule 2, the dequeue is intrinsically keeping an increasing sequence.