Coding Patterns
Queue
Problems

Problems

Put your queue knowledge to the test with these curated LeetCode problems. Start from the top and work your way through. Refer to our Code Templates for reusable implementations.

Easy Problems

1. Implement Queue using Stacks

  • Brief: Implement a FIFO queue using only two stacks.
  • Why this pattern?: Shows how to convert LIFO to FIFO structure using two stacks as temporary storage.
  • Key Insight: When the output stack is empty, transfer all elements from input stack. This reverses the order, giving us FIFO behavior.
  graph TD
    subgraph Operation["Push 1, 2, 3"]
        A[Input Stack: 1, 2, 3] --> B[Pop]
    end

    subgraph Transfer["Transfer to Output"]
        B --> C[Output Stack: 3, 2, 1]
    end

    subgraph Result["Pop Operations"]
        C --> D[Returns 1]
        D --> E[Returns 2]
    end

class MyQueue {
    constructor() {
        this.inStack = [];
        this.outStack = [];
    }

    push(x) {
        this.inStack.push(x);
    }

    pop() {
        this._moveToOutStack();
        return this.outStack.pop();
    }

    peek() {
        this._moveToOutStack();
        return this.outStack[this.outStack.length - 1];
    }

    empty() {
        return this.inStack.length === 0 && this.outStack.length === 0;
    }

    _moveToOutStack() {
        if (this.outStack.length === 0) {
            while (this.inStack.length > 0) {
                this.outStack.push(this.inStack.pop());
            }
        }
    }
}
class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self._move_to_out_stack()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._move_to_out_stack()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return len(self.in_stack) == 0 and len(self.out_stack) == 0

    def _move_to_out_stack(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
import java.util.Stack;

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        moveToOutStack();
        return outStack.pop();
    }

    public int peek() {
        moveToOutStack();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void moveToOutStack() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}
#include <stack>

class MyQueue {
private:
    std::stack<int> inStack;
    std::stack<int> outStack;

    void moveToOutStack() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        moveToOutStack();
        int val = outStack.top();
        outStack.pop();
        return val;
    }

    int peek() {
        moveToOutStack();
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};
type MyQueue struct {
    inStack  []int
    outStack []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (q *MyQueue) Push(x int) {
    q.inStack = append(q.inStack, x)
}

func (q *MyQueue) Pop() int {
    q.moveToOutStack()
    val := q.outStack[len(q.outStack)-1]
    q.outStack = q.outStack[:len(q.outStack)-1]
    return val
}

func (q *MyQueue) Peek() int {
    q.moveToOutStack()
    return q.outStack[len(q.outStack)-1]
}

func (q *MyQueue) Empty() bool {
    return len(q.inStack) == 0 && len(q.outStack) == 0
}

func (q *MyQueue) moveToOutStack() {
    if len(q.outStack) == 0 {
        for len(q.inStack) > 0 {
            n := len(q.inStack) - 1
            q.outStack = append(q.outStack, q.inStack[n])
            q.inStack = q.inStack[:n]
        }
    }
}
class MyQueue
  def initialize
    @in_stack = []
    @out_stack = []
  end

  def push(x)
    @in_stack.push(x)
  end

  def pop
    move_to_out_stack
    @out_stack.pop
  end

  def peek
    move_to_out_stack
    @out_stack.last
  end

  def empty
    @in_stack.empty? && @out_stack.empty?
  end

  private

  def move_to_out_stack
    if @out_stack.empty?
      until @in_stack.empty?
        @out_stack.push(@in_stack.pop)
      end
    end
  end
end

Time Complexity: Amortized

O(1)
for push,
O(1)
for pop/peek/empty | Space Complexity:
O(n)

2. Number of Recent Calls

  • Brief: Count the number of calls in the last 3000 milliseconds.
  • Why this pattern?: Queue naturally handles time-based sliding window by removing expired timestamps.
  • Key Insight: Maintain timestamps in queue, removing those outside the 3000ms window before counting.
  sequenceDiagram
    participant Queue as Queue
    participant Time as Current Time

    Queue->>Time: t=100, push<br/>Queue: [100]
    Queue->>Time: t=3001, remove<br/>Queue: []
    Queue->>Time: t=3002, push<br/>Queue: [3002]

    Note over Queue: Window: t-3000 to t

class RecentCounter {
    constructor() {
        this.requests = [];
    }

    ping(t) {
        this.requests.push(t);

        while (this.requests.length > 0 && this.requests[0] < t - 3000) {
            this.requests.shift();
        }

        return this.requests.length;
    }
}
from collections import deque

class RecentCounter:
    def __init__(self):
        self.requests = deque()

    def ping(self, t: int) -> int:
        self.requests.append(t)

        while self.requests and self.requests[0] < t - 3000:
            self.requests.popleft()

        return len(self.requests)
import java.util.LinkedList;
import java.util.Queue;

class RecentCounter {
    private Queue<Integer> requests;

    public RecentCounter() {
        requests = new LinkedList<>();
    }

    public int ping(int t) {
        requests.offer(t);

        while (requests.peek() < t - 3000) {
            requests.poll();
        }

        return requests.size();
    }
}
#include <queue>

class RecentCounter {
private:
    std::queue<int> requests;

public:
    RecentCounter() {}

    int ping(int t) {
        requests.push(t);

        while (requests.front() < t - 3000) {
            requests.pop();
        }

        return requests.size();
    }
};
type RecentCounter struct {
    requests []int
}

func Constructor() RecentCounter {
    return RecentCounter{}
}

func (rc *RecentCounter) Ping(t int) int {
    rc.requests = append(rc.requests, t)

    for len(rc.requests) > 0 && rc.requests[0] < t-3000 {
        rc.requests = rc.requests[1:]
    }

    return len(rc.requests)
}
class RecentCounter
  def initialize
    @requests = []
  end

  def ping(t)
    @requests.push(t)

    while @requests.any? && @requests.first < t - 3000
      @requests.shift
    end

    @requests.length
  end
end

Time Complexity:

O(n)
worst case, amortized
O(1)
| Space Complexity:
O(n)

Medium Problems

3. Binary Tree Level Order Traversal

  • Brief: Return the level order traversal of a binary tree’s nodes’ values.
  • Why this pattern?: Queue naturally processes nodes level by level in BFS fashion.
  • Key Insight: Track level boundaries using queue size before processing each level.
  graph TD
    subgraph Tree
        root[3] --> left1[9]
        root --> right1[20]
        right1 --> left2[15]
        right1 --> right2[7]
    end

    subgraph BFS["BFS Order"]
        A[Level 0: 3] --> B[Level 1: 9, 20]
        B --> C[Level 2: 15, 7]
    end

    style root fill:#f9f,stroke:#333

function levelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
}
from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }
}
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;

        std::queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            std::vector<int> currentLevel;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            result.push_back(currentLevel);
        }

        return result;
    }
};
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            currentLevel = append(currentLevel, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, currentLevel)
    }

    return result
}
class TreeNode
  attr_accessor :val, :left, :right

  def initialize(val = 0, left = nil, right = nil)
    @val = val
    @left = left
    @right = right
  end
end

def level_order(root)
  result = []
  return result unless root

  queue = [root]

  while !queue.empty?
    level_size = queue.size
    current_level = []

    level_size.times do
      node = queue.shift
      current_level << node.val

      queue << node.left if node.left
      queue << node.right if node.right
    end

    result << current_level
  end

  result
end

Time Complexity:

O(n)
where n is number of nodes | Space Complexity:
O(n)

4. Open the Lock

  • Brief: Find the minimum number of turns to open a 4-wheel lock, avoiding deadends.
  • Why this pattern?: BFS guarantees shortest path in unweighted state space graph.
  • Key Insight: Treat each lock combination as a node, generate neighbors by turning each wheel up/down.
  graph TD
    A["0000"] --> B["1000"]
    A --> C["0001"]
    A --> D["0010"]
    A --> E["0100"]
    B --> F["2000"]
    B --> G["0000"]

function openLock(deadends, target) {
    const dead = new Set(deadends);
    const visited = new Set();
    const queue = [['0000', 0]];

    if (dead.has('0000')) return -1;

    while (queue.length > 0) {
        const [combination, moves] = queue.shift();

        if (combination === target) return moves;
        if (visited.has(combination)) continue;
        if (dead.has(combination)) continue;

        visited.add(combination);

        for (let i = 0; i < 4; i++) {
            for (const delta of [-1, 1]) {
                const newDigit = String((parseInt(combination[i]) + delta + 10) % 10);
                const newCombo = combination.slice(0, i) + newDigit + combination.slice(i + 1);
                queue.push([newCombo, moves + 1]);
            }
        }
    }

    return -1;
}
from collections import deque

def openLock(deadends: list[str], target: str) -> int:
    dead = set(deadends)
    visited = set()
    queue = deque([("0000", 0)])

    if "0000" in dead:
        return -1

    while queue:
        combination, moves = queue.popleft()

        if combination == target:
            return moves
        if combination in visited:
            continue
        if combination in dead:
            continue

        visited.add(combination)

        for i in range(4):
            for delta in [-1, 1]:
                new_digit = str((int(combination[i]) + delta) % 10)
                new_combo = combination[:i] + new_digit + combination[i+1:]
                queue.append((new_combo, moves + 1))

    return -1
import java.util.*;

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        Set<String> visited = new HashSet<>();
        Queue<String[]> queue = new LinkedList<>();
        queue.offer(new String[]{"0000", "0"});

        if (dead.contains("0000")) return -1;

        while (!queue.isEmpty()) {
            String[] curr = queue.poll();
            String combination = curr[0];
            int moves = Integer.parseInt(curr[1]);

            if (combination.equals(target)) return moves;
            if (visited.contains(combination)) continue;
            if (dead.contains(combination)) continue;

            visited.add(combination);

            for (int i = 0; i < 4; i++) {
                for (int delta : new int[]{-1, 1}) {
                    int newDigit = (combination.charAt(i) - '0' + delta + 10) % 10;
                    String newCombo = combination.substring(0, i) + newDigit + combination.substring(i + 1);
                    queue.offer(new String[]{newCombo, String.valueOf(moves + 1)});
                }
            }
        }

        return -1;
    }
}
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        queue<pair<string, int>> q;
        q.push({"0000", 0});

        if (dead.count("0000")) return -1;

        while (!q.empty()) {
            auto [combination, moves] = q.front();
            q.pop();

            if (combination == target) return moves;
            if (visited.count(combination)) continue;
            if (dead.count(combination)) continue;

            visited.insert(combination);

            for (int i = 0; i < 4; i++) {
                for (int delta : {-1, 1}) {
                    int newDigit = (combination[i] - '0' + delta + 10) % 10;
                    string newCombo = combination;
                    newCombo[i] = '0' + newDigit;
                    q.push({newCombo, moves + 1});
                }
            }
        }

        return -1;
    }
};
func openLock(deadends []string, target string) int {
    dead := make(map[string]bool)
    for _, d := range deadends {
        dead[d] = true
    }

    visited := make(map[string]bool)
    queue := [][2]string{{"0000", "0"}}

    if dead["0000"] {
        return -1
    }

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        combination := curr[0]
        moves, _ := strconv.Atoi(curr[1])

        if combination == target {
            return moves
        }
        if visited[combination] {
            continue
        }
        if dead[combination] {
            continue
        }

        visited[combination] = true

        for i := 0; i < 4; i++ {
            for _, delta := range []int{-1, 1} {
                newDigit := (int(combination[i]-'0')+delta+10) % 10
                newCombo := combination[:i] + string(rune('0'+newDigit)) + combination[i+1:]
                queue = append(queue, [2]string{newCombo, strconv.Itoa(moves + 1)})
            }
        }
    }

    return -1
}
def open_lock(deadends, target)
  dead = deadends.to_set
  visited = Set.new
  queue = [["0000", 0]]

  return -1 if dead.include?("0000")

  while !queue.empty?
    combination, moves = queue.shift

    return moves if combination == target
    next if visited.include?(combination)
    next if dead.include?(combination)

    visited.add(combination)

    4.times do |i|
      [-1, 1].each do |delta|
        new_digit = (combination[i].to_i + delta) % 10
        new_combo = combination[0...i] + new_digit.to_s + combination[i+1..]
        queue << [new_combo, moves + 1]
      end
    end
  end

  -1
end

Time Complexity:

O(1)
bounded by 10,000 possible states | Space Complexity:
O(1)

5. Course Schedule II

  • Brief: Find the ordering of courses to take given prerequisites.
  • Why this pattern?: Kahn’s algorithm uses queue to process nodes with zero indegree one by one.
  • Key Insight: Queue stores courses with no prerequisites; process them and decrement dependents’ indegree.
  graph TD
    subgraph Courses["Courses and Prerequisites"]
        C0[0: indegree 0] -.-> C1[1]
        C0 -.-> C2[2]
        C1[1: indegree 1] -.-> C3[3]
        C2[2: indegree 1] -.-> C3[3]
        C3[3: indegree 2]
    end

    subgraph Queue["Processing Order"]
        Q0[Queue: 0] --> Q1[Queue: 1, 2] --> Q2[Queue: 3]
    end

    style C0 fill:#9f9,stroke:#333

function findOrder(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    const result = [];

    while (queue.length > 0) {
        const course = queue.shift();
        result.push(course);

        for (const dependent of graph[course]) {
            indegree[dependent]--;
            if (indegree[dependent] === 0) {
                queue.push(dependent);
            }
        }
    }

    return result.length === numCourses ? result : [];
}
from collections import deque
from typing import List

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    result = []

    while queue:
        course = queue.popleft()
        result.append(course)

        for dependent in graph[course]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                queue.append(dependent)

    return result if len(result) == numCourses else []
import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        int[] indegree = new int[numCourses];
        for (int[] prereq : prerequisites) {
            graph.get(prereq[1]).add(prereq[0]);
            indegree[prereq[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] result = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[index++] = course;

            for (int dependent : graph.get(course)) {
                indegree[dependent]--;
                if (indegree[dependent] == 0) {
                    queue.offer(dependent);
                }
            }
        }

        return index == numCourses ? result : new int[0];
    }
}
#include <vector>
#include <queue>
#include <unordered_map>

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);

        for (auto& prereq : prerequisites) {
            graph[prereq[1]].push_back(prereq[0]);
            indegree[prereq[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> result;
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            result.push_back(course);

            for (int dependent : graph[course]) {
                indegree[dependent]--;
                if (indegree[dependent] == 0) {
                    q.push(dependent);
                }
            }
        }

        return result.size() == numCourses ? result : vector<int>();
    }
};
func findOrder(numCourses int, prerequisites [][]int) []int {
    graph := make([][]int, numCourses)
    indegree := make([]int, numCourses)

    for _, prereq := range prerequisites {
        graph[prereq[1]] = append(graph[prereq[1]], prereq[0])
        indegree[prereq[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    result := []int{}
    for len(queue) > 0 {
        course := queue[0]
        queue = queue[1:]
        result = append(result, course)

        for _, dependent := range graph[course] {
            indegree[dependent]--
            if indegree[dependent] == 0 {
                queue = append(queue, dependent)
            }
        }
    }

    if len(result) == numCourses {
        return result
    }
    return []int{}
}
def find_order(num_courses, prerequisites)
  graph = Array.new(num_courses) { [] }
  indegree = Array.new(num_courses, 0)

  prerequisites.each do |course, prereq|
    graph[prereq] << course
    indegree[course] += 1
  end

  queue = (0...num_courses).select { |i| indegree[i] == 0 }
  result = []

  until queue.empty?
    course = queue.shift
    result << course

    graph[course].each do |dependent|
      indegree[dependent] -= 1
      queue << dependent if indegree[dependent] == 0
    end
  end

  result.length == num_courses ? result : []
end

Time Complexity:

O(V + E)
where V = courses, E = prerequisites | Space Complexity:
O(V + E)

Hard Problems

6. Sliding Window Maximum

  • Brief: Find maximum element in each sliding window of size k.
  • Why this pattern?: Monotonic deque maintains decreasing order, giving O(1) access to max.
  • Key Insight: Store indices in deque; remove out-of-window indices and smaller elements from back.
  sequenceDiagram
    participant D as Deque
    participant W as Window

    W->>D: Process 3<br/>Deque: [0]
    W->>D: Process 1<br/>Deque: [0]
    W->>D: Process 3<br/>Deque: [0, 2]
    W->>D: Window complete<br/>Max: nums[0] = 3
    W->>D: Process -2<br/>Deque: [0, 2, 3]

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = [];

    for (let i = 0; i < nums.length; i++) {
        while (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }

        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}
from collections import deque
from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    result = []
    dq = deque()

    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()

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

        dq.append(i)

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

    return result
import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}
#include <vector>
#include <deque>

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;

        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }

            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }

        return result;
    }
};
func maxSlidingWindow(nums []int, k int) []int {
    result := []int{}
    dq := []int{}

    for i, num := range nums {
        for len(dq) > 0 && dq[0] < i-k+1 {
            dq = dq[1:]
        }

        for len(dq) > 0 && nums[dq[len(dq)-1]] <= num {
            dq = dq[:len(dq)-1]
        }

        dq = append(dq, i)

        if i >= k-1 {
            result = append(result, nums[dq[0]])
        }
    }

    return result
}
def max_sliding_window(nums, k)
  result = []
  dq = []

  nums.each_with_index do |num, i|
    while !dq.empty? && dq.first < i - k + 1
      dq.shift
    end

    while !dq.empty? && nums[dq.last] <= num
      dq.pop
    end

    dq.push(i)

    if i >= k - 1
      result << nums[dq.first]
    end
  end

  result
end

Time Complexity:

O(n)
| Space Complexity:
O(k)

Recommended Study Order

  1. Start with Implement Queue using Stacks to understand queue mechanics and LIFO to FIFO conversion.
  2. Move to Binary Tree Level Order Traversal to master the classic BFS queue pattern.
  3. Tackle Open the Lock to practice BFS on state spaces with visited tracking.
  4. Progress to Sliding Window Maximum for advanced monotonic deque technique.
  5. Finish with Course Schedule II to understand topological sorting with queue-based Kahn’s algorithm.
Pro Tip: When implementing BFS, always mark nodes as visited before adding them to the queue, not after removing them. This prevents the same node from being added multiple times and causing exponential memory usage.