Tracks

Full-Stack Interview Prep

Graph

38 problems · 43 approaches

Number of islandsMedium2 approaches

Problem

In a grid of "1" (land) and "0" (water), an island is a group of land cells connected up, down, left or right. Return the number of islands.

Example 1

Input:  [["1","1","0","0"], ["1","1","0","0"], ["0","0","1","0"], ["0","0","0","1"]]
Output: 3

Also asked as: Find the no. of Isalnds · Find the no. of Islands

1. DFS flood fill

Time O(R·C)Space O(R·C) recursion worst case

Scan the grid; each unvisited land cell starts a new island — sink its whole component.

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

2. BFS flood fill

Time O(R·C)Space O(min(R,C))

Same idea, queue instead of recursion — avoids deep stacks on huge grids.

function numIslands(grid) {
  const R = grid.length, C = grid[0].length;
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (grid[r][c] === '1') {
        count++;
        const q = [[r, c]]; grid[r][c] = '0';
        while (q.length) {
          const [x, y] = q.shift();
          for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && ny >= 0 && nx < R && ny < C && grid[nx][ny] === '1') {
              grid[nx][ny] = '0'; q.push([nx, ny]);
            }
          }
        }
      }
  return count;
}

Topological sort of a DAGMedium2 approaches

Problem

Given a directed acyclic graph (n nodes, with edges u → v meaning u must come before v), return any ordering of the nodes in which every edge points forward. In Course Schedule II the edges are prerequisites; return [] if a cycle makes an ordering impossible.

Example 1

Input:  n = 4, edges = [[1,0], [2,0], [3,1], [3,2]]  (course, prerequisite)
Output: [0, 1, 2, 3] or [0, 2, 1, 3]

Also asked as: topological sort · course schedule

1. Kahn's algorithm (BFS on in-degrees)

Time O(V + E)Space O(V + E)

Repeatedly remove a node with in-degree 0 and decrement its neighbours. If you can’t process all nodes, there is a cycle.

function topoSort(numNodes, edges) {
  const adj = Array.from({ length: numNodes }, () => []);
  const indeg = Array(numNodes).fill(0);
  for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; }
  const q = [];
  for (let i = 0; i < numNodes; i++) if (indeg[i] === 0) q.push(i);
  const order = [];
  while (q.length) {
    const u = q.shift();
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return order.length === numNodes ? order : null; // null ⇒ cycle
}

2. DFS with colours

Time O(V + E)Space O(V + E)

DFS; push a node to the front of the order after its subtree is done. A back-edge to a "grey" node means a cycle.

function topoSort(numNodes, edges) {
  const adj = Array.from({ length: numNodes }, () => []);
  for (const [u, v] of edges) adj[u].push(v);
  const state = Array(numNodes).fill(0); // 0=unseen 1=in-progress 2=done
  const order = [];
  let ok = true;
  const dfs = (u) => {
    state[u] = 1;
    for (const v of adj[u]) {
      if (state[v] === 1) { ok = false; return; }
      if (state[v] === 0) dfs(v);
    }
    state[u] = 2;
    order.push(u);
  };
  for (let i = 0; i < numNodes && ok; i++) if (state[i] === 0) dfs(i);
  return ok ? order.reverse() : null;
}

Represent a graph; BFS and DFSEasy1 approach

Problem

Build an adjacency list from an edge list, then print the nodes in breadth-first order (level by level from the source) and in depth-first order (go as deep as possible before backtracking).

Example 1

Input:  edges = [[0,1], [0,2], [1,3], [2,4]], source 0
Output: BFS 0 1 2 3 4 · DFS 0 1 3 2 4

Also asked as: Create a Graph, print it · Implement BFS algorithm · Implement DFS Algo

1. Adjacency list + queue (BFS) / stack or recursion (DFS)

Time O(V + E)Space O(V + E)

Store neighbours per node. BFS explores in rings using a queue; DFS goes deep with recursion or an explicit stack.

function buildGraph(n, edges, directed = false) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); if (!directed) adj[v].push(u); }
  return adj;
}
function bfs(adj, src) {
  const seen = new Array(adj.length).fill(false), order = [];
  const q = [src]; seen[src] = true;
  for (let i = 0; i < q.length; i++) {
    const u = q[i]; order.push(u);
    for (const v of adj[u]) if (!seen[v]) { seen[v] = true; q.push(v); }
  }
  return order;
}
function dfs(adj, src, seen = new Array(adj.length).fill(false), order = []) {
  seen[src] = true; order.push(src);
  for (const v of adj[src]) if (!seen[v]) dfs(adj, v, seen, order);
  return order;
}

Detect a cycle — directed and undirectedMedium2 approaches

Problem

Return true if the graph contains a cycle. Handle both cases: an undirected graph (a visited neighbour that is not your parent means a cycle) and a directed graph (reaching a node still on the current DFS path means a cycle).

Example 1

Input:  directed: 0→1, 1→2, 2→0
Output: true

Example 2

Input:  undirected: 0–1, 1–2
Output: false

Also asked as: Detect Cycle in Directed Graph using BFS/DFS Algo · Detect Cycle in UnDirected Graph using BFS/DFS Algo · Find whether it is possible to finish all tasks or not from given dependencies

1. Directed — DFS with 3 colours (or Kahn count)

Time O(V + E)Space O(V)

grey = on the current DFS path. An edge to a grey node is a back-edge ⇒ cycle. "Can finish all tasks" is exactly "the dependency DAG has no cycle".

function hasCycleDirected(adj) {
  const state = new Array(adj.length).fill(0); // 0 unseen, 1 grey, 2 done
  const dfs = (u) => {
    state[u] = 1;
    for (const v of adj[u]) {
      if (state[v] === 1) return true;
      if (state[v] === 0 && dfs(v)) return true;
    }
    state[u] = 2;
    return false;
  };
  for (let i = 0; i < adj.length; i++) if (state[i] === 0 && dfs(i)) return true;
  return false;
}

2. Undirected — DFS tracking the parent (or Union-Find)

Time O(V + E)Space O(V)

A visited neighbour that is not the node you came from means a cycle. Alternatively, an edge whose endpoints are already in the same DSU set forms a cycle.

function hasCycleUndirected(adj) {
  const seen = new Array(adj.length).fill(false);
  const dfs = (u, parent) => {
    seen[u] = true;
    for (const v of adj[u]) {
      if (!seen[v]) { if (dfs(v, u)) return true; }
      else if (v !== parent) return true;
    }
    return false;
  };
  for (let i = 0; i < adj.length; i++) if (!seen[i] && dfs(i, -1)) return true;
  return false;
}

Flood fillEasy1 approach

Problem

Given an image grid, a start pixel (sr, sc) and a new colour, recolour the start pixel and every pixel connected to it (up, down, left or right) that has the same original colour. Return the image.

Example 1

Input:  image = [[1,1,1], [1,1,0], [1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2], [2,2,0], [2,0,1]]

Also asked as: flood fill algo

1. DFS/BFS from the start pixel

Time O(R·C)Space O(R·C)

Recolour the start pixel and recurse into 4-connected neighbours that still have the original colour.

function floodFill(image, sr, sc, newColor) {
  const old = image[sr][sc];
  if (old === newColor) return image;
  const fill = (r, c) => {
    if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] !== old) return;
    image[r][c] = newColor;
    fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1);
  };
  fill(sr, sc);
  return image;
}

Clone a graphMedium1 approach

Problem

Given a reference to one node of a connected undirected graph (each node has a value and a list of neighbours), return a deep copy of the whole graph.

Example 1

Input:  adjacency = [[2,4], [1,3], [2,4], [1,3]]
Output: A new graph with the same structure

Also asked as: Clone a graph

1. DFS/BFS with an original → copy map

Time O(V + E)Space O(V)

On first visit, create the copy and store it; for each neighbour, recurse (creating it if needed) and link.

function cloneGraph(node) {
  if (!node) return null;
  const map = new Map();
  const dfs = (n) => {
    if (map.has(n)) return map.get(n);
    const copy = { val: n.val, neighbors: [] };
    map.set(n, copy);
    for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

Shortest path on a grid — rat in a maze, knight moves, snake & ladderMedium1 approach

Problem

Unweighted shortest-path problems, all solved with BFS:

Knight moves — the minimum number of knight moves from a source square to a target square on an n × n board. Snake & ladder — the minimum number of dice throws to go from square 1 to the last square, following snakes and ladders. Maze — the fewest steps from the start to the exit, moving through open cells only.

Example 1

Input:  knight: n = 6, from (4,5) to (1,1)
Output: 3

Also asked as: Search in a Maze · Minimum Step by Knight · Snake and Ladders Problem · Rat in a maze Problem

1. BFS (unweighted shortest path)

Time O(cells)Space O(cells)

Every cell/state is a node; edges are legal moves. BFS from the start gives the minimum number of moves. Snake & ladder: nodes are board squares 1..100, edges are dice rolls, jumps rewrite the destination.

function minKnightMoves(N, start, target) {
  const moves = [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]];
  const seen = Array.from({ length: N }, () => Array(N).fill(false));
  let q = [[...start, 0]];
  seen[start[0]][start[1]] = true;
  while (q.length) {
    const next = [];
    for (const [r, c, d] of q) {
      if (r === target[0] && c === target[1]) return d;
      for (const [dr, dc] of moves) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nc >= 0 && nr < N && nc < N && !seen[nr][nc]) { seen[nr][nc] = true; next.push([nr, nc, d + 1]); }
      }
    }
    q = next;
  }
  return -1;
}

Rat in a maze wants ALL paths, not the shortest — that is backtracking (record the path, mark/unmark visited cells).

Word Ladder (shortest transformation sequence)Hard1 approach

Problem

Transform beginWord into endWord by changing one letter at a time, where every intermediate word must be in the word list. Return the number of words in the shortest such sequence (including both ends), or 0 if it is impossible.

Example 1

Input:  begin = "hit", end = "cog", list = ["hot","dot","dog","lot","log","cog"]
Output: 5

hit → hot → dot → dog → cog.

Also asked as: word Ladder

1. BFS over words, neighbours = one-letter changes

Time O(N · L · 26)Space O(N · L)

From each word, generate all words that differ by one letter; keep those in the dictionary. BFS distance from beginWord to endWord + 1 is the ladder length.

function ladderLength(begin, end, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(end)) return 0;
  let q = [begin], steps = 1;
  dict.delete(begin);
  while (q.length) {
    const next = [];
    for (const word of q) {
      if (word === end) return steps;
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c < 123; c++) {
          const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (dict.has(cand)) { dict.delete(cand); next.push(cand); }
        }
      }
    }
    q = next; steps++;
  }
  return 0;
}

Dijkstra's shortest pathsMedium1 approach

Problem

Given a weighted graph with non-negative edge weights and a source node, return the shortest distance from the source to every node. Network Delay Time asks for the largest of those distances, or −1 if some node is unreachable.

Example 1

Input:  edges (u, v, w) = [[2,1,1], [2,3,1], [3,4,1]], n = 4, source = 2
Output: distances 1:1, 2:0, 3:1, 4:2 → network delay 2

Also asked as: Dijkstra algo

1. Min-priority queue by tentative distance

Time O((V + E) log V)Space O(V)

Repeatedly pop the closest unfinalised node and relax its edges. Needs non-negative weights.

function dijkstra(adj, src) { // adj[u] = [[v, w], ...]
  const dist = new Array(adj.length).fill(Infinity);
  dist[src] = 0;
  const pq = [[0, src]]; // [d, node]; simple array used as a min-heap
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) { dist[v] = d + w; pq.push([dist[v], v]); }
    }
  }
  return dist;
}

Topological sort; job completion times & longest path in a DAGMedium1 approach

Problem

Using a topological order: (1) print a valid ordering; (2) each job takes 1 unit of time and can start only after its prerequisites finish — find the earliest completion time of every job; (3) find the longest weighted path from a source in a DAG.

Example 1

Input:  jobs: n = 4, edges 1→2, 1→3, 2→4, 3→4
Output: completion times: 1, 2, 2, 3

Also asked as: Implement Topological Sort · Minimum time taken by each job to be completed given by a Directed Acyclic Graph · Longest path in a Directed Acyclic Graph

1. Kahn's order, then relax in that order

Time O(V + E)Space O(V + E)

Process nodes in topological order. Job time: finish[v] = 1 + max(finish[u]) over predecessors. Longest path: dist[v] = max(dist[u] + w) — a simple DP once the order is fixed.

function longestPathDAG(n, edges) { // edges: [u, v, w]
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v, w] of edges) { adj[u].push([v, w]); indeg[v]++; }
  const q = [];
  for (let i = 0; i < n; i++) if (!indeg[i]) q.push(i);
  const dist = new Array(n).fill(0);
  for (let i = 0; i < q.length; i++) {
    const u = q[i];
    for (const [v, w] of adj[u]) {
      dist[v] = Math.max(dist[v], dist[u] + w);
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return Math.max(...dist);
}

Alien dictionary — order of lettersHard1 approach

Problem

An alien language uses English letters in an unknown order. Given a list of words sorted in that language's order, deduce an order of the letters that is consistent with it, or return "" if the list is contradictory.

Example 1

Input:  ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"

Also asked as: Given a sorted Dictionary of an Alien Language, find order of characters

1. Build a precedence graph from adjacent words, topological sort

Time O(total chars)Space O(1) — 26 letters

For each adjacent pair of words, the first differing character gives an edge a → b. Topologically sort the letters. A prefix that comes after its extension is invalid.

function alienOrder(words) {
  const adj = new Map(), indeg = new Map();
  for (const w of words) for (const c of w) { adj.set(c, adj.get(c) || new Set()); indeg.set(c, 0); }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i + 1];
    if (a.length > b.length && a.startsWith(b)) return '';
    for (let j = 0; j < Math.min(a.length, b.length); j++) {
      if (a[j] !== b[j]) {
        if (!adj.get(a[j]).has(b[j])) { adj.get(a[j]).add(b[j]); indeg.set(b[j], indeg.get(b[j]) + 1); }
        break;
      }
    }
  }
  const q = [...indeg].filter(([, d]) => d === 0).map(([c]) => c);
  let order = '';
  for (let i = 0; i < q.length; i++) {
    order += q[i];
    for (const nb of adj.get(q[i])) if (indeg.set(nb, indeg.get(nb) - 1).get(nb) === 0) q.push(nb);
  }
  return order.length === indeg.size ? order : '';
}

Minimum spanning tree — Kruskal and PrimMedium2 approaches

Problem

Given a connected, weighted, undirected graph, choose a subset of edges that connects every node with the minimum total weight (a spanning tree with no cycles). Return that weight. Min Cost to Connect All Points is the same problem with Manhattan distance as the edge weight.

Example 1

Input:  edges (u, v, w) = [[0,1,10], [0,2,6], [0,3,5], [1,3,15], [2,3,4]]
Output: 19

Edges 2–3 (4), 0–3 (5) and 0–1 (10).

Also asked as: Implement Kruksal’sAlgorithm · Implement Prim’s Algorithm · Total no. of Spanning tree in a graph

1. Kruskal — sort edges, Union-Find to avoid cycles

Time O(E log E)Space O(V)

Add the cheapest edge that connects two different components; stop after V−1 edges.

function kruskal(n, edges) { // edges: [u, v, w]
  edges.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  let cost = 0, used = 0;
  for (const [u, v, w] of edges) {
    const ru = find(u), rv = find(v);
    if (ru !== rv) { parent[ru] = rv; cost += w; used++; }
  }
  return used === n - 1 ? cost : -1; // -1 ⇒ disconnected
}

2. Prim — grow the tree from one node, always take the cheapest crossing edge

Time O(E log V)Space O(V + E)

Min-priority queue of edges leaving the current tree; repeatedly add the lightest edge to a new node.

function prim(adj) { // adj[u] = [[v, w], ...]
  const n = adj.length;
  const inMST = new Array(n).fill(false);
  const pq = [[0, 0]];
  let cost = 0;
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [w, u] = pq.shift();
    if (inMST[u]) continue;
    inMST[u] = true; cost += w;
    for (const [v, w2] of adj[u]) if (!inMST[v]) pq.push([w2, v]);
  }
  return cost;
}

Counting all spanning trees uses Kirchhoff’s Matrix-Tree Theorem: the determinant of any cofactor of the Laplacian (degree matrix − adjacency matrix).

Bellman–Ford and detecting a negative cycleMedium1 approach

Problem

Find the shortest distances from a source in a graph whose edges may have negative weights, and report whether the graph contains a negative-weight cycle (in which case shortest paths are undefined).

Example 1

Input:  edges = [[0,1,-1], [0,2,4], [1,2,3], [1,3,2], [1,4,2], [3,2,5], [3,1,1], [4,3,-3]], source 0
Output: [0, -1, 2, -2, 1], no negative cycle

Also asked as: Implement Bellman Ford Algorithm · Detect Negative cycle in a graph

1. Relax all edges V−1 times; a further relaxation means a negative cycle

Time O(V·E)Space O(V)

Handles negative weights. If any edge can still be relaxed after V−1 rounds, a negative cycle is reachable.

function bellmanFord(n, edges, src) { // edges: [u, v, w]
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i < n - 1; i++)
    for (const [u, v, w] of edges)
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  for (const [u, v, w] of edges)
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) return { negativeCycle: true };
  return { dist };
}

Floyd–Warshall (all-pairs shortest paths)Medium1 approach

Problem

Given a weighted adjacency matrix (∞ where there is no edge), return the shortest distance between every pair of nodes.

Example 1

Input:  [[0,3,∞,7], [8,0,2,∞], [5,∞,0,1], [2,∞,∞,0]]
Output: [[0,3,5,6], [5,0,2,3], [3,6,0,1], [2,5,7,0]]

Also asked as: Implement Floyd warshallAlgorithm

1. DP over intermediate vertices

Time O(V³)Space O(V²)

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every k. Negative cycle iff any dist[i][i] < 0.

function floydWarshall(dist) { // dist[i][j] = weight or Infinity, dist[i][i] = 0
  const n = dist.length;
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
  return dist;
}

Check whether a graph is bipartite / the Two-Clique problemMedium1 approach

Problem

(1) Return true if the nodes can be coloured with two colours so that every edge joins different colours. (2) Two-Clique: return true if the nodes can be split into two groups, each forming a complete subgraph — which holds exactly when the complement graph is bipartite.

Example 1

Input:  adjacency = [[1,3], [0,2], [1,3], [0,2]]
Output: true

Example 2

Input:  [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false

The triangle 0–1–2 cannot be 2-coloured.

Also asked as: Check whether a graph is Bipartite or Not · Two Clique Problem

1. 2-colour with BFS/DFS

Time O(V + E)Space O(V)

Colour a node, colour its neighbours the opposite colour. A conflict means an odd cycle ⇒ not bipartite. "Two cliques": a graph’s vertices split into two cliques iff its COMPLEMENT is bipartite.

function isBipartite(adj) {
  const color = new Array(adj.length).fill(-1);
  for (let s = 0; s < adj.length; s++) {
    if (color[s] !== -1) continue;
    color[s] = 0;
    const q = [s];
    for (let i = 0; i < q.length; i++) {
      const u = q[i];
      for (const v of adj[u]) {
        if (color[v] === -1) { color[v] = color[u] ^ 1; q.push(v); }
        else if (color[v] === color[u]) return false;
      }
    }
  }
  return true;
}

Bridges and articulation pointsHard1 approach

Problem

In an undirected graph, a bridge is an edge whose removal increases the number of connected components. An articulation point is a vertex whose removal does the same. Find them all in O(V + E).

Example 1

Input:  edges 1–0, 0–2, 2–1, 0–3, 3–4
Output: bridges: 0–3, 3–4 · articulation points: 0, 3

Also asked as: Find bridge in a graph

1. Tarjan's DFS with discovery time & low-link

Time O(V + E)Space O(V)

low[u] = earliest discovery time reachable from u’s subtree via one back-edge. Edge (u, v) is a bridge iff low[v] > disc[u]; u is an articulation point iff some child has low[v] ≥ disc[u] (root: ≥ 2 DFS children).

function findBridges(n, adj) {
  const disc = new Array(n).fill(-1), low = new Array(n).fill(0);
  const bridges = [];
  let timer = 0;
  const dfs = (u, parent) => {
    disc[u] = low[u] = timer++;
    for (const v of adj[u]) {
      if (v === parent) continue;
      if (disc[v] === -1) {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) bridges.push([u, v]);
      } else {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  };
  for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
  return bridges;
}

Strongly connected components (Kosaraju)Hard1 approach

Problem

In a directed graph, a strongly connected component is a maximal set of nodes where every node can reach every other. Count (or list) the SCCs.

Example 1

Input:  edges 1→0, 0→2, 2→1, 0→3, 3→4
Output: 3 SCCs: {0, 1, 2}, {3}, {4}

Also asked as: Count Strongly connected Components(Kosaraju Algo)

1. Two passes: finish-time order, then DFS the transpose

Time O(V + E)Space O(V + E)

1) DFS the graph pushing nodes on a stack by finish time. 2) DFS the reversed graph in that stack order — each tree is one SCC.

function kosaraju(n, adj) {
  const radj = Array.from({ length: n }, () => []);
  for (let u = 0; u < n; u++) for (const v of adj[u]) radj[v].push(u);
  const seen = new Array(n).fill(false), order = [];
  const dfs1 = (u) => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs1(v); order.push(u); };
  for (let i = 0; i < n; i++) if (!seen[i]) dfs1(i);
  seen.fill(false);
  let count = 0;
  const dfs2 = (u) => { seen[u] = true; for (const v of radj[u]) if (!seen[v]) dfs2(v); };
  for (let i = order.length - 1; i >= 0; i--) if (!seen[order[i]]) { dfs2(order[i]); count++; }
  return count;
}

Graph / m-colouring problemMedium1 approach

Problem

Return true if the graph's vertices can be coloured with at most m colours so that no edge joins two vertices of the same colour.

Example 1

Input:  4 vertices, edges 0–1, 1–2, 2–3, 3–0, 0–2, m = 3
Output: true

Also asked as: Graph ColouringProblem · M-ColouringProblem · m Coloring Problem

1. Backtracking over vertices

Time O(mⱽ)Space O(V)

Try each colour 1..m for the current vertex if no neighbour already has it; recurse; backtrack.

function canColor(n, adj, m) {
  const color = new Array(n).fill(0);
  const ok = (u, c) => adj[u].every((v) => color[v] !== c);
  const bt = (u) => {
    if (u === n) return true;
    for (let c = 1; c <= m; c++) {
      if (ok(u, c)) { color[u] = c; if (bt(u + 1)) return true; color[u] = 0; }
    }
    return false;
  };
  return bt(0);
}

Travelling Salesman Problem (exact)Hard1 approach

Problem

Given a matrix of distances between n cities, return the length of the shortest tour that starts at city 0, visits every city exactly once, and returns to city 0. n is small (about 15 or fewer), so an exponential bitmask DP is expected.

Example 1

Input:  [[0,10,15,20], [10,0,35,25], [15,35,0,30], [20,25,30,0]]
Output: 80

0 → 1 → 3 → 2 → 0.

Also asked as: Travelling Salesman Problem

1. Bitmask DP (Held–Karp)

Time O(2ⁿ · n²)Space O(2ⁿ · n)

dp[mask][i] = shortest path that visits exactly the set `mask` and ends at city i. Extend to an unvisited city j.

function tsp(dist) {
  const n = dist.length, FULL = (1 << n) - 1;
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
  dp[1][0] = 0;
  for (let mask = 1; mask <= FULL; mask++)
    for (let i = 0; i < n; i++) {
      if (!(mask & (1 << i)) || dp[mask][i] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nm = mask | (1 << j);
        dp[nm][j] = Math.min(dp[nm][j], dp[mask][i] + dist[i][j]);
      }
    }
  let best = Infinity;
  for (let i = 1; i < n; i++) best = Math.min(best, dp[FULL][i] + dist[i][0]);
  return best;
}

Making wired connections / redundant connection (components)Medium1 approach

Problem

(1) Making Wired Connections: n computers and a list of cables. You may unplug any cable and reconnect it elsewhere. Return the minimum number of moves needed to connect every computer, or −1 if there are too few cables (fewer than n − 1). (2) Redundant Connection: a tree had one extra edge added — return the edge that creates the cycle (the last such edge in the input).

Example 1

Input:  n = 4, connections = [[0,1], [0,2], [1,2]]
Output: 1

Example 2

Input:  redundant: [[1,2], [1,3], [2,3]]
Output: [2, 3]

Also asked as: Making wired Connections

1. Union-Find — extra cables vs components to join

Time O(E α(V))Space O(V)

Each edge that connects two already-connected nodes is a spare cable. You can connect c components if you have ≥ c−1 spare cables.

function makeConnected(n, connections) {
  if (connections.length < n - 1) return -1;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  let components = n;
  for (const [a, b] of connections) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { parent[ra] = rb; components--; }
  }
  return components - 1; // moves needed to link all components
}

Journey to the Moon (count invalid pairs)Medium1 approach

Problem

Astronauts from the same country are linked by the given pairs (and transitively). Count the pairs of astronauts from different countries.

Example 1

Input:  n = 5, pairs = [[0,1], [2,3], [0,4]]
Output: 6

Countries {0,1,4} and {2,3}: 3 × 2 = 6.

Also asked as: Journey to the Moon

1. Union-Find component sizes, complement counting

Time O(N + P)Space O(N)

Same-country astronauts are one component. Valid pairs = total pairs − Σ (sizeᵢ choose 2).

function journeyToMoon(n, pairs) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array(n).fill(1);
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  for (const [a, b] of pairs) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { parent[ra] = rb; size[rb] += size[ra]; }
  }
  let sumC2 = 0, done = new Set();
  for (let i = 0; i < n; i++) {
    const r = find(i);
    if (done.has(r)) continue;
    done.add(r);
    sumC2 += (size[r] * (size[r] - 1)) / 2;
  }
  return (n * (n - 1)) / 2 - sumC2;
}

Cheapest flights within K stopsMedium1 approach

Problem

Given flights [from, to, price], a source, a destination and k, return the cheapest price from source to destination using at most k stops (k + 1 flights), or −1 if there is no such route.

Example 1

Input:  n = 4, flights = [[0,1,100], [1,2,100], [2,0,100], [1,3,600], [2,3,200]], src = 0, dst = 3, k = 1
Output: 700

0 → 1 → 3. The cheaper 0 → 1 → 2 → 3 uses 2 stops.

Also asked as: Cheapest Flights Within K Stops

1. Bellman–Ford limited to K+1 relaxations

Time O(K · E)Space O(V)

Relax all edges K+1 times, but each round must read from the previous round’s distances (snapshot) so a path never uses more than K stops.

function findCheapestPrice(n, flights, src, dst, K) {
  let dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i <= K; i++) {
    const snap = dist.slice();
    for (const [u, v, w] of flights)
      if (snap[u] + w < dist[v]) dist[v] = snap[u] + w;
  }
  return dist[dst] === Infinity ? -1 : dist[dst];
}

Water jug problem (reach a target amount)Medium1 approach

Problem

You have jugs of capacity m and n litres and unlimited water. Each step you may fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full. Return the minimum number of steps to measure exactly d litres in either jug, or −1 if impossible.

Example 1

Input:  m = 3, n = 5, d = 4
Output: 6

Also asked as: Water Jug problem using BFS

1. BFS over (jug1, jug2) states

Time O(cap1 · cap2)Space O(cap1 · cap2)

Each state is the pair of current amounts; transitions are fill/empty/pour for either jug. BFS finds the fewest steps to any state containing the target.

function waterJug(cap1, cap2, target) {
  const seen = new Set(['0,0']);
  let q = [[0, 0, 0]];
  while (q.length) {
    const next = [];
    for (const [a, b, d] of q) {
      if (a === target || b === target || a + b === target) return d;
      const moves = [
        [cap1, b], [a, cap2], [0, b], [a, 0],
        [Math.min(a + b, cap1), b - (Math.min(a + b, cap1) - a)],
        [a - (Math.min(a + b, cap2) - b), Math.min(a + b, cap2)],
      ];
      for (const [na, nb] of moves) {
        const key = na + ',' + nb;
        if (!seen.has(key)) { seen.add(key); next.push([na, nb, d + 1]); }
      }
    }
    q = next;
  }
  return -1;
}

Minimum edges to reverse to make a path from source to destinationMedium1 approach

Problem

In a directed graph, return the minimum number of edges whose direction must be reversed so that a path exists from source to destination.

Example 1

Input:  edges 0→1, 2→1, 2→3, 5→1, 4→5, 6→4, 6→3, src = 0, dst = 6
Output: 2

0 → 1 → 2 (reverse 2→1) → 3 → 6 (reverse 6→3).

Also asked as: Minimum edges to reverse o make path from source to destination · Find if there is a path of more thank length from a source

1. 0-1 BFS on a doubled graph

Time O(V + E)Space O(V + E)

Keep every original edge with weight 0 and add its reverse with weight 1. The shortest path (0-1 BFS with a deque) from src to dst is the minimum reversals.

function minReversals(n, edges, src, dst) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push([v, 0]); adj[v].push([u, 1]); }
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const dq = [src];
  while (dq.length) {
    const u = dq.shift();
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        w === 0 ? dq.unshift(v) : dq.push(v);
      }
    }
  }
  return dist[dst] === Infinity ? -1 : dist[dst];
}

"Path of length > k from a source" (sum of edge weights, no revisits) is NP-hard in general — solved by backtracking / DFS with a visited set for small graphs.

Count triangles in a graphMedium1 approach

Problem

Count the triangles (sets of three mutually connected vertices) in a graph given as an adjacency matrix. Note the directed and undirected counts differ in how duplicates are divided out.

Example 1

Input:  undirected [[0,1,1,0], [1,0,1,1], [1,1,0,1], [0,1,1,0]]
Output: 2

{0,1,2} and {1,2,3}.

Also asked as: Number of Triangles in a Directed and Undirected Graph

1. Trace of A³ / adjacency-matrix cubing

Time O(V³)Space O(V²)

The number of closed walks of length 3 is trace(A³). Divide by 6 for an undirected graph, by 3 for a directed one.

function countTriangles(A, directed = false) {
  const n = A.length;
  const mul = (X, Y) => {
    const Z = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = 0; i < n; i++)
      for (let k = 0; k < n; k++)
        if (X[i][k]) for (let j = 0; j < n; j++) Z[i][j] += X[i][k] * Y[k][j];
    return Z;
  };
  const A3 = mul(mul(A, A), A);
  let trace = 0;
  for (let i = 0; i < n; i++) trace += A3[i][i];
  return trace / (directed ? 3 : 6);
}

Minimise cash flow among friendsMedium1 approach

Problem

graph[i][j] is how much person i owes person j. Settle every debt using the fewest transactions (or the smallest total amount moved), by working out each person's net balance.

Example 1

Input:  [[0,1000,2000], [0,0,5000], [0,0,0]]
Output: Person 1 pays 4000 to person 2; person 0 pays 3000 to person 2

Also asked as: Minimise the cashflow among a given set of friends who have borrowed money from each other · Minimize Cash Flow among a given set of friends who have borrowed money from each other

1. Net balance per person, greedily settle max creditor with max debtor

Time O(n²)Space O(n)

Compute each person’s net (received − paid). Repeatedly pick the biggest positive and biggest negative balance; settle min(|a|, |b|); repeat until all are zero.

function minCashFlow(graph) { // graph[i][j] = amount i owes j
  const n = graph.length;
  const net = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) { net[i] += graph[j][i]; net[i] -= graph[i][j]; }
  const txns = [];
  const settle = () => {
    let mxCredit = net.indexOf(Math.max(...net));
    let mxDebit = net.indexOf(Math.min(...net));
    if (net[mxCredit] === 0 && net[mxDebit] === 0) return;
    const amt = Math.min(-net[mxDebit], net[mxCredit]);
    net[mxCredit] -= amt; net[mxDebit] += amt;
    txns.push([mxDebit, mxCredit, amt]);
    settle();
  };
  settle();
  return txns;
}

Euler path / circuit — Seven Bridges, Chinese PostmanHard1 approach

Problem

(1) Decide whether an undirected graph has an Euler circuit (every edge used once, ending at the start: all degrees even) or an Euler path (exactly 0 or 2 odd-degree vertices). (2) Chinese Postman: the shortest closed walk that uses every edge at least once — pair up the odd-degree vertices and add the cheapest duplicate paths.

Example 1

Input:  edges 0–1, 0–2, 1–2, 2–3
Output: Euler path (vertices 2 and 3 have odd degree), no circuit

Also asked as: Paths to travel each nodes using each edge(Seven Bridges) · Chinese Postman or Route Inspection

1. Degree conditions + Hierholzer

Time O(E) for HierholzerSpace O(E)

An undirected connected graph has an Euler circuit iff every vertex has even degree; an Euler path iff exactly 0 or 2 vertices have odd degree (the Seven Bridges graph has 4 odd, so no path). Hierholzer’s algorithm builds the trail in O(E). Chinese Postman: pair up odd-degree vertices with minimum-weight matching and duplicate those shortest paths, then take an Euler circuit.

function hierholzer(n, adj) { // adj[u] = multiset of neighbours; assumes an Euler circuit exists
  const stack = [0], circuit = [];
  const local = adj.map((l) => [...l]);
  while (stack.length) {
    const u = stack[stack.length - 1];
    if (local[u].length) {
      const v = local[u].pop();
      local[v].splice(local[v].indexOf(u), 1);
      stack.push(v);
    } else {
      circuit.push(stack.pop());
    }
  }
  return circuit.reverse();
}

Vertex Cover ProblemHard1 approach

Problem

Find a smallest set of vertices such that every edge has at least one endpoint in the set. The problem is NP-hard in general: know the 2-approximation (take both ends of any uncovered edge) and the exact DP for trees.

Example 1

Input:  edges 0–1, 0–2, 1–3, 3–4, 4–5, 5–6
Output: e.g. {0, 3, 5} or {0, 3, 4, 6}

Also asked as: Vertex Cover Problem

1. Tree DP (exact) / 2-approximation (general graph)

Time O(n) tree / O(E) approxSpace O(n)

On a tree: dp[node][0/1] = min cover of the subtree when node is / is not in the cover; if a node is excluded, all children must be included. General graph: pick any uncovered edge, add BOTH endpoints to the cover — this is a 2-approximation (exact vertex cover is NP-hard).

function vertexCoverTree(node) {
  if (!node) return [0, 0]; // [notInCover, inCover]
  const L = vertexCoverTree(node.left);
  const R = vertexCoverTree(node.right);
  const notIn = L[1] + R[1];                        // children must be covered
  const inCover = 1 + Math.min(L[0], L[1]) + Math.min(R[0], R[1]);
  return [notIn, inCover];
}
// answer: Math.min(...vertexCoverTree(root))

function approxVertexCover(n, edges) {
  const used = new Set();
  const covered = new Set();
  for (const [u, v] of edges) {
    if (covered.has(u) || covered.has(v)) continue;
    used.add(u); used.add(v);
    covered.add(u); covered.add(v);
  }
  return [...used];
}

Oliver and the Game (ancestor check on a rooted tree)Medium1 approach

Problem

A tree of houses is rooted at 1 (the King's mansion). For each query (type, X, Y), Bob hides at Y. Type 0: can Oliver reach X by moving towards the root from Y? Type 1: can he reach X by moving away from the root from Y? Answer YES/NO. This reduces to "is X an ancestor of Y?" and can be answered with DFS entry/exit times.

Example 1

Input:  edges 1–2, 1–3, 2–6, 2–7, 6–9, 7–8, 3–4, 3–5, 5–10; query (0, 2, 8)
Output: YES

8 → 7 → 2 moves towards the root.

Also asked as: Oliver and the Game · Oliver and the Game

1. Euler tour in/out times

Time O(n + q)Space O(n)

DFS from the king’s node recording in[v] and out[v]. u is an ancestor of v iff in[u] ≤ in[v] and out[v] ≤ out[u]. Each query (who moves toward/away from the king) is then O(1).

function eulerTour(n, adj, root = 1) {
  const tin = new Array(n + 1).fill(0), tout = new Array(n + 1).fill(0);
  let timer = 0;
  const dfs = (u, parent) => {
    tin[u] = ++timer;
    for (const v of adj[u]) if (v !== parent) dfs(v, u);
    tout[u] = ++timer;
  };
  dfs(root, 0);
  const isAncestor = (u, v) => tin[u] <= tin[v] && tout[v] <= tout[u];
  return { isAncestor };
}

Max Area of IslandMedium1 approach

Problem

In a binary grid, an island is a group of 1s connected up, down, left or right. Return the area (cell count) of the largest island, or 0 if there is none.

Example 1

Input:  [[0,0,1,0,0], [0,1,1,1,0], [0,0,1,0,0], [1,1,0,0,0]]
Output: 5

1. DFS returning area

Time O(R·C)Space O(R·C) recursion worst case

Sink each land cell as you visit it and return 1 + the areas of its four neighbours.

function maxAreaOfIsland(grid) {
  const R = grid.length, C = grid[0].length;
  const area = (r, c) => {
    if (r < 0 || c < 0 || r >= R || c >= C || grid[r][c] !== 1) return 0;
    grid[r][c] = 0;
    return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1);
  };
  let best = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) best = Math.max(best, area(r, c));
  return best;
}

Pacific Atlantic Water FlowMedium1 approach

Problem

heights is an island grid. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges. Water flows from a cell to a neighbour of equal or lower height. Return every cell from which water can reach both oceans.

Example 1

Input:  [[1,2,2,3,5], [3,2,3,4,4], [2,4,5,3,1], [6,7,1,4,5], [5,1,1,2,4]]
Output: [[0,4], [1,3], [1,4], [2,2], [3,0], [3,1], [4,0]]

1. Reverse flow from each ocean

Time O(R·C)Space O(R·C)

Instead of testing every cell, spread uphill from each ocean’s border. Cells reached from both oceans are the answer.

function pacificAtlantic(h) {
  const R = h.length, C = h[0].length;
  const mk = () => Array.from({ length: R }, () => new Array(C).fill(false));
  const pac = mk(), atl = mk();
  const dfs = (r, c, seen) => {
    seen[r][c] = true;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < R && nc < C && !seen[nr][nc] && h[nr][nc] >= h[r][c])
        dfs(nr, nc, seen);
    }
  };
  for (let r = 0; r < R; r++) { dfs(r, 0, pac); dfs(r, C - 1, atl); }
  for (let c = 0; c < C; c++) { dfs(0, c, pac); dfs(R - 1, c, atl); }
  const res = [];
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (pac[r][c] && atl[r][c]) res.push([r, c]);
  return res;
}

Surrounded RegionsMedium1 approach

Problem

The board contains "X" and "O". Capture every region of "O"s that is completely surrounded by "X" by flipping it to "X". A region touching the border is never captured. Modify the board in place.

Example 1

Input:  [["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"]]
Output: [["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"]]

The bottom O touches the border, so it survives.

1. Protect border-connected cells, flip the rest

Time O(R·C)Space O(R·C) recursion worst case

Any "O" connected to the border survives. Mark those from the border as "S", flip remaining "O" to "X", then restore "S" to "O".

function solve(board) {
  const R = board.length, C = board[0].length;
  const mark = (r, c) => {
    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== 'O') return;
    board[r][c] = 'S';
    mark(r + 1, c); mark(r - 1, c); mark(r, c + 1); mark(r, c - 1);
  };
  for (let r = 0; r < R; r++) { mark(r, 0); mark(r, C - 1); }
  for (let c = 0; c < C; c++) { mark(0, c); mark(R - 1, c); }
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      board[r][c] = board[r][c] === 'S' ? 'O' : 'X';
}

Minimum Height TreesMedium1 approach

Problem

A tree has n nodes and n − 1 edges. Rooting it at different nodes gives different heights. Return every node that gives the minimum height.

Example 1

Input:  n = 4, edges = [[1,0], [1,2], [1,3]]
Output: [1]

Example 2

Input:  n = 6, edges = [[3,0], [3,1], [3,2], [3,4], [5,4]]
Output: [3, 4]

1. Peel leaves layer by layer

Time O(n)Space O(n)

Topological-sort style on an undirected tree: repeatedly remove all leaves (degree 1). The last one or two nodes are the centres.

function findMinHeightTrees(n, edges) {
  if (n === 1) return [0];
  const adj = Array.from({ length: n }, () => []);
  const deg = new Array(n).fill(0);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); deg[a]++; deg[b]++; }
  let leaves = [];
  for (let i = 0; i < n; i++) if (deg[i] === 1) leaves.push(i);
  let left = n;
  while (left > 2) {
    left -= leaves.length;
    const next = [];
    for (const u of leaves) for (const v of adj[u]) if (--deg[v] === 1) next.push(v);
    leaves = next;
  }
  return leaves;
}

Number of Connected Components in an Undirected GraphMedium2 approaches

Problem

Given n nodes labelled 0..n−1 and a list of undirected edges, return the number of connected components.

Example 1

Input:  n = 5, edges = [[0,1], [1,2], [3,4]]
Output: 2

1. DFS from each unvisited node

Time O(V + E)Space O(V + E)

Each DFS start is a new component.

function countComponents(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const seen = new Array(n).fill(false);
  const dfs = (u) => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs(v); };
  let count = 0;
  for (let i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); }
  return count;
}

2. Union-Find

Time O(E · α(n))Space O(n)

Start with n components; every successful union merges two, so subtract one.

function countComponents(n, edges) {
  const parent = [...Array(n).keys()];
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  let count = n;
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { parent[ra] = rb; count--; }
  }
  return count;
}

Graph Valid TreeMedium1 approach

Problem

Given n nodes and a list of undirected edges, return true if they form a valid tree: connected, with no cycle.

Example 1

Input:  n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2

Input:  n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

1. Edge count + Union-Find

Time O(n · α(n))Space O(n)

A tree on n nodes has exactly n − 1 edges and no cycle. With the right edge count, any union that finds both ends already joined means a cycle.

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const parent = [...Array(n).keys()];
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
  }
  return true;
}

Accounts MergeMedium1 approach

Problem

Each account is [name, email1, email2, …]. Two accounts belong to the same person if they share any email (names alone prove nothing). Merge them and return each person as [name, …their emails sorted].

Example 1

Input:  [["John","a@x","b@x"], ["John","c@x"], ["John","b@x","d@x"], ["Mary","m@x"]]
Output: [["John","a@x","b@x","d@x"], ["John","c@x"], ["Mary","m@x"]]

1. Union-Find over emails

Time O(N log N) — N total emails, dominated by sortingSpace O(N)

Union every email in an account with that account’s first email. Group emails by root, sort each group, prefix the owner’s name.

function accountsMerge(accounts) {
  const parent = new Map(), owner = new Map();
  const find = (x) => {
    if (parent.get(x) !== x) parent.set(x, find(parent.get(x)));
    return parent.get(x);
  };
  for (const [name, ...emails] of accounts) {
    for (const e of emails) {
      if (!parent.has(e)) parent.set(e, e);
      owner.set(e, name);
      parent.set(find(e), find(emails[0]));
    }
  }
  const groups = new Map();
  for (const e of parent.keys()) {
    const r = find(e);
    if (!groups.has(r)) groups.set(r, []);
    groups.get(r).push(e);
  }
  return [...groups.values()].map((g) => [owner.get(g[0]), ...g.sort()]);
}

Number of ProvincesMedium1 approach

Problem

isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.

Example 1

Input:  [[1,1,0], [1,1,0], [0,0,1]]
Output: 2

1. DFS on the adjacency matrix

Time O(n²)Space O(n)

Count how many DFS starts are needed to visit every city.

function findCircleNum(M) {
  const n = M.length, seen = new Array(n).fill(false);
  const dfs = (i) => {
    seen[i] = true;
    for (let j = 0; j < n; j++) if (M[i][j] && !seen[j]) dfs(j);
  };
  let count = 0;
  for (let i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); }
  return count;
}

Path With Minimum EffortMedium1 approach

Problem

Move up, down, left or right from the top-left cell to the bottom-right cell of a height grid. A route's effort is its largest absolute height difference between two consecutive cells. Return the minimum possible effort.

Example 1

Input:  [[1,2,2], [3,8,2], [5,3,5]]
Output: 2

The route 1→3→5→3→5 never steps by more than 2.

1. Dijkstra on the maximum step

Time O(R·C log(R·C))Space O(R·C)

Path cost is its largest height difference, not a sum. Dijkstra still works: always expand the cell with the smallest effort so far. MinHeap is the class from the patterns page.

function minimumEffortPath(h) {
  const R = h.length, C = h[0].length;
  const dist = Array.from({ length: R }, () => new Array(C).fill(Infinity));
  dist[0][0] = 0;
  const pq = new MinHeap((a, b) => a[0] - b[0]);
  pq.push([0, 0, 0]);
  while (pq.size) {
    const [d, r, c] = pq.pop();
    if (r === R - 1 && c === C - 1) return d;
    if (d > dist[r][c]) continue; // stale entry
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
      const nd = Math.max(d, Math.abs(h[nr][nc] - h[r][c]));
      if (nd < dist[nr][nc]) { dist[nr][nc] = nd; pq.push([nd, nr, nc]); }
    }
  }
  return 0;
}

Alternatives: binary search on the effort + BFS, or Union-Find adding edges in increasing weight.