Sliding Window Maximum

▶

Steps

setup

Initialize variables

Initialize an empty deque to store indices and an empty result list to store maximums.

💡 Starting with empty structures is essential to build the monotonic deque and collect results.

Line:

dq = deque()
result = []

💡 The deque will hold indices, not values, to efficiently check window boundaries.

fill_cells

Process element at index 0 (value 1)

Start processing the first element (1). Since the deque is empty, push index 0 onto the deque.

💡 The first element always gets added as a candidate maximum for the first window.

Line:

dq.append(i)  # i=0

💡 Deque now contains index 0, representing the first element as a potential maximum.

fill_cells

Process element at index 1 (value 3), pop smaller elements and push current

Process element 3 at index 1. Since 3 > nums[dq[-1]] (which is 1), pop index 0 from the deque, then push index 1.

💡 We remove smaller elements from the back to maintain decreasing order in the deque, then add the current index.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=1

dq.append(i)  # i=1

💡 Smaller elements behind the current element cannot be maximum in any future window including current index. Deque now holds index 1.

fill_cells

Process element at index 2 (value -1), no pops, then push current

Process element -1 at index 2. Since -1 < nums[dq[-1]] (3), no elements are popped. Then push index 2.

💡 Smaller elements behind current index remain candidates for maximum in future windows.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=2

dq.append(i)  # i=2

💡 Deque now contains indices [1, 2] with values [3, -1].

compare

Window formed, append max for window ending at index 2

Window [0..2] is full. Append nums[dq[0]] = nums[1] = 3 to result as max of first window.

💡 The front of the deque always holds the index of the max element for the current window.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])  # i=2

💡 Result list now contains [3].

fill_cells

Process element at index 3 (value -3), no pops, then push current

Process element -3 at index 3. Since -3 < nums[dq[-1]] (-1), no pops from deque. Then push index 3.

💡 Smaller elements remain candidates for maximum in future windows.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=3

dq.append(i)  # i=3

💡 Deque now contains [1, 2, 3] with values [3, -1, -3].

shrink_and_compare

Remove index out of window (index 0) from front and append max for window ending at index 3

Index 0 is out of the current window [1..3], so remove it if at front. It is not at front, so no removal. Then append nums[dq[0]] = nums[1] = 3 to result.

💡 We only remove from front if the index is out of the window to keep deque valid. The front of the deque is the max for the current window.

Line:

if dq[0] == i - k:
    dq.popleft()  # i=3

if i >= k - 1:
    result.append(nums[dq[0]])  # i=3

💡 Deque remains [1, 2, 3]. Result list now contains [3, 3].

fill_cells

Process element at index 4 (value 5), pop smaller elements and push current

Process element 5 at index 4. Pop indices 3, 2, and 1 from back because their values (-3, -1, 3) are less than 5. Then push index 4.

💡 Remove all smaller elements behind current to maintain decreasing order, then add current index.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=4

dq.append(i)  # i=4

💡 All smaller elements behind 5 are removed as they cannot be max in future windows. Deque now contains [4].

shrink_and_compare

Remove index out of window (index 1) from front and append max for window ending at index 4

Check if front index 4 equals i-k=1. It does not, so no removal. Then append nums[dq[0]] = nums[4] = 5 to result.

💡 Only remove front if it is out of the current window. Front of deque is max for current window.

Line:

if dq[0] == i - k:
    dq.popleft()  # i=4

if i >= k - 1:
    result.append(nums[dq[0]])  # i=4

💡 Deque remains [4]. Result list now contains [3, 3, 5].

fill_cells

Process element at index 5 (value 3), no pops, then push current

Process element 3 at index 5. Since 3 < nums[dq[-1]] (5), no pops. Then push index 5.

💡 Smaller elements remain candidates for future windows.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=5

dq.append(i)  # i=5

💡 Deque now contains [4, 5] with values [5, 3].

shrink_and_compare

Remove index out of window (index 2) from front and append max for window ending at index 5

Check if front index 4 equals i-k=2. It does not, so no removal. Then append nums[dq[0]] = nums[4] = 5 to result.

💡 Only remove front if it is out of the current window. Front of deque is max for current window.

Line:

if dq[0] == i - k:
    dq.popleft()  # i=5

if i >= k - 1:
    result.append(nums[dq[0]])  # i=5

💡 Deque remains [4, 5]. Result list now contains [3, 3, 5, 5].

fill_cells

Process element at index 6 (value 6), pop smaller elements and push current

Process element 6 at index 6. Pop indices 5 and 4 from back because their values (3, 5) are less than 6. Then push index 6.

💡 Remove smaller elements behind current to maintain decreasing order, then add current index.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=6

dq.append(i)  # i=6

💡 Smaller elements behind 6 removed as they cannot be max in future windows. Deque now contains [6].

shrink_and_compare

Remove index out of window (index 3) from front and append max for window ending at index 6

Check if front index 6 equals i-k=3. It does not, so no removal. Then append nums[dq[0]] = nums[6] = 6 to result.

💡 Only remove front if it is out of the current window. Front of deque is max for current window.

Line:

if dq[0] == i - k:
    dq.popleft()  # i=6

if i >= k - 1:
    result.append(nums[dq[0]])  # i=6

💡 Deque remains [6]. Result list now contains [3, 3, 5, 5, 6].

fill_cells

Process element at index 7 (value 7), pop smaller elements and push current

Process element 7 at index 7. Pop index 6 from back because 6 < 7. Then push index 7.

💡 Remove smaller elements behind current to maintain decreasing order, then add current index.

Line:

while dq and nums[dq[-1]] < nums[i]:
    dq.pop()  # i=7

dq.append(i)  # i=7

💡 Smaller element behind 7 removed. Deque now contains [7].

shrink_and_compare

Remove index out of window (index 4) from front and append max for window ending at index 7

Check if front index 7 equals i-k=4. It does not, so no removal. Then append nums[dq[0]] = nums[7] = 7 to result.

💡 Only remove front if it is out of the current window. Front of deque is max for current window.

Line:

if dq[0] == i - k:
    dq.popleft()  # i=7

if i >= k - 1:
    result.append(nums[dq[0]])  # i=7

💡 Deque remains [7]. Result list now contains [3, 3, 5, 5, 6, 7].

from typing import List
from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dq = deque()  # stores indices
    result = []
    for i in range(n):  # STEP 2 to 15
        while dq and nums[dq[-1]] < nums[i]:  # STEP 3,8,12,14
            dq.pop()  # remove smaller elements
        dq.append(i)  # STEP 3,4,6,8,10,12,14
        if dq[0] == i - k:  # STEP 7,9,11,13,15
            dq.popleft()  # remove out of window
        if i >= k - 1:  # STEP 5,7,9,11,13,15
            result.append(nums[dq[0]])
    return result

if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

📊

Sliding Window Maximum - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation on the deque reveals how the algorithm keeps track of potential maximums and discards irrelevant elements.

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

0

↑ pushed: 0

popElement[1]: 3

Stack (top→bottom)

1

↓ popped: [0]

pushElement[2]: -1

Stack (top→bottom)

2

1

↑ pushed: 2

no_opElement[2]: -1

Stack (top→bottom)

2

1

Contributes: 3

pushElement[3]: -3

Stack (top→bottom)

3

2

1

↑ pushed: 3

no_opElement[3]: -3

Stack (top→bottom)

3

2

1

Contributes: 3

popElement[4]: 5

Stack (top→bottom)

4

↓ popped: [3, 2, 1]

no_opElement[4]: 5

Stack (top→bottom)

4

Contributes: 5

pushElement[5]: 3

Stack (top→bottom)

5

4

↑ pushed: 5

no_opElement[5]: 3

Stack (top→bottom)

5

4

Contributes: 5

popElement[6]: 6

Stack (top→bottom)

6

↓ popped: [5, 4]

no_opElement[6]: 6

Stack (top→bottom)

6

Contributes: 6

popElement[7]: 7

Stack (top→bottom)

7

↓ popped: [6]

no_opElement[7]: 7

Stack (top→bottom)

7

Contributes: 7

Key Takeaways

✓ The deque always stores indices of elements in decreasing order of their values.

This property ensures the front of the deque is always the maximum for the current window.

✓ Elements smaller than the current element are popped from the back before pushing the current index.

This step removes elements that cannot be maximum in any future window including the current element.

✓ Indices that fall out of the current window are removed from the front of the deque.

This keeps the deque valid and ensures the maximum corresponds to the current sliding window.

Practice

1. Given the following Python code implementing the optimal stack-less calculator, what is the final returned value when the input string is "3+2*2"?

easy

A. 5

B. 10

C. 8

D. 7

Solution

1. Step 1: Trace first number and operator

   Read '3', current_op='+', total=0, last_num=0. On '+', total += last_num (0), last_num=3.

2. Step 2: Process '2*2'

   Read '2', operator '*', current_op='+', so total += last_num (3), last_num=2. Then read '2' after '*', current_op='*', last_num=2*2=4.

3. Step 3: End of string

   Add last_num (4) to total (3), total=7.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   3 + (2*2) = 7 matches traced total [OK]

Hint: Multiplication evaluated before addition, total accumulates last_num [OK]

Common Mistakes:

• Adding numbers before multiplication
• Off-by-one in loop end
• Not adding last_num at end

2. Given an integer array, you need to find the sum of the minimum values of all possible contiguous subarrays. Which algorithmic approach guarantees an optimal O(n) time complexity solution?

easy

A. Monotonic stack to find previous less and next less elements for each array element

B. Greedy approach selecting minimum elements from left to right

C. Dynamic programming with memoization of subarray minimums

D. Brute force nested loops checking all subarrays and their minimums

Solution

1. Step 1: Understand problem constraints

   The problem requires summing minimums of all subarrays efficiently, which brute force cannot do in O(n).

2. Step 2: Identify the pattern

   Monotonic stack helps find previous less and next less elements in O(n), enabling counting subarrays where each element is minimum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack finds boundaries for minimums in O(n) [OK]

Common Mistakes:

• Assuming greedy or DP solves this in O(n)
• Confusing with maximum subarray problems

3. What is the time complexity of the optimized monotonic stack solution for the sum of subarray minimums problem, and why?

medium

A. O(n log n) due to sorting or binary search inside the stack operations

B. O(n^2) because each element can be pushed and popped multiple times

C. O(n) because each element is pushed and popped at most once

D. O(n) but with O(n^2) auxiliary space for storing subarray minimums

Solution

1. Step 1: Identify stack operations per element

   Each element is pushed once and popped once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops or extra sorting

   The algorithm uses a single pass with a stack, no sorting or nested loops, so time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack guarantees linear time complexity [OK]

Hint: Each element pushed and popped once -> O(n) time [OK]

Common Mistakes:

• Assuming multiple pops per element cause O(n^2)
• Confusing with sorting-based methods

4. Suppose the calculator must now support expressions where numbers can be reused multiple times (e.g., "2*2*2") and the input length can be very large. Which modification to the optimal approach is necessary to handle this efficiently?

hard

A. Switch to a brute force left-to-right evaluation ignoring precedence to reduce complexity.

B. Implement memoization to cache results of subexpressions to avoid recomputation.

C. Use a stack to immediately evaluate multiplication and division, but keep track of last_num to handle repeated operations efficiently.

D. Use recursion with backtracking to explore all possible reuse combinations.

Solution

1. Step 1: Understand reuse impact

   Repeated multiplication/division requires immediate evaluation to maintain precedence and efficiency.

2. Step 2: Identify suitable approach

   Using a stack or stack-like variables to immediately compute * and / handles repeated operations efficiently without extra overhead.

3. Step 3: Reject alternatives

   Brute force ignores precedence, memoization is unnecessary for linear evaluation, recursion/backtracking is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Immediate evaluation with stack variables handles reuse and large inputs efficiently [OK]

Hint: Immediate evaluation with stack variables handles repeated ops efficiently [OK]

Common Mistakes:

• Ignoring precedence in reuse
• Using recursion unnecessarily
• Trying brute force for efficiency

5. Suppose the problem changes so that elements in the array can be negative integers. Which modification to the monotonic stack approach is necessary to correctly compute the sum of subarray minimums?

hard

A. Add a sentinel element with value 0 at the end to ensure stack empties correctly

B. No change needed; the existing monotonic stack approach works for negative values

C. Use a different data structure like a balanced BST to handle negative values

D. Modify the comparison to use <= instead of < to handle negative duplicates

Solution

1. Step 1: Analyze effect of negative values on monotonic stack

   The monotonic stack approach relies on relative ordering, which holds regardless of sign.

2. Step 2: Confirm no structural changes needed

   Sentinel and strict < comparison still work; negative values do not break the logic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack handles negatives without modification [OK]

Hint: Monotonic stack compares values, sign does not affect correctness [OK]

Common Mistakes:

• Assuming negative values require different data structures
• Changing comparison operators unnecessarily