Solve the sliding window maximum problem

The sliding window algorithm is often used to find the target number in a string/list. Today, I’ll introduce how to solve this leetcode problem using the sliding window algorithm and optimize its running time.

Problem description

You are given an array of integers 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.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], 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

You can solve it online here: leetcode 239.

Solve it using the sliding window algorithm

The intuitive solution is to find the maximum number in each sliding window. As the previous example shows, each sliding window could be marked by two pointers: left and right boundary. Steps to solve this problem are:

• Create an initial sliding window from index 0. And the right pointer is the k number away from the left pointer. Calculate the current maximum number inside the window and append it to the result list.
• We move the sliding window from index 1. Each iteration will move the left and right pointer to its left to create a new sliding window.
• For each newly created sliding window, find the maximum number inside and record it in the result list.

Code:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = []
        result = []
        right = k
        
        for i in range(k):
            window.append(nums[i])
            
        while right < len(nums):
            result.append(max(window))
            window.pop(0)
            window.append(nums[right])
            right += 1  
        result.append(max(window))
        return result

Analysis

• Time complexity: O(k*n). There are total n-k+1 sliding windows for n size list. And each sliding window will take k time to find the maximum number inside it.
• Space complexity: O(k). We create a sliding window list with size k to record the current window.

Optimize it with a deque

O(k*n) is too time-consuming. Can we solve it in linear time? The answer is yes, by introducing a deque.

Deque is a data structure that’s similar to a list. The difference is that it takes constant time to remove/append an element to the front/end of the deque. For this problem, we can introduce a deque to help to find the maximum number in each sliding window. The deque is storing the numbers that could be the maximum number in each sliding window.

Let’s how to improve it with an example: nums = [1,3,-1,-3,5,3,6,7], k = 3 .

Step1: 
nums = [1,3,-1,-3,5,3,6,7], i = 0, nums[i] = 1, deque = []
When deque is empty, nums[i] is a candidate, append i to the deque. Now deque = [0]
Step2: 
nums = [1,3,-1,-3,5,3,6,7], i = 1, nums[i] = 3, deque = [0]
The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [1]
Step3: 
nums = [1,3,-1,-3,5,3,6,7], i = 2, nums[i] = -1, deque = [1]
The current number is less than the last element in the deque. Meaning the current number is candidate for the next sliding window. We append the current index to the deque. Now deque = [1, 2]. And we've done seeing the frist sliding window, we push the first element to the result. result = [3]
Step4: 
nums = [1,3,-1,-3,5,3,6,7], i = 3, nums[i] = -3, deque = [1,2]
The current number is less than the last element in the deque. Meaning the current number is candidate for the next sliding window. We append the current index to the deque. Now deque = [1,2,3]. For second sliding window, the maximum number is nums[deque[0]]. We append it to the result. result = [3,3]
Step5: 
nums = [1,3,-1,-3,5,3,6,7], i = 4, nums[i] = 5, deque = [1,2,3]
The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [4]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5]
Step6: 
nums = [1,3,-1,-3,5,3,6,7], i = 5, nums[i] = 3, deque = [4]
The current number is less than the last element in the deque. Meaning the current number is candidate for the next sliding window. We append the current index to the deque. Now deque = [4,5]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5,5]
Step7: 
nums = [1,3,-1,-3,5,3,6,7], i = 6, nums[i] = 6, deque = [4,5]
The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [6]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5,5,6]
Step8: 
nums = [1,3,-1,-3,5,3,6,7], i = 7, nums[i] = 7, deque = [6]
The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [7]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5,5,6,7]

Code:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        arr = []
        
        for index, num in enumerate(nums):
            while arr and nums[arr[-1]] > num:
                arr.pop()
                
            arr.append(index)
            if arr[0] == index - k:
                arr.pop(0)
                
            if index >= k-1:
                result.append(nums[arr[0]])
                
        return result

Analysis

• Time complexity: O(n). We iterate the given list once to find the result.
• Space complexity: O(k). In the worst-case scenario, the size of the deque is k.

Reference

Sliding Window Maximum - LeetCode