Find Maximum in Sliding Window

Try to solve the Find Maximum in Sliding Window problem.

We'll cover the following

Statement#

Given an integer list, nums, find the maximum values in all the contiguous subarrays (windows) of size w.

Note: If the window size is greater than the array size, we consider the entire array as a single window.

Constraints:

  • 11 ≤\leq arr.length ≤\leq 10310^3
  • −104-10^4 ≤\leq arr[i] ≤\leq 10410^4
  • 11 ≤\leq w

Examples#

Created with Fabric.js 3.6.6 Output Input window size 3 nums -4 2 -5 3 6 Output 2 3 6 Sample example 1

1 of 3

Created with Fabric.js 3.6.6 Output Input nums 1 2 3 4 5 6 Output 6 window size 6 Sample example 2

2 of 3

Created with Fabric.js 3.6.6 Output Input nums 1 2 3 4 5 6 7 8 9 10 window size 4 Output 4 5 6 7 8 9 10 Sample example 3

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Find Maximum in Sliding Window

1

What should be the output if the following input is given?

nums = [-4, 5, 4, -4, 4, 6, 7, 20]

w = 2

A)

[5, 4, 6, 20]

B)

[5, 20]

C)

[5, 5, 4, 4, 6, 7, 20]

D)

[5, 5, 4, 6, 6]

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize an empty deque data structure.

Iterate through the first w elements in the input array, performing cleanup operations on the deque to maintain a decreasing order of values.

Store the maximum value of the initial window.

Slide the window through the array, updating the deque and storing maximum values for each window.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Input #2
%0 node_01 1 node_11 2 node_21 3 node_31 4 node_41 5 node_51 6 node_61 7 node_71 8 node_81 9 node_91 10
Visualization for Input #1
Find Maximum in Sliding Window

Sliding Window: Introduction

Solution: Find Maximum in Sliding Window