BFS

BFS

200. Number of Islands

Problem: Given a grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Thinking Process

  • Model: Connected components. Each time we see an unvisited '1', we run BFS/DFS to sink the whole island.
  • Steps: Loop through grid → if '1' and unvisited, launch BFS/DFS → mark visited → increment count.
  • Complexity: O(mn).
  • Pitfall: Mark visited immediately when enqueuing, not after dequeuing.

102. Binary Tree Level Order Traversal

Problem: Return the level order traversal of a binary tree.

Thinking Process

  • Model: Standard BFS with queue. Process nodes level by level.
  • Steps: Push root → while queue not empty, process all nodes of current level → collect children into queue.
  • Complexity: O(n).
  • Pitfall: Don’t forget to handle empty tree.

103. Binary Tree Zigzag Level Order Traversal

Problem: Similar to 102, but alternate direction at each level.

Thinking Process

  • Approach 1: Collect each level into a list, reverse it if needed.
  • Approach 2: Use deque and insert values at either end depending on direction.
  • Complexity: O(n).
  • Pitfall: Reverse once per level, not per node.

994. Rotting Oranges

Problem: A rotten orange at time t rots its adjacent fresh oranges at time t+1. Return the minimum minutes until no fresh orange remains. If impossible, return -1.

Thinking Process

  • Model: Multi-source BFS. All rotten oranges are starting points.
  • Steps: Put all rotten oranges in queue → track fresh count → BFS layer by layer → decrease fresh count.
  • Complexity: O(mn).
  • Pitfall: Decide carefully when to increment minute count.

199. Binary Tree Right Side View

Problem: Return the values of the nodes visible from the right side.

Thinking Process

  • Approach 1: BFS → take the last node of each level.
  • Approach 2: DFS (right-first) → first node at each depth is visible.
  • Complexity: O(n).
  • Pitfall: With DFS, depth indexing must be correct.

286. Walls and Gates

Problem: Given a grid with -1 as wall, 0 as gate, and INF as empty room, fill each room with the distance to its nearest gate.

Thinking Process

  • Model: Multi-source BFS starting from all gates.
  • Steps: Enqueue all gates → BFS → when reaching INF, set distance and enqueue.
  • Complexity: O(mn).
  • Pitfall: Don’t try BFS from each empty room (too slow).

490. The Maze

Problem: Ball rolls until hitting a wall. Determine if there’s a path from start to destination.

Thinking Process

  • Model: BFS/DFS but transitions are “rolling stops” not adjacent moves.
  • Steps: From current cell, roll in one direction until hitting a wall → stop point is the neighbor → enqueue if unvisited.
  • Complexity: O(mn).
  • Pitfall: Mark only stopping positions visited, not the in-between cells.

207. Course Schedule

Problem: Given prerequisites, determine if it’s possible to finish all courses.

Thinking Process

  • Model: Detect cycle in directed graph. Kahn’s BFS topological sort.
  • Steps: Build graph → compute indegrees → enqueue zero-indegree nodes → pop and decrement neighbors → count visited.
  • Complexity: O(V+E).
  • Pitfall: Don’t forget isolated nodes; final check is whether processed count == total courses.

Template: Unweighted Shortest Path (Equal-weight Graphs)

  • Model: BFS. First time reaching a node gives shortest distance.
  • Complexity: O(V+E).

Template: Dijkstra (Non-negative Weights)

  • Model: Min-heap + greedy.
  • Steps: Pop the closest node; relax edges; skip outdated heap entries.
  • Complexity: O(E log V).