{ljdelavega.com}
← Back to Blog

Core Algorithms and Patterns Part 2

July 26, 2025

Table of Contents

Core Algorithmic Techniques Part 2

Depth-First Search (DFS)

Definition: Depth-First Search (DFS) is a fundamental traversal algorithm for trees and graphs. The core principle is to explore as far as possible down one branch before backtracking. It operates on a LIFO (Last-In, First-Out) basis, which is naturally implemented using recursion (which uses the implicit call stack) or an explicit stack data structure. When faced with a choice of nodes to visit, DFS will always go deeper into the graph first, only exploring sibling nodes after the entire path from a child has been exhausted.

Time Complexity:
  • O(V + E) for an explicit graph represented by an adjacency list, where V is the number of vertices and E is the number of edges.
  • For implicit graphs like a grid or matrix of size R x C, the complexity is O(R * C), as each cell is visited at most once.
Space Complexity:
  • O(H), where H is the maximum depth of the recursion or the maximum size of the explicit stack. In a graph, this represents the longest path from the source to a leaf.
  • In the worst case (e.g., a skewed tree or a long, snake-like path in a grid), this can be O(V) or O(R * C). For a balanced tree, it is O(log N).
  • This does not include the space for a visited set, which can also be up to O(V).
Strengths:
  • Simple Implementation: The recursive version of DFS is often very intuitive and requires minimal code.
  • Space Efficiency: For graphs that are very wide but not very deep, DFS can be more space-efficient than Breadth-First Search (BFS).
  • Path Finding: It is excellent for problems where you simply need to find if a path exists between two nodes, or for detecting cycles in a graph.
Weaknesses:
  • Non-Optimal Paths: DFS does not guarantee finding the shortest path between two nodes in an unweighted graph; BFS is used for that purpose.
  • Stack Overflow Risk: For very deep graphs or trees, the recursive implementation can exceed the call stack limit and cause a stack overflow error. In such cases, an iterative approach with an explicit stack is safer.
Step-by-Step Process (Number of Islands):

Problem: Number of Islands

  • Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
  • An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
  • You may assume all four edges of the grid are all surrounded by water.

This process uses DFS to count the number of distinct islands in a 2D grid of '1's (land) and '0's (water).

  1. Initialize: Set island_count = 0. You will also need a way to track visited cells, which can be done by creating a separate visited grid or by modifying the input grid in-place (e.g., changing '1's to '#').
  2. Iterate Grid: Loop through every cell (row, col) of the grid.
  3. Find a New Island: If the current cell is land ('1') and has not been visited:
    • You have found the start of a new, uncounted island. Increment island_count.
    • Begin a DFS traversal from this starting cell to find and mark all connected land cells belonging to this same island.
  4. DFS Helper Function: The dfs(row, col) function will do the following:
    • Base Case: Check if the current (row, col) is out of the grid's bounds or if the cell is water ('0') or has already been visited. If any of these are true, stop and return.
    • Mark as Visited: Mark the current cell (row, col) as visited.
    • Explore Neighbors: Recursively call the DFS helper function for all four adjacent neighbors (up, down, left, and right).
  5. Terminate: After the main loop has checked every cell, island_count will hold the total number of distinct islands.
Python Example:

This code solves "Number of Islands" (#200).

def num_islands(grid: list[list[str]]) -> int:
    """
    Counts the number of islands in a grid.
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    def dfs(r, c):
        # Base case: check for out of bounds or water
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        
        # Mark the current cell as visited by changing its value
        grid[r][c] = '0'
        
        # Explore neighbors
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                island_count += 1
                dfs(r, c)
    
    return island_count

# Example Usage
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(f"Number of islands: {num_islands(grid)}") # Expected Output: 1
Java Example: 
public class NumberOfIslands {

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int islandCount = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    islandCount++;
                    dfs(grid, r, c);
                }
            }
        }
        return islandCount;
    }

    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Base case for recursion
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
            return;
        }

        // Mark as visited by "sinking" the island part
        grid[r][c] = '0';
        
        // Explore neighbors
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        NumberOfIslands solver = new NumberOfIslands();
        // Expected Output: Number of islands: 3
        System.out.println("Number of islands: " + solver.numIslands(grid));
    }
}
Visual Example:

Processing a grid to count islands:

Grid:
[1, 1, 0]
[1, 0, 1]
[0, 0, 1]

1. Main loop starts at (0,0). It's '1'.
   - island_count = 1.
   - Start DFS at (0,0).
   - DFS visits (0,0), (0,1), (1,0) and marks them as '0' (or visited).
   - All connected '1's are now visited. DFS ends.
   - Grid becomes: [0, 0, 0], [0, 0, 1], [0, 0, 1]

2. Main loop continues. Skips all '0's. Reaches (1,2). It's '1'.
   - island_count = 2.
   - Start DFS at (1,2).
   - DFS visits (1,2) and (2,2). Marks them as '0'.
   - Grid becomes: [0, 0, 0], [0, 0, 0], [0, 0, 0]

3. Main loop finishes.
Final count: 2.
Example Problems:

Breadth-First Search (BFS)

Definition: Breadth-First Search (BFS) is a fundamental traversal algorithm for trees and graphs that explores nodes "level by level." It starts at a source node and visits all of its immediate neighbors before moving on to the next level of nodes. This process is managed using a queue data structure, which enforces a FIFO (First-In, First-Out) strategy. Unlike Depth-First Search (DFS), which goes as deep as possible, BFS explores layer by layer, making it ideal for finding the shortest path in an unweighted graph.

Time Complexity:
  • O(V + E) for an explicit graph represented by an adjacency list, where V is the number of vertices and E is the number of edges.
  • For implicit graphs like a tree (N nodes) or a grid (R x C), the complexity is O(N) or O(R * C), as each node is enqueued and dequeued exactly once.
Space Complexity:
  • O(W), where W is the maximum width of the graph or tree at any level.
  • In the worst case of a wide, shallow graph or a complete binary tree, the number of nodes in the queue can be proportional to N (up to N/2 nodes on the last level of a balanced tree), leading to O(N) space complexity.
Strengths:
  • Finds Shortest Path: BFS is guaranteed to find the shortest path (in terms of the number of edges) between a starting node and any other node in an unweighted graph. This is its most significant advantage.
  • Level-by-Level Traversal: It is naturally suited for problems where you need to process nodes in order of their proximity to the source, such as level-order traversal of a tree.
Weaknesses:
  • Memory Intensive: For graphs that are very wide, the queue can become very large, leading to high memory consumption. DFS might be more space-efficient for tall, narrow graphs.
  • Slower for Deep Paths: If the target node is very deep in the graph and far from the source, BFS may be slower than DFS at finding it, as BFS must explore every node at every intermediate level first.
Step-by-Step Process (Binary Tree Level Order Traversal):

Problem: Binary Tree Level Order Traversal

  • Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).
  • Return the result as a list of lists, where each inner list contains the values of nodes at that level.

This process traverses a binary tree level by level.

  1. Handle Edge Case: If the root node is null, return an empty list.
  2. Initialize: Create an empty result list to store the final level-by-level output. Create a queue and add the root node to it.
  3. Loop by Level: Begin a while loop that continues as long as the queue is not empty.
  4. Process Current Level:
    • Before processing, get the number of nodes currently in the queue (level_size). This is the number of nodes at the current level.
    • Create a new list, current_level, to store the values of the nodes at this depth.
  5. Dequeue and Enqueue Children: Start a for loop that runs level_size times. In each iteration:
    • Dequeue the node from the front of the queue.
    • Add its value to the current_level list.
    • If the dequeued node has a non-null left child, enqueue the left child.
    • If the dequeued node has a non-null right child, enqueue the right child.
  6. Store Level Result: After the for loop completes, the current_level list is fully populated. Add it to the result list.
  7. Terminate: The while loop repeats until the queue is empty, at which point all levels have been processed. Return the result list.
Python Example:

This code solves "Binary Tree Level Order Traversal" (#102).

import collections

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

def level_order(root: TreeNode) -> list[list[int]]:
    """
    Performs a level-order traversal of a binary tree.
    """
    if not root:
        return []

    result = []
    queue = collections.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

# Example Usage: Tree =  [3, 9, 20, null, null, 15, 7]
#     3
#    / \
#   9  20
#     /  \
#    15   7
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# Expected Output: [[3], [9, 20], [15, 7]]
print(f"Level order traversal: {level_order(root)}")
Java Example: 
import java.util.*;

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

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(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.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(currentLevel);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        BfsExample solver = new BfsExample();
        // Expected Output: Level order traversal: [[3], [9, 20], [15, 7]]
        System.out.println("Level order traversal: " + solver.levelOrder(root));
    }
}
Visual Example:

Level-order traversal of a tree:

Tree:
      A
     / \
    B   C
   /   / \
  D   E   F

1. Initial:
   - result = []
   - queue = [A]

2. Level 1:
   - level_size = 1. Dequeue A. Add B, C to queue.
   - result = [[A]]
   - queue = [B, C]

3. Level 2:
   - level_size = 2. Dequeue B, add D. Dequeue C, add E, F.
   - result = [[A], [B, C]]
   - queue = [D, E, F]

4. Level 3:
   - level_size = 3. Dequeue D, E, F. No children to add.
   - result = [[A], [B, C], [D, E, F]]
   - queue = []

5. Queue is empty. Loop terminates.
Final result: [[A], [B, C], [D, E, F]]
Example Problems:

Binary Tree Traversal

Definition: Binary Tree Traversal is the fundamental process of visiting (e.g., reading or processing) each node in a binary tree exactly once. The order in which the nodes are visited defines the traversal type and is chosen based on the problem to be solved. There are two main approaches: Depth-First Search (DFS) and Breadth-First Search (BFS).

The four primary traversal orders are:

  • In-order (Left, Root, Right): A DFS approach that recursively visits the left subtree, processes the current node (the "root" of that subtree), and finally visits the right subtree. For a Binary Search Tree (BST), this traversal yields the node values in sorted order.
  • Pre-order (Root, Left, Right): A DFS approach that processes the current node first, then recursively visits the left and right subtrees. This is useful for creating a copy of a tree or serializing it.
  • Post-order (Left, Right, Root): A DFS approach that recursively visits the left and right subtrees before processing the current node. This is useful when you need to process child nodes before the parent, such as when deleting nodes from a tree.
  • Level-order (BFS): This approach visits nodes level by level, from top to bottom, and left to right within each level. It uses BFS and is implemented with a queue. It is ideal for finding the shortest path from the root to any other node.
Time Complexity:
  • O(N) for all traversal types, where N is the number of nodes in the tree. Each node must be visited once.
Space Complexity:

The space complexity depends on the traversal type and implementation (recursive vs. iterative).

  • DFS (Recursive): O(H), where H is the height of the tree. This space is used by the call stack. For a balanced tree, this is O(log N); for a completely skewed tree, it becomes O(N).
  • DFS (Iterative): O(H), as the explicit stack used will hold at most H nodes.
  • BFS (Level-order): O(W), where W is the maximum width of the tree. In the worst case (a complete, balanced tree), the last level can contain up to N/2 nodes, making the space complexity O(N).
Strengths:
  • Systematic Processing: Provides a clear and exhaustive way to interact with every node in a tree.
  • Problem-Specific Orders: The different traversal orders are tailored to solve specific types of problems efficiently. For example, using in-order traversal on a BST is a simple way to get a sorted list of its elements.
Weaknesses:
  • Stack Overflow Risk: The recursive DFS approaches are elegant but can cause a stack overflow error if the tree is very deep (i.e., highly unbalanced or skewed).
  • Iterative Complexity: Iterative DFS traversals, especially post-order, can be more complex to implement correctly compared to their recursive counterparts.
Step-by-Step Process (Binary Tree Inorder Traversal):

Problem: Binary Tree Inorder Traversal

  • Given the root of a binary tree, return the inorder traversal of its nodes' values.
  • Inorder traversal visits nodes in the order: Left subtree, Root, Right subtree.
  • Follow up: Recursive solution is trivial, could you do it iteratively?

This process visits nodes in the (Left, Root, Right) order using a stack.

  1. Initialize: Create an empty stack and an empty result list. Initialize a current node pointer to the root of the tree.
  2. Loop: Start a loop that continues as long as current is not null or the stack is not empty.
  3. Traverse Left Subtree: While current is not null, push current onto the stack and move the pointer to its left child (current = current.left). This phase ensures we go as far left as possible.
  4. Visit Node and Go Right: When current becomes null, it means we can't go further left.
    • Pop the last node from the stack. This is the node we "visit." Add its value to the result list.
    • Set the current pointer to the right child of the popped node (current = popped_node.right). The main loop will then handle this right subtree, starting again by traversing its left path.
  5. Terminate: The loop ends when current is null and the stack is empty, signifying all nodes have been visited.
Python Example:

This code solves "Binary Tree Inorder Traversal" (#94) and includes both the recursive and iterative solutions. A simple TreeNode class is included for context.

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

# --- Recursive Solution ---
def inorder_traversal_recursive(root: TreeNode) -> list[int]:
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

# --- Iterative Solution ---
def inorder_traversal_iterative(root: TreeNode) -> list[int]:
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        
        # Pop, visit, and go right
        current = stack.pop()
        result.append(current.val)
        current = current.right
        
    return result

# Example Usage: Tree =  [1, null, 2, 3]
#     1
#      \
#       2
#      /
#     3
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(f"Recursive In-order: {inorder_traversal_recursive(root)}") # Expected: [1, 3, 2]
print(f"Iterative In-order: {inorder_traversal_iterative(root)}") # Expected: [1, 3, 2]
Java Example: 
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

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

public class TreeTraversalExample {

    // --- Recursive Solution ---
    public List<Integer> inorderTraversalRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) return;
        dfs(node.left, result);
        result.add(node.val);
        dfs(node.right, result);
    }

    // --- Iterative Solution ---
    public List<Integer> inorderTraversalIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }

    public static void main(String[] args) {
        // Tree =  [1, null, 2, 3]
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        TreeTraversalExample solver = new TreeTraversalExample();
        System.out.println("Recursive In-order: " + solver.inorderTraversalRecursive(root));
        System.out.println("Iterative In-order: " + solver.inorderTraversalIterative(root));
    }
}
Visual Example:

For a tree with root F, left child B, right child G, etc.:

        F
      /   \
     B     G
    / \     \
   A   D     I
      / \   /
     C   E H
  • Pre-order (Root, L, R): F, B, A, D, C, E, G, I, H
  • In-order (L, Root, R): A, B, C, D, E, F, G, H, I
  • Post-order (L, R, Root): A, C, E, D, B, H, I, G, F
  • Level-order (BFS): F, B, G, A, D, I, C, E, H
Example Problems:

Matrix Traversal

Definition: Matrix Traversal refers to the family of algorithms used to visit and process cells in a 2D grid. Many matrix problems can be modeled as implicit graphs, where each cell (row, col) is a node and its adjacent cells (up, down, left, right) are its neighbors. Consequently, the most common traversal techniques are graph algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS). These are used for problems involving connectivity, pathfinding, and searching. Other matrix-specific patterns include spiral traversal and dynamic programming approaches. A crucial part of any matrix traversal is carefully handling boundary conditions to avoid going out of bounds.

Time Complexity:
  • O(R * C), where R is the number of rows and C is the number of columns. In a typical traversal, each cell in the matrix is visited at most once.
Space Complexity:
  • DFS (Recursive): O(R * C) in the worst case. The space is determined by the maximum depth of the recursion, which could be the entire grid in a snake-like path.
  • BFS (Iterative): O(R * C) in the worst case, as the queue could potentially hold all cells (e.g., a checkerboard pattern).
  • A visited set or grid of the same dimensions might also be needed, contributing O(R * C) space if the input matrix cannot be modified.
Strengths:
  • Structured Model: It provides a clear way to apply powerful graph traversal algorithms (DFS, BFS) to problems that are not explicitly defined as graphs.
  • Versatile: This pattern is fundamental to a wide range of common interview problems, including finding connected components (islands), pathfinding (shortest path in a maze), and searching (word search).
Weaknesses:
  • Boundary Condition Errors: Traversal code is prone to off-by-one errors or IndexOutOfBounds exceptions if boundary checks for rows and columns are not handled correctly for every neighbor.
  • State Management: It is essential to keep track of visited cells to prevent infinite loops and redundant computations. This can be done by modifying the input matrix (in-place) or using an auxiliary data structure.
Step-by-Step Process (Rotting Oranges via BFS):

Problem: Rotting Oranges

  • You are given an m x n grid where each cell can have one of three values:

    • 0 representing an empty cell,
    • 1 representing a fresh orange, or
    • 2 representing a rotten orange.

  • Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

  • Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

This process uses BFS to find the minimum time for all fresh oranges to become rotten.

  1. Initial Scan and Setup:
    • Initialize a queue for the BFS process.
    • Initialize a fresh_oranges counter to 0.
    • Iterate through the entire grid once to:
      • Count the total number of fresh_oranges (value 1).
      • Add the starting coordinates of all initially rotten oranges (value 2) to the queue.
  2. Initialize Time: Set minutes = 0.
  3. BFS Loop: Start a while loop that continues as long as the queue is not empty and there are still fresh_oranges left to rot.
  4. Process a Level (Pass one minute):
    • Increment minutes.
    • Get the level_size of the queue to know how many currently rotting oranges will spread in this minute.
    • Start a for loop that runs level_size times.
  5. Dequeue and Infect Neighbors:
    • Inside the for loop, dequeue a rotten orange's coordinates (r, c).
    • For each of its four neighbors ((nr, nc)), check if the neighbor is in-bounds and is a fresh orange (value 1).
    • If it is, "infect" it by changing its value to 2, decrement the fresh_oranges count, and enqueue the neighbor's coordinates.
  6. Determine Final Result: After the loop terminates, check if the fresh_oranges count is 0.
    • If fresh_oranges == 0, it means all oranges rotted successfully. Return minutes.
    • If fresh_oranges > 0, some oranges were unreachable. Return -1.
Python Example:

This code solves "Rotting Oranges" (#994).

import collections

def oranges_rotting(grid: list[list[int]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    queue = collections.deque()
    fresh_oranges = 0

    # Initial grid scan
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                fresh_oranges += 1
            elif grid[r][c] == 2:
                queue.append((r, c))

    if fresh_oranges == 0:
        return 0

    minutes = -1 # Start at -1 to account for the last empty level check
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    # BFS loop
    while queue:
        level_size = len(queue)
        minutes += 1
        for _ in range(level_size):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh_oranges -= 1
                    queue.append((nr, nc))

    return minutes if fresh_oranges == 0 else -1

Java Example: (Rotting Oranges). Note: This uses ArrayDeque instead of LinkedList for the queue because it is the preferred implementation for queues in Java due to its better performance.

import java.util.ArrayDeque;
import java.util.Queue;

public class MatrixTraversalExample {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int freshOranges = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    freshOranges++;
                }
            }
        }

        if (freshOranges == 0) return 0;

        int minutes = -1; // Start at -1 because we count a level before processing it
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            minutes++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] point = queue.poll();
                for (int[] dir : directions) {
                    int r = point[0] + dir[0];
                    int c = point[1] + dir[1];

                    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != 1) {
                        continue;
                    }

                    grid[r][c] = 2;
                    freshOranges--;
                    queue.offer(new int[]{r, c});
                }
            }
        }

        return freshOranges == 0 ? minutes : -1;
    }
}
Visual Example: 
grid = [
  [2,1,1],
  [1,1,0],
  [0,1,1]
]

Initial State:
- fresh = 5
- queue = [(0,0)]
- minutes = -1

Minute 0 (level_size = 1, minutes = 0):
- Dequeue (0,0). Infect neighbors (0,1) and (1,0).
- fresh = 3
- queue = [(0,1), (1,0)]
- grid = [[2,2,1],[2,1,0],[0,1,1]]

Minute 1 (level_size = 2, minutes = 1):
- Dequeue (0,1). Infect (0,2).
- Dequeue (1,0). Infect (1,1).
- fresh = 1
- queue = [(0,2), (1,1)]
- grid = [[2,2,2],[2,2,0],[0,1,1]]

Minute 2 (level_size = 2, minutes = 2):
- Dequeue (0,2). No fresh neighbors.
- Dequeue (1,1). Infect (2,1).
- fresh = 0
- queue = [(2,1)]
- grid = [[2,2,2],[2,2,0],[0,2,1]]

Minute 3 (level_size = 1, minutes = 3):
- Dequeue (2,1). Infect (2,2).
- fresh = 0
- queue = [(2,2)]
- grid = [[2,2,2],[2,2,0],[0,2,2]]

Minute 4 (level_size = 1, minutes = 4):
- Dequeue (2,2). No fresh neighbors.
- queue = []

Loop ends. fresh_oranges is 0, so return `minutes` which is 4.
Example Problems:

Top K Elements

Definition: The Top K Elements pattern describes a class of problems where the goal is to find a specific number (k) of the most frequent, largest, or smallest elements in a collection. While sorting the entire collection and taking the first k elements is a straightforward approach, it's often inefficient (O(N log N)). The optimal approach for this pattern typically involves using a Heap (also known as a Priority Queue), which allows the solution to be found in O(N log K) time. For frequency-based problems, a Hash Map is first used to count occurrences.

The core idea is to maintain a heap of size k and iterate through the elements. For each element, you compare it to the top of the heap and decide whether to add the new element and remove the top, thereby always keeping the "top k" elements seen so far.

Time Complexity:
  • O(N log K). The process usually involves two passes. First, building a frequency map takes O(N). Second, iterating through the N unique elements and adding them to a heap of size k takes O(log K) for each element, resulting in O(N log K). This is more efficient than the O(N log N) sorting approach when k is significantly smaller than N.
Space Complexity:
  • O(N + K). In the worst case, the frequency map can require O(N) space if all elements are unique. The heap requires O(K) space. This simplifies to O(N).
Strengths:
  • Efficient: Far more time-efficient than sorting when you only need a subset of the elements (k) and not the entire sorted collection.
  • Adaptable: The same underlying heap-based logic can be used to find the largest, smallest, most frequent, or least frequent elements with minor tweaks (e.g., using a min-heap vs. a max-heap).
Weaknesses:
  • Implementation Complexity: The solution is more complex to implement than a simple sort, requiring familiarity with Heaps/Priority Queues and, for frequency problems, Hash Maps.
  • Space Usage: It's not an in-place algorithm and requires additional space for both the heap and potentially a frequency map, which can be a drawback for very large datasets.
Step-by-Step Process (Top K Frequent Elements):

Problem: Top K Frequent Elements

  • Given an integer array nums and an integer k, return the k most frequent elements.
  • You may return the answer in any order.
  • The answer is guaranteed to be unique.

This process uses a min-heap to find the k most frequent elements.

  1. Frequency Count: Iterate through the input array and use a Hash Map to build a frequency count for each number. The key will be the number, and the value will be its frequency.
  2. Initialize Heap: Create a min-heap. This heap will store tuples or objects of (frequency, number). A min-heap is used to easily keep track of the element with the smallest frequency currently in our set of top k candidates.
  3. Build Heap: Iterate through the items in the frequency map. For each (number, frequency) pair:
    • Push the (frequency, number) pair onto the min-heap.
    • If the heap's size grows larger than k, pop from the heap. Since it's a min-heap, this action removes the element with the lowest frequency, ensuring the heap only retains the k most frequent elements seen so far.
  4. Extract Result: After iterating through all the numbers, the min-heap will contain the k most frequent elements. Extract the numbers from the heap to build the final result list.
Python Example:

This code solves "Top K Frequent Elements" (#347).

import collections
import heapq

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """
    Finds the k most frequent elements in an array.
    """
    # 1. Build a frequency map.
    # O(N) time.
    if not nums:
        return []
    counts = collections.Counter(nums)
    
    # 2. Use a min-heap to find the top k frequent elements.
    # O(N log K) time.
    min_heap = []
    for num, freq in counts.items():
        # Push a tuple of (frequency, number) onto the heap
        heapq.heappush(min_heap, (freq, num))
        # If the heap size exceeds k, pop the element with the smallest frequency
        if len(min_heap) > k:
            heapq.heappop(min_heap)
            
    # 3. Extract the numbers from the heap to build the result.
    result = [num for freq, num in min_heap]
    return result

# Example Usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
# Frequencies: {1: 3, 2: 2, 3: 1}. The top 2 are 1 and 2.
print(f"Top {k} frequent elements: {top_k_frequent(nums, k)}") # Expected Output: [2, 1] or [1, 2]
Java Example: 
import java.util.*;

public class TopKElementsExample {

    public static int[] topKFrequent(int[] nums, int k) {
        // 1. Build frequency map - O(N)
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        // 2. Initialize a min-heap. The comparator sorts by frequency (the value).
        // The lambda (a, b) -> a.getValue() - b.getValue() creates a min-heap on frequency.
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

        // 3. Build the heap - O(N log K)
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            minHeap.add(entry);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the element with the smallest frequency
            }
        }

        // 4. Extract the result
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll().getKey();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        int[] result = topKFrequent(nums, k);
        // Expected Output: Top 2 frequent elements: [1, 2] (order may vary)
        System.out.println("Top " + k + " frequent elements: " + Arrays.toString(result));
    }
}
Visual Example:

Finding top 2 frequent elements in [1,1,1,2,2,3]:

1. Frequency Map:
   {1: 3, 2: 2, 3: 1}

2. Build Min-Heap (k=2):
   - Process (num=1, freq=3): push (3,1). Heap: [(3,1)]
   - Process (num=2, freq=2): push (2,2). Heap: [(2,2), (3,1)]
   - Process (num=3, freq=1): push (1,3). Heap: [(1,3), (3,1), (2,2)]
     - Heap size is 3 (>k). Pop smallest: (1,3) is popped.
     - Heap: [(2,2), (3,1)]

3. Loop ends. Final Heap contains the top 2 elements.
   - Heap: [(2,2), (3,1)]

4. Extract result: [2, 1]
Example Problems:

Overlapping Intervals

Definition: The Overlapping Intervals pattern is a common algorithmic approach for problems involving ranges or time intervals (e.g., meeting schedules, geometric ranges). The core idea is that if you sort the intervals by their start times, you can process them in a single, linear pass to solve the problem. Once sorted, determining if two adjacent intervals overlap becomes a simple comparison. This sorted order allows for greedy decisions, such as merging overlapping intervals, counting required resources (like meeting rooms), or finding non-overlapping sets.

Time Complexity:
  • O(N log N). The dominant operation is sorting the N intervals. The subsequent merging or processing step is a single pass, which takes O(N) time.
Space Complexity:
  • O(N) or O(log N). The space complexity of the sorting algorithm can vary depending on the language's implementation (from O(log N) to O(N)). Additionally, if the result requires creating a new list of intervals, it can take up to O(N) space in the worst case (if no intervals are merged).
Strengths:
  • Structured Approach: Provides a reliable and clear strategy for a whole class of interval-based problems. The "sort then process" pattern is very powerful.
  • Efficient: Drastically simplifies the problem from a potential brute-force comparison of all pairs (O(N^2)) to a much faster O(N log N) solution.
Weaknesses:
  • Sorting Bottleneck: The primary performance limitation is the O(N log N) time required for sorting.
  • Specific Data Type: The pattern is only applicable to problems that can be represented as a collection of 1-dimensional intervals, each having a start and an end.
Step-by-Step Process (Merge Intervals):

Problem: Merge Intervals

  • Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals.
  • Return an array of the non-overlapping intervals that cover all the intervals in the input.

This process merges all overlapping intervals in a collection.

  1. Handle Edge Cases: If the input list has fewer than two intervals, no merging is possible. Return the list as is.
  2. Sort: Sort the list of intervals based on their start times in ascending order. This is the most crucial step.
  3. Initialize Result: Create a new list for the merged intervals (e.g., merged_intervals) and add the very first interval from the sorted list to it.
  4. Iterate and Merge: Loop through the sorted intervals, starting from the second one. For each current_interval:
    • Get a reference to the last_interval in the merged_intervals list.
    • Check for Overlap: An overlap occurs if the current_interval's start is less than or equal to the last_interval's end.
    • If Overlap: Merge them by updating the last_interval's end to be the maximum of its current end and the current_interval's end.
    • If No Overlap: The intervals are distinct. Add the current_interval to the merged_intervals list.
  5. Terminate: After the loop finishes, merged_intervals contains the final, non-overlapping merged intervals.
Python Example:

This code solves the classic "Merge Intervals" problem (#56).

def merge(intervals: list[list[int]]) -> list[list[int]]:
    """
    Merges all overlapping intervals.
    """
    if not intervals:
        return []
    
    # 1. Sort intervals based on their start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for i in range(1, len(intervals)):
        current_interval = intervals[i]
        last_merged = merged[-1]
        
        # Check for overlap: current_start <= last_end
        if current_interval[0] <= last_merged[1]:
            # Merge by updating the end of the last merged interval
            last_merged[1] = max(last_merged[1], current_interval[1])
        else:
            # No overlap, add the new interval
            merged.append(current_interval)
            
    return merged

# Example Usage
intervals = [[1,3], [2,6], [8,10], [15,18]]
# Expected Output: [[1, 6], [8, 10], [15, 18]]
print(f"Merged intervals: {merge(intervals)}")

intervals2 = [[1,4], [4,5]]
# Expected Output: [[1, 5]]
print(f"Merged intervals: {merge(intervals2)}")
Java Example: 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervalsExample {

    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        // 1. Sort intervals based on start times
        // The lambda (a, b) -> Integer.compare(a[0], b[0]) sorts by the first element.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] currentInterval = intervals[i];
            int[] lastMerged = merged.get(merged.size() - 1);

            // Check for overlap: current_start <= last_end
            if (currentInterval[0] <= lastMerged[1]) {
                // Merge by updating the end of the last merged interval
                lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]);
            } else {
                // No overlap, add the new interval
                merged.add(currentInterval);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3}, {2,6}, {8,10}, {15,18}};
        int[][] result = merge(intervals);
        // Expected Output: Merged intervals: [[1, 6], [8, 10], [15, 18]]
        System.out.println("Merged intervals: " + Arrays.deepToString(result));
    }
}
Visual Example:

Merging [[1,3],[8,10],[2,6],[15,18]]:

1. Unsorted: [[1,3], [8,10], [2,6], [15,18]]

2. Sorted by start time: [[1,3], [2,6], [8,10], [15,18]]

3. Process:
   - merged = []
   - Add first interval [1,3].
     - merged: [[1,3]]

   - Current: [2,6]. Last in merged: [1,3].
     - Does it overlap? Yes, 2 <= 3.
     - Merge: Update end of [1,3] to max(3, 6) -> 6.
     - merged: [[1,6]]

   - Current: [8,10]. Last in merged: [1,6].
     - Does it overlap? No, 8 > 6.
     - Add [8,10] to merged.
     - merged: [[1,6], [8,10]]

   - Current: [15,18]. Last in merged: [8,10].
     - Does it overlap? No, 15 > 10.
     - Add [15,18] to merged.
     - merged: [[1,6], [8,10], [15,18]]

4. Final Result: [[1,6], [8,10], [15,18]]
Example Problems:

Definition: A Modified Binary Search is an advanced application of the standard binary search algorithm. While traditional binary search operates on perfectly sorted data, the modified version is adapted for data structures or search spaces that are not strictly sorted but still possess a monotonic property that can be exploited. This allows you to eliminate half of the search space at each step, even in complex scenarios like rotated sorted arrays, bitonic arrays, or when searching for an answer within a range of potential values (e.g., finding the square root of a number). The key is to adjust the logic for how to narrow down the left and right boundaries based on the problem's unique conditions.

Monotonic means varying in such a way that it either never decreases or never increases. ie. a monotonic increasing array is an array where each element is greater than or equal to the previous element. A monotonic decreasing array is an array where each element is less than or equal to the previous element.

Time Complexity:
  • O(log N), where N is the number of elements in the search space. This logarithmic complexity is the primary advantage of any binary search-based approach.
Space Complexity:
  • O(1) for the standard iterative implementation, as it only requires a few variables to keep track of the left, right, and mid pointers.
Strengths:
  • Extremely Efficient: It offers one of the best time complexities possible for search-related problems, making it suitable for very large datasets.
  • Versatile: The core principle of "divide and conquer" can be applied to a wide range of problems, not just finding a value in an array. It can find minimums/maximums, insertion points, or a specific value that satisfies a condition within a range.
Weaknesses:
  • Requires Monotonicity: The fundamental requirement is a sorted or monotonic property. If no such property exists, binary search cannot be applied.
  • Complex Conditions: The logic to determine which half of the search space to discard is often more complex and error-prone than in a standard binary search. Off-by-one errors and handling boundary conditions (<= vs <) require careful implementation.
Step-by-Step Process (Search in Rotated Sorted Array):

Problem: Search in Rotated Sorted Array

  • There is an integer array nums sorted in ascending order (with distinct values).
  • Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].
  • Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
  • You must write an algorithm with O(log n) runtime complexity.

This process finds a target value in a sorted array that has been rotated at some unknown pivot.

  1. Initialize Pointers: Set left = 0 and right = n - 1, where n is the length of the array.
  2. Loop: Continue as long as left <= right.
  3. Find Midpoint: Calculate mid = left + (right - left) // 2 to prevent potential integer overflow.
  4. Check for Target: If nums[mid] == target, the element is found. Return mid.
  5. Identify Sorted Half: Determine which part of the array is currently sorted.
    • Check if the left half is sorted by comparing nums[left] <= nums[mid].
  6. Decide Which Half to Search:
    • If Left Half is Sorted: Check if the target is within the bounds of this sorted half (nums[left] <= target < nums[mid]).
      • If yes, the target must be in the left half, so discard the right half: right = mid - 1.
      • If no, the target must be in the unsorted right half: left = mid + 1.
    • If Right Half is Sorted: (This is the else case, meaning nums[left] > nums[mid]). Check if the target is within the bounds of this sorted right half (nums[mid] < target <= nums[right]).
      • If yes, the target must be in the right half: left = mid + 1.
      • If no, the target must be in the unsorted left half: right = mid - 1.
  7. Terminate: If the loop finishes without finding the target, it does not exist in the array. Return -1.
Python Example:

This code solves "Search in Rotated Sorted Array" (#33).

def search(nums: list[int], target: int) -> int:
    """
    Searches for a target in a rotated sorted array.
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # Check if the left half is sorted
        if nums[left] <= nums[mid]:
            # Check if target is in the sorted left half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Otherwise, the right half must be sorted
        else:
            # Check if target is in the sorted right half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
                
    return -1

# Example Usage
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
# Expected Output: 4
print(f"Index of target {target}: {search(nums, target)}")

target2 = 3
# Expected Output: -1
print(f"Index of target {target2}: {search(nums, target2)}")
Java Example: 
public class ModifiedBinarySearchExample {

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // Check if the left half is sorted
            if (nums[left] <= nums[mid]) {
                // Check if target is in the sorted left half
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            // Otherwise, the right half must be sorted
            } else {
                // Check if target is in the sorted right half
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        // Expected Output: Index of target 0: 4
        System.out.println("Index of target " + target + ": " + search(nums, target));
        
        int target2 = 3;
        // Expected Output: Index of target 3: -1
        System.out.println("Index of target " + target2 + ": " + search(nums, target2));
    }
}
Visual Example:

Searching for target = 0 in [4, 5, 6, 7, 0, 1, 2]:

Initial:
 L           R
[4, 5, 6, 7, 0, 1, 2]

Step 1:
- mid = 3. nums[mid] = 7. Not the target.
- Left half [4,5,6,7] is sorted.
- Target 0 is NOT in [4,7]. Search right.
- L = mid + 1 = 4.
   L           R
[4, 5, 6, 7, 0, 1, 2]
             L     R

Step 2:
- mid = 5. nums[mid] = 1. Not the target.
- Left half [0,1] is NOT sorted (since nums[L] > nums[mid]).
- Right half [1,2] is sorted.
- Target 0 is NOT in (1,2]. Search left.
- R = mid - 1 = 4.
             L,R
[4, 5, 6, 7, 0, 1, 2]

Step 3:
- mid = 4. nums[mid] = 0. Target found!
- Return mid = 4.
Example Problems:

Remember: The goal isn't just to memorize implementations, but to understand the underlying principles and trade-offs that make each algorithm suitable for specific problems. Practice recognizing patterns and choosing the right algorithmic approach based on problem constraints and requirements.

For part 1, check out Core Algorithms and Patterns Part 1.

For part 3, check out Core Algorithms and Patterns Part 3.

For a comprehensive guide to data structures, check out Core Data Structures and Advanced Data Structures.