Code Templates

These standardized code templates serve as memorizable blueprints for queue-related problems. Adapt these patterns to solve most queue challenges efficiently.

Ready to dive in? Check the Concept Guide for the theory behind these templates.

Main Template: BFS with Queue

This is the most common queue pattern - breadth-first search for level-order traversal and shortest path in unweighted graphs. This template directly solves problems like Binary Tree Level Order Traversal.

/**
 * BFS template using queue
 * Use for: level-order traversal, shortest path in unweighted graphs
 * Time: O(V + E) where V = vertices, E = edges
 * Space: O(V) for queue and visited set
 */
function bfs(graph, start) {
    const queue = [start];
    const visited = new Set([start]);

    while (queue.length > 0) {
        const node = queue.shift();

        // Process current node
        console.log(node);

        // Add unvisited neighbors to queue
        for (const neighbor of graph[node] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

"""
BFS template using queue
Use for: level-order traversal, shortest path in unweighted graphs
Time: O(V + E) where V = vertices, E = edges
Space: O(V) for queue and visited set
"""
from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([start])

    while queue:
        node = queue.popleft()

        # Process current node
        print(node)

        # Add unvisited neighbors to queue
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

/**
 * BFS template using queue
 * Use for: level-order traversal, shortest path in unweighted graphs
 * Time: O(V + E) where V = vertices, E = edges
 * Space: O(V) for queue and visited set
 */
import java.util.*;

public void bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();

        // Process current node
        System.out.println(node);

        // Add unvisited neighbors to queue
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

/**
 * BFS template using queue
 * Use for: level-order traversal, shortest path in unweighted graphs
 * Time: O(V + E) where V = vertices, E = edges
 * Space: O(V) for queue and visited set
 */
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <vector>

void bfs(std::unordered_map<int, std::vector<int>>& graph, int start) {
    std::queue<int> q;
    std::unordered_set<int> visited;

    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // Process current node
        std::cout << node << std::endl;

        // Add unvisited neighbors to queue
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

/**
 * BFS template using queue
 * Use for: level-order traversal, shortest path in unweighted graphs
 * Time: O(V + E) where V = vertices, E = edges
 * Space: O(V) for queue and visited set
 */
package queue

func bfs(graph map[int][]int, start int) {
    queue := []int{start}
    visited := make(map[int]bool)
    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        // Process current node
        fmt.Println(node)

        // Add unvisited neighbors to queue
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

# BFS template using queue
# Use for: level-order traversal, shortest path in unweighted graphs
# Time: O(V + E) where V = vertices, E = edges
# Space: O(V) for queue and visited set
def bfs(graph, start)
  queue = [start]
  visited = Set.new([start])

  while !queue.empty?
    node = queue.shift

    # Process current node
    puts node

    # Add unvisited neighbors to queue
    (graph[node] || []).each do |neighbor|
      unless visited.include?(neighbor)
        visited.add(neighbor)
        queue.push(neighbor)
      end
    end
  end
end

Code Breakdown

Key Components

Queue: Stores nodes to visit in FIFO order. When we discover a node, we add it to the back of the queue.
Visited Set: Tracks nodes we have already processed. This prevents revisiting nodes and infinite loops.
Graph: Adjacency list representation where each key is a node and value is its neighbors.

Processing Flow

  stateDiagram-v2
    [*] --> Initialize: Create queue, add start node, mark visited
    Initialize --> CheckQueue: Queue not empty?
    CheckQueue --> ProcessNode: Dequeue node
    ProcessNode --> VisitNeighbors: Process current node
    VisitNeighbors --> CheckNeighbor: For each neighbor
    CheckNeighbor --> AddToQueue: If not visited
    AddToQueue --> VisitNeighbors: Mark visited, enqueue
    CheckNeighbor --> CheckQueue: If visited
    CheckQueue --> [*]: Queue empty

Critical Sections

Initialization: Add the start node to queue and mark it as visited immediately. This prevents adding start node multiple times.

Queue Processing: Use a while loop that continues as long as queue is not empty. Dequeue one node at a time.

Neighbor Exploration: For each unvisited neighbor, mark it visited before enqueuing. This is the crucial step that prevents duplicates.

Variations

Level-Order Tree Traversal

When processing a binary tree level by level, use the queue size to track level boundaries.

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

def level_order(root):
    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.*;

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>

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;
}

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
}

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

Sliding Window Maximum with Monotonic Deque

Uses a deque to maintain elements in decreasing order, achieving O(n) time complexity for finding maximum in each sliding window.

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // Stores indices, maintains decreasing order

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

        // Remove indices of smaller elements from back
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        // Add to result when window is complete
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

from collections import deque

def max_sliding_window(nums, k):
    result = []
    dq = deque()  # Stores indices, maintains decreasing order

    for i, num in enumerate(nums):
        # Remove indices outside current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove indices of smaller elements from back
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        dq.append(i)

        # Add to result when window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

import java.util.*;

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

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

        // Remove indices of smaller elements from back
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // Add to result when window is complete
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }

    return result;
}

#include <vector>
#include <deque>

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::vector<int> result;
    std::deque<int> dq; // Stores indices

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

        // Remove indices of smaller elements from back
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // Add to result when window is complete
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

func maxSlidingWindow(nums []int, k int) []int {
    result := []int{}
    dq := []int{} // Stores indices

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

        // Remove indices of smaller elements from back
        for len(dq) > 0 && nums[dq[len(dq)-1]] <= num {
            dq = dq[:len(dq)-1]
        }

        dq = append(dq, i)

        // Add to result when window is complete
        if i >= k-1 {
            result = append(result, nums[dq[0]])
        }
    }

    return result
}

def max_sliding_window(nums, k)
  result = []
  dq = []  # Stores indices

  nums.each_with_index do |num, i|
    # Remove indices outside current window
    while !dq.empty? && dq.first < i - k + 1
      dq.shift
    end

    # Remove indices of smaller elements from back
    while !dq.empty? && nums[dq.last] <= num
      dq.pop
    end

    dq.push(i)

    # Add to result when window is complete
    if i >= k - 1
      result << nums[dq.first]
    end
  end

  result
end

Pro Tip: For monotonic deque problems, the deque stores indices rather than values. This allows us to easily check if an index is outside the current window range by comparing with the current position.

Practice

Ready to apply these templates? Head over to our Practice Problems to solve real LeetCode challenges using these patterns.