Deque - store the index

The Problem

Leetcode 239. Sliding Window Maximum: Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Follow up: Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

The Solution

The obvious solution is for every subarray of length k, we find the maximum. But the complexity will be O((n-k)*k). Let’s figure out the linear time solution.

Lets consider a k-length subarray from index [i to j] with max value at index m, i.e. j-i+1 = k. Let’s say we move the window forward so the new window from [i+1 to j+1], then we have 2 observations:

1. If nums[k+1] >= nums[m], then we know that the max value from [i+1 to j+1] is nums[j+1], and in fact, we do not need to revisit the array from index j+1 backward anymore.
2. If nums[k+1] < nums[m] ,then we must keep track of the index at both the current max m and the index (k+1), for example:
nums = [1,2,3,10,4,3,2,1] , k = 3

The windows [2,3,10], [3,10,4] and [10,4,3] are all have max of 10, but the moment the window passes 10, we need to be able to tell that the max is 4.

Observation 1 tells us that we need to know whether the index of max value is within the current window, if yes, we simply return the value at max index.

Observation 2 tells store the index of the max value (and to remove the index when it is out of the k-length window). We also need to keep track of the index of new element from the right of the max value if it is smaller than the current max value. We need to perform operations from both left and right and hence a useful data structure for this case is deque.

from collections import deque
def max_sliding_window(nums, k):
res = []
deq = deque()

for i in range(len(nums)):
if len(deq) > 0 and i - deq >= k:
deq.popleft()

while len(deq) > 0 and nums[deq[-1]] <= nums[i]:
deq.pop()
deq.append(i)

if len(deq) > 0 and i >= k-1:
res.append(nums[deq])

return res

The Analysis

Even though there is a while loop inside the for loop, you can see that the complexity is still linear, since the total of operation of the while loop for entire of algorithm is only equivalent to the number of elements in the given array.

There are 2 things we can learn from this technique: the deque data structure and to store the index instead of array values. The former is rarely seen, and usually queue only occurs in very difficult problems. The idea of storing index, however, is worth learning, as we will see later on, not only we can store the indexes in queue/deque, we can also store the indexes in stack and other data structure.

Updated: