Sliding Window Maximum in Python

The sliding window maximum problem involves finding the maximum value in every subarray of a fixed size (or window) as the window slides over the entire array. This problem is often encountered in signal processing, financial analysis, and real-time data analysis where it's crucial to determine the peak value within a specific window of data.

Problem statement

Given an array of integers nums and an integer k, find the maximum value in each sliding window of size k.

Input

• An array of integers nums.
• An integer k representing the size of the sliding window.

Output

• A list of integers representing the maximum values in each sliding window.

Example

1nums = [1,3,-1,-3,5,3,6,7]
2k = 3
3# Output: [3, 3, 5, 5, 6, 7]

Explanation:

• The first window is [1, 3, -1], the maximum is 3.

How to solve

To solve the sliding window maximum problem efficiently, we can use a deque (double-ended queue). The deque helps to keep track of the indexes of useful elements in each window, and it allows us to efficiently get the maximum element in O(1) time. The overall time complexity is O(n) where n is the number of elements in the array.

Full code in Python

Here's the complete Python code to solve the sliding window maximum problem:

1from collections import deque
2
3def maxSlidingWindow(nums, k):
4    if not nums:
5        return []
6    
7    deq = deque()
8    result = []
9    
10    for i in range(len(nums)):
11        # Remove indexes that are out of the current window
12        if deq and deq[0] < i - k + 1:
13            deq.popleft()
14        
15        # Remove elements from the deque that are smaller than the current element
16        while deq and nums[deq[-1]] < nums[i]:
17            deq.pop()
18        
19        # Add current element's index to the deque
20        deq.append(i)
21        
22        # Append the maximum element to the result list once the first window is complete
23        if i >= k - 1:
24            result.append(nums[deq[0]])
25    
26    return result
27
28# Example usage
29nums = [1, 3, -1, -3, 5, 3, 6, 7]
30k = 3
31print("Sliding window maximums:", maxSlidingWindow(nums, k))  # Output: [3, 3, 5, 5, 6, 7]

Explanation of the code

• Initialize Deque and Result List: The deque deq will store the indexes of useful elements, and result will store the maximum values for each window.
• Iterate Over the Array: For each element in nums, we:
  • Remove indexes from the deque that are out of the current window.
  • Remove elements from the back of the deque that are smaller than the current element since they are no longer useful.
  • Add the current element's index to the deque.
  • Append the maximum element (element at the front of the deque) to the result list once the first window is complete.
• Return the Result: The result list contains the maximum values for each window.

Time complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because each element is added and removed from the deque at most once.