Graphs

DFS and BFS on adjacency lists for connectivity, cycles, and path problems.

9 problems 0 Easy 9 Medium 0 Hard

Overview

Graph problems span connectivity, shortest paths, cycle detection, and topological ordering. Building a solid foundation here unlocks a huge class of interview questions.

When to Use

Number of islands
Clone graph
Course schedule (cycle detection)
Pacific Atlantic water flow
Word ladder
Shortest path problems

Common Mistakes

Not building the adjacency list first
Forgetting visited set causes infinite loops
Treating directed vs undirected graphs the same

Complexity

Time

O(V + E)

Space

O(V) for visited set

function numIslands(grid) {
  let count = 0;
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        dfs(grid, r, c);
        count++;
      }
    }
  }
  return count;
}

function dfs(grid, r, c) {
  if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== '1') return;
  grid[r][c] = '0'; // mark visited
  dfs(grid, r+1, c); dfs(grid, r-1, c);
  dfs(grid, r, c+1); dfs(grid, r, c-1);
}

Problems (9)

Hide completed

Problem	Difficulty	Companies	Freq	Link
Clone Graph	Medium	FacebookAmazon +1	High
Pacific Atlantic Water Flow	Medium	GoogleFacebook +1	Medium
Number of Connected Components in Undirected Graph ★	Medium	LinkedInGoogle +1	Medium	★
Surrounded Regions	Medium	GoogleFacebook +1	Medium
Minimum Height Trees	Medium	GoogleAmazon	Medium
Network Delay Time	Medium	AmazonGoogle +1	Medium
Find Eventual Safe States	Medium	GoogleAmazon	Medium
All Paths From Source to Target	Medium	AmazonFacebook +1	Medium
Cheapest Flights Within K Stops	Medium	AmazonGoogle +1	High

Not sure which graph algorithm to reach for? This cheat sheet maps problem types to the right tool i…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee