# Sliding Window Maximum Problem is Not that Difficult

## Three approaches to solving the sliding window maximum problem

In this post, we are gonna discuss multiple solutions for **sliding window maximum** problem.

If you prefer to learn through videos, please have a look at the following video.

# Problem Statement

You are given an array of integers, 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:**

**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**

# Solution 1: Brute Force

Among all solutions, **Brute force** is the easiest one to understand. It moves sliding windows from left to right and searches the largest value for every window.

**Time:** `O(Nk)`

**Space:** `O(1)`

not including the output array

The Brute force solution uses almost no additional space. But it is the least efficient algorithm.

`def simple(nums, k):`

res = []

length = len(nums)

i = 0

while i < length-k+1:

mx = max(nums[i:i+k])

res.append(mx)

i +=1

return res

# Solution 2: Priority Queue

To find the greatest or smallest value in a shorter time, a **priority queue** is usually an good choice to consider.

We store `item = (value, index)`

pair inside the priority queue.

- The
`value`

is the**priority key**to compare - The
`index`

is useful to restrict window range

**Execution Steps:**

- Fill in
`k`

items into the heap first - Add the next item into the heap
- Dequeue the first item if the index of it is out of window range
- Repeat step 2 to 3

Here is the code：

import heapqclass Solution: def maxSlidingWindow(self, nums, k):

lens = len(nums)

h = []

res = []

for r in range(k):

heapq.heappush(h, (-nums[r],r))

res.append(-h[0][0])

for r in range(k, lens):

l = r-k+1

# window index range: l, l+1, ..., l+k-1

heapq.heappush(h, (-nums[r],r)) while h[0][1] <l or h[0][1] > l+k-1:

heapq.heappop(h)

res.append(-h[0][0])

return res

# Solution 3: Monotonic Deque

**Deques** are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”)

A **Monotonic Queue **is a data structure that keeps its elements either entirely in non-increasing, or entirely in non-decreasing order.

Monotonic deque has three basic operations:

**Push**: add an element into the queue**Pop:**remove an element from either end of the queue**max**: peek the max element in O(1）

Here is the code

from collections import dequeclass Solution: def maxSlidingWindow(self, nums, k):

res = []

d = deque([])

for r in range(len(nums)):

# remove item outside the window

# 1. if first index in Q(Deque) < i-k+1

if d and d[0][1] < r-k+1:

d.popleft()

# 2. a new bigger item comes

while d and nums[r] >= d[0][0]:

d.popleft()

# keep Monotonic

while d and nums[r] > d[-1][0]:

d.pop()

d.append((nums[r],r))

if r >= k-1:

res.append(d[0][0])

return res

If you liked this article, please clap so others can see it. 💚