Skip to main content

Sliding Window Maximum Tracker

medium
QueueDequeSliding WindowMonotonic QueueMonotonic QueueSliding Window
Asked atAmazonGoogleMicrosoftBloomberg

Problem Description

Given an integer array `readings` of length `n` and a positive integer `windowSize`, a sliding window of size `windowSize` moves from the left edge of the array to the right edge, one step at a time.

For each position of the window, find the **maximum value** among the elements currently inside it.

Return an array containing all the per-window maximums in order.

**Example 1:**
```
Input: readings = [4, 1, 7, 3, 8, 2, 6], windowSize = 3
Output: [7, 7, 8, 8, 8, 6]
Explanation:
Window [4,1,7] → max 7
Window [1,7,3] → max 7
Window [7,3,8] → max 8
Window [3,8,2] → max 8
Window [8,2,6] → max 8 ← 8 exits, 6 enters → still 8 for [8,2,6]
Wait: [8,2,6] max = 8
```

**Example 2:**
```
Input: readings = [9, 5, 3, 11, 2], windowSize = 2
Output: [9, 5, 11, 11]
Explanation:
Window [9,5] → max 9
Window [5,3] → max 5
Window [3,11] → max 11
Window [11,2] → max 11
```

Constraints

  • 1 <= readings.length <= 10^5
  • 1 <= windowSize <= readings.length
  • -10^4 <= readings[i] <= 10^4

Follow-up

Can you also return the **minimum** of each window simultaneously, using two deques, in a single O(n) pass?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.