Sliding Window Maximum

📋

Problem

Imagine monitoring the highest temperature in the last hour every minute to detect heat spikes instantly.

Given an integer array nums and an integer k, return an array of the maximum values of each sliding window of size k moving from left to right across nums.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^41 ≤ k ≤ nums.length

Edge cases: k = 1 → output is the original arrayAll elements are equal → output is array of that element repeatedk equals array length → output is single max of entire array

</>

IDE

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:public int[] maxSlidingWindow(int[] nums, int k)vector<int> maxSlidingWindow(vector<int>& nums, int k)function maxSlidingWindow(nums, k)

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    # Write your solution here
    pass

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    // Write your solution here
    return {};
}

function maxSlidingWindow(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Output missing max for some windows or incorrect max valuesNot removing indices from deque front when they fall out of the current window✅ Add condition to pop from front of deque if deque[0] < i - k + 1 inside the loop

Wrong: Output has repeated smaller values instead of maxNot maintaining deque in decreasing order, failing to pop smaller elements from back✅ While deque not empty and nums[i] >= nums[deque.back()], pop back before pushing i

Wrong: Output incorrect when k=1, not returning original arrayCode does not handle k=1 as a special case or general logic fails for window size 1✅ Return nums directly if k == 1 or ensure window logic works for k=1

Wrong: Code crashes or returns non-empty output on empty inputNo guard clause for empty input array✅ Add check at start: if not nums: return []

Wrong: Solution times out on large inputsUsing brute force O(n*k) or heap O(n log k) instead of O(n) monotonic deque✅ Implement monotonic deque approach with O(n) time complexity

✓

Test Cases

Focus on handling minimal and boundary inputs correctly before moving on.

Check your deque maintenance logic carefully to avoid off-by-one and ordering bugs.

Optimize your solution to O(n) time using a monotonic deque to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,3,-1,-3,5,3,6,7],"k":3}

Expected[3,3,5,5,6,7]

⏱ Performance - must finish in 2000ms

For each window of size 3, the maximums are: [1,3,-1] → 3, [3,-1,-3] → 3, [-1,-3,5] → 5, [-3,5,3] → 5, [5,3,6] → 6, [3,6,7] → 7

💡 Consider using a data structure that keeps track of maximums efficiently.

💡 A monotonic deque can maintain candidates for max in O(n) time.

💡 Push new elements and pop smaller ones from the back; pop front if out of window.

Why it failed: Output incorrect - likely not maintaining max correctly or window boundaries wrong. Fix by using a deque that stores indices and remove elements out of current window.

✓ Correctly computes sliding window maximum using monotonic deque.

t1_02basic

Input{"nums":[9,11,8,5,7,10],"k":2}

Expected[11,11,8,7,10]

⏱ Performance - must finish in 2000ms

Windows: [9,11] → 11, [11,8] → 11, [8,5] → 8, [5,7] → 7, [7,10] → 10

💡 Try sliding the window and updating max efficiently rather than recomputing each time.

💡 Use a deque to store indices of elements in decreasing order.

💡 Remove indices from front if they fall out of the window; remove smaller elements from back.

Why it failed: Wrong output - probably recomputing max naively or not removing outdated indices. Fix by maintaining deque with indices and popping front when out of window.

✓ Correctly handles sliding window max for different input sizes.

t2_01edge

Input{"nums":[],"k":1}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array returns empty output.

💡 Check how your code handles empty input arrays.

💡 Ensure no index errors occur when nums is empty.

💡 Return empty list immediately if nums is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a guard clause for empty nums.

✓ Handles empty input gracefully.

t2_02edge

Input{"nums":[5],"k":1}

Expected[5]

⏱ Performance - must finish in 2000ms

Single element window returns the element itself.

💡 When k=1, each element is its own window max.

💡 Check if your code handles k=1 as a special case or general case.

💡 Return nums directly if k=1 for efficiency.

Why it failed: Output incorrect for k=1, possibly due to window size handling. Fix by ensuring windows of size 1 return original elements.

✓ Correctly returns original array when k=1.

t2_03edge

Input{"nums":[2,2,2,2],"k":2}

Expected[2,2,2]

⏱ Performance - must finish in 2000ms

All elements equal, max in each window is the same element.

💡 Check if your deque handles equal elements correctly.

💡 Ensure you do not remove equal elements prematurely from deque.

💡 Maintain non-increasing order in deque including equal values.

Why it failed: Deque removes equal elements incorrectly causing wrong max. Fix by allowing equal elements to remain in deque.

✓ Handles all-equal elements correctly.

t3_01corner

Input{"nums":[1,3,1,2,0,5],"k":3}

Expected[3,3,2,5]

⏱ Performance - must finish in 2000ms

Tests correct removal of elements outside window and maintaining max correctly.

💡 Check if you remove indices from front when they fall out of the window.

💡 Verify deque front always corresponds to current window max index.

💡 Pop front indices when they are less than i-k+1.

Why it failed: Output wrong due to not removing outdated indices from deque front. Fix by popping front indices when they are out of current window range.

✓ Correctly removes outdated indices and maintains max.

t3_02corner

Input{"nums":[4,3,2,1,0],"k":2}

Expected[4,3,2,1]

⏱ Performance - must finish in 2000ms

Descending order input tests if code handles decreasing sequences correctly.

💡 Check if your deque correctly removes smaller elements from back.

💡 Ensure monotonic decreasing order of values in deque is maintained.

💡 Pop from back while current element is greater or equal.

Why it failed: Deque not maintained in decreasing order causing wrong max. Fix by popping smaller elements from back before pushing new element.

✓ Handles descending sequences correctly.

t3_03corner

Input{"nums":[1,3,1,3,1,3],"k":2}

Expected[3,3,3,3,3]

⏱ Performance - must finish in 2000ms

Alternating pattern tests if code handles repeated max values correctly.

💡 Check if equal max values are handled without removing prematurely.

💡 Ensure deque stores indices and compares values correctly.

💡 Maintain deque so max is always at front even with duplicates.

Why it failed: Code removes equal max values too early causing wrong output. Fix by allowing equal values to stay in deque until out of window.

✓ Correctly handles repeated max values in alternating pattern.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with k=50000 tests O(n) monotonic deque solution performance within 2 seconds.

💡 Brute force O(n*k) will time out for large n and k.

💡 Use a monotonic deque to achieve O(n) time complexity.

💡 Avoid nested loops and recomputing max for each window.

Why it failed: TLE due to O(n*k) or O(n log k) approach. Fix by implementing O(n) monotonic deque algorithm.

✓ Solution runs within time limit using O(n) monotonic deque approach.

Practice

1. Given the following Python code for asteroid collision, what is the output when the input is [8, -8, 5, -10]?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

print(asteroidCollision([8, -8, 5, -10]))

easy

A. [5, -10]

B. [-10]

C. [8, 5, -10]

D. []

Solution

1. Step 1: Trace collision between 8 and -8

   8 and -8 are equal size but opposite direction, both explode -> stack empty.

2. Step 2: Process 5 and then -10

   5 is pushed; -10 collides with 5, since 10 > 5, 5 pops, -10 remains and is pushed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final stack contains only [-10] after resolving collisions [OK]

Hint: Equal size opposite asteroids both explode [OK]

Common Mistakes:

• Forgetting to pop both equal asteroids
• Appending asteroid after it exploded
• Not handling multiple collisions in while loop

2. You are given a list of tokens representing an arithmetic expression in postfix notation, where each token is either an integer or an operator (+, -, *, /). Which algorithmic approach guarantees an optimal and straightforward evaluation of this expression?

easy

A. Dynamic programming approach that stores intermediate results in a table indexed by token positions.

B. Greedy algorithm that evaluates tokens from left to right, applying operators as soon as possible without using extra data structures.

C. Stack-based iterative evaluation that pushes operands and applies operators by popping the last two operands from the stack.

D. Recursive backtracking that tries all possible ways to parenthesize the expression and selects the correct evaluation.

Solution

1. Step 1: Understand the problem structure

   Postfix expressions require operands to be processed before operators, which naturally fits a stack structure.

2. Step 2: Identify the correct approach

   Stack-based iterative evaluation pushes operands and pops two operands when an operator is encountered, applying the operator and pushing the result back.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Stack usage matches postfix evaluation logic [OK]

Hint: Postfix evaluation naturally uses a stack [OK]

Common Mistakes:

• Thinking greedy evaluation without stack works
• Confusing postfix with infix DP
• Using recursion without clear base cases

3. Consider the following Python code implementing the optimized next greater element algorithm. What is the final output when calling nextGreaterElement([4,1,2], [1,3,4,2])?

easy

A. [-1, -1, 3]

B. [-1, 3, -1]

C. [3, -1, -1]

D. [3, 4, -1]

Solution

1. Step 1: Trace stack and map updates for nums2

   Process nums2: push 1, then 3 > 1 so pop 1 -> map[1]=3; push 3; 4 > 3 pop 3 -> map[3]=4; push 4; 2 < 4 push 2. Stack ends with [4,2].

2. Step 2: Assign -1 for remaining stack elements and build result

   Pop 2 -> map[2]=-1; pop 4 -> map[4]=-1. Result for nums1=[4,1,2] is [map[4], map[1], map[2]] = [-1,3,-1].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches expected output from code comments and manual trace [OK]

Hint: Stack pops smaller elements when a bigger one arrives [OK]

Common Mistakes:

• Confusing order of popping leading to wrong map values
• Forgetting to assign -1 for elements with no next greater
• Mixing up indices when building the final result

4. What is the time complexity of the optimized stack simulation algorithm for the asteroid collision problem, given n asteroids in the input list?

medium

A. O(n) because each asteroid is pushed and popped at most once

B. O(n log n) due to sorting implicit in stack operations

C. O(n^2) because each asteroid can cause multiple pops in the stack

D. O(n) for iteration plus O(n) for auxiliary space, total O(n)

Solution

1. Step 1: Analyze iteration over asteroids

   The algorithm iterates over each asteroid once.

2. Step 2: Analyze stack operations

   Each asteroid can be pushed once and popped once, so total stack operations are O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each asteroid processed at most twice (push/pop) [OK]

Hint: Each asteroid pushed and popped once max [OK]

Common Mistakes:

• Assuming nested while loop causes O(n^2)
• Confusing stack operations with sorting
• Ignoring amortized analysis of stack pops

5. Identify the bug in the following circular queue implementation snippet:

medium

A. Line updating tail pointer should use modulo operation to wrap around.

B. Line checking if queue is full should compare head and tail pointers instead of size.

C. Line initializing queue should use an empty list instead of fixed-size array.

D. Line incrementing size should be before updating tail pointer.

Solution

1. Step 1: Examine tail pointer update

   Tail pointer increments by 1 but lacks modulo operation, so it can exceed array bounds.

2. Step 2: Understand consequences

   Without modulo, tail pointer goes out of range causing runtime errors or incorrect behavior.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modulo operation is essential for circular wrap-around [OK]

Hint: Tail pointer must wrap modulo capacity [OK]

Common Mistakes:

• Forgetting modulo wrap-around
• Using size incorrectly to check full
• Misordering size increment