Advanced Graph DFS: Region Analysis and Cycle Detection

Surrounded Regions (LeetCode 130)

Any 'O' connected to the boundary cannot be captured. The logic is to start from the boundaries, mark all reachable 'O's as "safe," then flip the remaining 'O's to 'X'.

public void solve(char[][] board) {
    if (board == null || board.length == 0) return;
    int rows = board.length, cols = board[0].length;
    
    // 1. Traverse all boundary 'O's and mark their entire connected region as safe
    for (int i = 0; i < rows; i++) {
        dfsMark(board, i, 0);
        dfsMark(board, i, cols - 1);
    }
    for (int j = 0; j < cols; j++) {
        dfsMark(board, 0, j);
        dfsMark(board, rows - 1, j);
    }
    
    // 2. Scan and transform: 
    // Unmarked 'O' -> 'X' (Captured)
    // Marked '#'   -> 'O' (Restore safety)
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '#') board[i][j] = 'O';
        }
    }
}

private void dfsMark(char[][] board, int r, int c) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O') return;
    board[r][c] = '#'; // Mark as safe
    dfsMark(board, r + 1, c);
    dfsMark(board, r - 1, c);
    dfsMark(board, r, c + 1);
    dfsMark(board, r, c - 1);
}

Pacific Atlantic Water Flow (LeetCode 417)

Reverse Thinking: Instead of simulating water flowing down from every cell, simulate water flowing "uphill" from the oceans (Pacific and Atlantic) toward the peaks. Find the intersection of cells reachable from both oceans.

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] canReachPacific = new boolean[m][n];
    boolean[][] canReachAtlantic = new boolean[m][n];
    
    // Trigger DFS from all cells bordering the respective oceans
    for (int i = 0; i < m; i++) {
        dfsUphill(heights, canReachPacific, i, 0);
        dfsUphill(heights, canReachAtlantic, i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        dfsUphill(heights, canReachPacific, 0, j);
        dfsUphill(heights, canReachAtlantic, m - 1, j);
    }
    
    List<List<Integer>> intersection = new ArrayList<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (canReachPacific[i][j] && canReachAtlantic[i][j]) {
                intersection.add(Arrays.asList(i, j));
            }
        }
    }
    return intersection;
}

private void dfsUphill(int[][] h, boolean[][] visited, int r, int c) {
    if (visited[r][c]) return;
    visited[r][c] = true;
    int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : directions) {
        int nr = r + d[0], nc = c + d[1];
        // Only move to neighbor if it's equal or HIGHER in altitude
        if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length 
            && !visited[nr][nc] && h[nr][nc] >= h[r][c]) {
            dfsUphill(h, visited, nr, nc);
        }
    }
}

Clone Graph (LeetCode 133)

Create a deep copy of a connected undirected graph using BFS and a mapping table.

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> originalToClone = new HashMap<>(); // Maps old nodes to brand new nodes
    Queue<Node> queue = new ArrayDeque<>();
    
    originalToClone.put(node, new Node(node.val));
    queue.offer(node);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        for (Node neighbor : current.neighbors) {
            if (!originalToClone.containsKey(neighbor)) {
                originalToClone.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            // Link current clone to neighbor clone
            originalToClone.get(current).neighbors.add(originalToClone.get(neighbor));
        }
    }
    return originalToClone.get(node);
}

Patterns Summary