Coding

BFS/DFS

Queue for level order (BFS), stack/recursion for depth (DFS).

Coding pattern

Overview

BFS and DFS are the two fundamental ways to explore a graph or grid. BFS fans out level by level (shortest unweighted paths); DFS dives deep first (connectivity, cycles, backtracking). Knowing which guarantees what is the whole game.

How it works

Coding pattern

ClientAsyncServiceData

Step by step, with examples

1
Source node
- Choose a start node and init the visited set.
2
Queue/Stack
- BFS uses a queue (levels); DFS uses a stack/recursion.
3
Neighbors
- Push each unvisited neighbor.
4
Traversal
- BFS gives shortest hops; DFS gives full reachability.
- Example: Shortest unweighted path

When to reach for it

Shortest hops
Flood fill
Exhaustive traversal

Example problem

Number of islands in a grid.

Approach

Scan each cell
On land, flood-fill its neighbors and count one island

Solution

function numIslands(grid) {
  let count = 0;
  const flood = (r,c) => {
    if(r<0||c<0||r>=grid.length||c>=grid[0].length||grid[r][c]!=='1') return;
    grid[r][c] = '0';
    flood(r+1,c);flood(r-1,c);flood(r,c+1);flood(r,c-1);
  };
  for(let r=0;r<grid.length;r++)for(let c=0;c<grid[0].length;c++)
    if(grid[r][c]==='1'){count++;flood(r,c);}
  return count;
}

Complexity

Time O(rows·cols), Space O(rows·cols) worst case.

Common pitfalls

Out-of-bounds checks
Not marking visited

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions