Frontend Prep

Appearance

01 - DSA: Graphs ​

Why This Matters for Temple ​

Temple (ex-Zomato founding team) leans heavy on core CS fundamentals. Graphs show up everywhere: dependency resolution, network modeling, shortest-path routing, scheduling. Expect whiteboard-style problems and follow-ups on complexity.

Quick Reference ​

Scan this table in 5 minutes before your interview.

AlgorithmTimeSpaceKey IdeaWhen to Use
BFSO(V + E)O(V)Level-by-level exploration using a queueShortest path in unweighted graph, level-order
DFSO(V + E)O(V)Go deep via recursion/stack, backtrackPath finding, cycle detection, connected components
Topological Sort (Kahn's)O(V + E)O(V)Process zero in-degree nodes firstDependency ordering, course scheduling
Topological Sort (DFS)O(V + E)O(V)Post-order DFS, reverse the resultSame as above, sometimes cleaner recursion
DijkstraO((V + E) log V)O(V)Greedy + min-heap, relax edgesShortest path in weighted graph (non-negative)
Cycle Detection (Directed)O(V + E)O(V)3-color DFS: WHITE/GRAY/BLACKDetecting back edges in directed graphs
Cycle Detection (Undirected)O(V + E)O(V)DFS with parent trackingDetecting cycles in undirected graphs
Union-FindO(alpha(n)) amortizedO(V)Path compression + union by rankDynamic connectivity, Kruskal's MST
Bipartite CheckO(V + E)O(V)BFS 2-coloringOdd-cycle detection, 2-partition problems
Bellman-FordO(V * E)O(V)Relax all edges V-1 timesNegative weights, negative cycle detection
Floyd-WarshallO(V^3)O(V^2)All-pairs via DP on intermediate nodesAll-pairs shortest path, small dense graphs
Prim's MSTO((V + E) log V)O(V)Greedy — always pick cheapest edge from treeMinimum spanning tree (dense graphs)
Kruskal's MSTO(E log E)O(V)Sort edges + Union-FindMinimum spanning tree (sparse graphs)
Kosaraju's SCCO(V + E)O(V)Two-pass DFS on original + reversed graphStrongly connected components

1. Graph Representations ​

Adjacency List ​

Best for sparse graphs (most real-world graphs). Space: O(V + E).

ts
// Unweighted adjacency list
function buildAdjList(n: number, edges: number[][]): Map<number, number[]> {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) {
    graph.set(i, []);
  }
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u); // remove for directed graph
  }
  return graph;
}

// Weighted adjacency list
function buildWeightedAdjList(
  n: number,
  edges: [number, number, number][]
): Map<number, [number, number][]> {
  const graph = new Map<number, [number, number][]>();
  for (let i = 0; i < n; i++) {
    graph.set(i, []);
  }
  for (const [u, v, w] of edges) {
    graph.get(u)!.push([v, w]);
    graph.get(v)!.push([u, w]); // remove for directed graph
  }
  return graph;
}

Adjacency Matrix ​

Best for dense graphs or when you need O(1) edge lookup. Space: O(V^2).

ts
function buildAdjMatrix(n: number, edges: number[][]): number[][] {
  const matrix: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  for (const [u, v] of edges) {
    matrix[u][v] = 1;
    matrix[v][u] = 1; // remove for directed graph
  }
  return matrix;
}

// Weighted version — store weights instead of 1/0
function buildWeightedAdjMatrix(
  n: number,
  edges: [number, number, number][]
): number[][] {
  const matrix: number[][] = Array.from({ length: n }, () =>
    Array(n).fill(Infinity)
  );
  for (let i = 0; i < n; i++) matrix[i][i] = 0;
  for (const [u, v, w] of edges) {
    matrix[u][v] = w;
    matrix[v][u] = w; // remove for directed graph
  }
  return matrix;
}

Trade-offs ​

OperationAdjacency ListAdjacency Matrix
SpaceO(V + E)O(V^2)
Check if edge existsO(degree)O(1)
Iterate neighborsO(degree)O(V)
Add edgeO(1)O(1)
Best forSparse graphs, most problemsDense graphs, Floyd-Warshall

Rule of thumb: Use adjacency list unless you need constant-time edge queries or E is close to V^2.

2. BFS (Breadth-First Search) ​

BFS explores level by level. It naturally finds the shortest path in an unweighted graph.

Template ​

ts
function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>([start]);
  const queue: number[] = [start];
  const order: number[] = [];

  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

BFS with Distance Tracking ​

ts
function bfsWithDistance(
  graph: Map<number, number[]>,
  start: number
): Map<number, number> {
  const dist = new Map<number, number>([[start, 0]]);
  const queue: number[] = [start];

  while (queue.length > 0) {
    const node = queue.shift()!;
    const currentDist = dist.get(node)!;

    for (const neighbor of graph.get(node) || []) {
      if (!dist.has(neighbor)) {
        dist.set(neighbor, currentDist + 1);
        queue.push(neighbor);
      }
    }
  }

  return dist;
}

Multi-Source BFS ​

Used when you have multiple starting points (e.g., "rotting oranges", "walls and gates").

ts
function multiSourceBfs(
  grid: number[][],
  sources: [number, number][]
): number[][] {
  const rows = grid.length;
  const cols = grid[0].length;
  const dist: number[][] = Array.from({ length: rows }, () =>
    Array(cols).fill(-1)
  );
  const queue: [number, number][] = [];

  // Enqueue all sources at distance 0
  for (const [r, c] of sources) {
    dist[r][c] = 0;
    queue.push([r, c]);
  }

  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];

  let idx = 0;
  while (idx < queue.length) {
    const [r, c] = queue[idx++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (
        nr >= 0 &&
        nr < rows &&
        nc >= 0 &&
        nc < cols &&
        dist[nr][nc] === -1
      ) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return dist;
}

When to Use BFS ​

  • Shortest path in an unweighted graph
  • Level-order traversal (trees or graphs)
  • Multi-source shortest distance
  • Anything that asks "minimum number of steps/moves"

3. DFS (Depth-First Search) ​

DFS goes as deep as possible before backtracking. Two flavors: recursive and iterative.

Recursive Template ​

ts
function dfsRecursive(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const order: number[] = [];

  function dfs(node: number): void {
    visited.add(node);
    order.push(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  dfs(start);
  return order;
}

Iterative Template ​

ts
function dfsIterative(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const stack: number[] = [start];
  const order: number[] = [];

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);

    // Push neighbors in reverse to maintain left-to-right order
    const neighbors = graph.get(node) || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return order;
}

DFS on a Grid (Flood Fill Pattern) ​

Used in "Number of Islands", "Surrounded Regions", etc.

ts
function dfsGrid(grid: string[][], r: number, c: number): void {
  const rows = grid.length;
  const cols = grid[0].length;

  if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") {
    return;
  }

  grid[r][c] = "0"; // mark visited
  dfsGrid(grid, r + 1, c);
  dfsGrid(grid, r - 1, c);
  dfsGrid(grid, r, c + 1);
  dfsGrid(grid, r, c - 1);
}

When to Use DFS ​

  • Path finding / path existence
  • Cycle detection
  • Connected components
  • Topological sort
  • Backtracking (permutations, combinations)
  • Anything that asks "does a path exist" or "find all paths"

4. Topological Sort ​

Linear ordering of vertices such that for every directed edge u -> v, u comes before v. Only works on DAGs (Directed Acyclic Graphs). If a cycle exists, topological sort is impossible.

Kahn's Algorithm (BFS-Based, In-Degree) ​

This is the most intuitive approach. Process nodes with in-degree 0, then reduce in-degrees.

ts
function topologicalSortKahn(
  numNodes: number,
  edges: number[][] // [prerequisite, dependent]
): number[] {
  const graph = new Map<number, number[]>();
  const inDegree = new Array(numNodes).fill(0);

  for (let i = 0; i < numNodes; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    inDegree[v]++;
  }

  // Start with all nodes that have no prerequisites
  const queue: number[] = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);

    for (const neighbor of graph.get(node)!) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // If order doesn't include all nodes, there's a cycle
  if (order.length !== numNodes) {
    return []; // cycle detected — no valid topological order
  }

  return order;
}

DFS-Based Topological Sort ​

Post-order DFS: add node to result after processing all descendants, then reverse.

ts
function topologicalSortDFS(
  numNodes: number,
  edges: number[][]
): number[] {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < numNodes; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
  }

  const visited = new Set<number>();
  const stack: number[] = [];
  let hasCycle = false;
  const visiting = new Set<number>(); // for cycle detection

  function dfs(node: number): void {
    if (hasCycle) return;
    visiting.add(node);
    visited.add(node);

    for (const neighbor of graph.get(node)!) {
      if (visiting.has(neighbor)) {
        hasCycle = true;
        return;
      }
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }

    visiting.delete(node);
    stack.push(node); // post-order
  }

  for (let i = 0; i < numNodes; i++) {
    if (!visited.has(i)) {
      dfs(i);
    }
  }

  if (hasCycle) return [];
  return stack.reverse();
}

When to Use ​

  • Course scheduling: Course Schedule I (can you finish?) and II (in what order?)
  • Build systems: compile dependencies in the right order
  • Task scheduling: any problem with prerequisite relationships
  • Cycle detection in directed graphs (if topo sort fails, cycle exists)

5. Cycle Detection ​

Directed Graph: 3-Color Method (WHITE / GRAY / BLACK) ​

  • WHITE (0): unvisited
  • GRAY (1): in current DFS path (on the recursion stack)
  • BLACK (2): fully processed

A cycle exists if we encounter a GRAY node during DFS (back edge).

ts
enum Color {
  WHITE = 0,
  GRAY = 1,
  BLACK = 2,
}

function hasCycleDirected(
  numNodes: number,
  edges: number[][]
): boolean {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < numNodes; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
  }

  const color: Color[] = new Array(numNodes).fill(Color.WHITE);

  function dfs(node: number): boolean {
    color[node] = Color.GRAY;

    for (const neighbor of graph.get(node)!) {
      if (color[neighbor] === Color.GRAY) {
        return true; // back edge — cycle found
      }
      if (color[neighbor] === Color.WHITE && dfs(neighbor)) {
        return true;
      }
    }

    color[node] = Color.BLACK;
    return false;
  }

  for (let i = 0; i < numNodes; i++) {
    if (color[i] === Color.WHITE && dfs(i)) {
      return true;
    }
  }

  return false;
}

Undirected Graph: Parent Tracking ​

In undirected graphs, we track the parent to avoid counting the edge we came from as a cycle.

ts
function hasCycleUndirected(
  numNodes: number,
  edges: number[][]
): boolean {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < numNodes; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u);
  }

  const visited = new Set<number>();

  function dfs(node: number, parent: number): boolean {
    visited.add(node);

    for (const neighbor of graph.get(node)!) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true; // visited neighbor that isn't our parent — cycle
      }
    }

    return false;
  }

  for (let i = 0; i < numNodes; i++) {
    if (!visited.has(i) && dfs(i, -1)) {
      return true;
    }
  }

  return false;
}

Quick Comparison ​

DirectedUndirected
Method3-color (WHITE/GRAY/BLACK)Parent tracking
Cycle indicatorBack edge to GRAY nodeEdge to visited non-parent
Also detects viaTopological sort failureUnion-Find

6. Dijkstra's Algorithm ​

Finds the shortest path from a source to all other nodes in a weighted graph with non-negative weights.

Uses a min-heap (priority queue) for greedy selection of the next closest node.

Min-Heap Helper ​

JavaScript doesn't have a built-in heap, so here is a minimal implementation for interviews.

ts
class MinHeap<T> {
  private heap: T[] = [];
  private compareFn: (a: T, b: T) => number;

  constructor(compareFn: (a: T, b: T) => number) {
    this.compareFn = compareFn;
  }

  get size(): number {
    return this.heap.length;
  }

  push(val: T): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compareFn(this.heap[i], this.heap[parent]) < 0) {
        [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
        i = parent;
      } else {
        break;
      }
    }
  }

  private sinkDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.compareFn(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      if (right < n && this.compareFn(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }
      if (smallest !== i) {
        [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
        i = smallest;
      } else {
        break;
      }
    }
  }
}

Dijkstra Implementation ​

ts
function dijkstra(
  graph: Map<number, [number, number][]>, // node -> [neighbor, weight]
  source: number,
  n: number
): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

  // Min-heap of [distance, node]
  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
  heap.push([0, source]);

  while (heap.size > 0) {
    const [d, u] = heap.pop()!;

    // Skip if we've already found a shorter path
    if (d > dist[u]) continue;

    for (const [v, w] of graph.get(u) || []) {
      const newDist = dist[u] + w;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        heap.push([newDist, v]);
      }
    }
  }

  return dist;
}

Example Usage: Network Delay Time (LC 743) ​

ts
function networkDelayTime(times: number[][], n: number, k: number): number {
  const graph = new Map<number, [number, number][]>();
  for (let i = 1; i <= n; i++) graph.set(i, []);
  for (const [u, v, w] of times) {
    graph.get(u)!.push([v, w]);
  }

  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;

  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
  heap.push([0, k]);

  while (heap.size > 0) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue;

    for (const [v, w] of graph.get(u)!) {
      const newDist = dist[u] + w;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        heap.push([newDist, v]);
      }
    }
  }

  let maxDist = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    maxDist = Math.max(maxDist, dist[i]);
  }
  return maxDist;
}

Key Points ​

  • Time: O((V + E) log V) with a binary heap
  • Does NOT work with negative weights (use Bellman-Ford for that)
  • The "skip if d > dist[u]" line is critical -- it avoids reprocessing stale entries
  • In an interview, mention that JS lacks a native heap and you'd normally import one

7. Connected Components / Union-Find ​

Union-Find (Disjoint Set Union) with Path Compression + Union by Rank ​

This is the gold standard for dynamic connectivity problems.

ts
class UnionFind {
  parent: number[];
  rank: number[];
  count: number; // number of connected components

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) return false; // already connected

    // Union by rank — attach smaller tree under larger tree
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }

    this.count--;
    return true;
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}

Example Usage: Number of Connected Components ​

ts
function countComponents(n: number, edges: number[][]): number {
  const uf = new UnionFind(n);
  for (const [u, v] of edges) {
    uf.union(u, v);
  }
  return uf.count;
}

When to Use Union-Find ​

  • Dynamic connectivity: "are these two nodes connected?" with incremental edge additions
  • Kruskal's MST: sort edges by weight, union them greedily
  • Number of islands (alternative to DFS/BFS)
  • Accounts merge, redundant connection, graph valid tree
  • Any time you need to merge groups and query membership efficiently

Complexity ​

  • find: O(alpha(n)) amortized -- practically O(1)
  • union: O(alpha(n)) amortized
  • alpha(n) is the inverse Ackermann function; it grows insanely slowly (<=4 for all practical n)

8. Bipartite Check ​

A graph is bipartite if its vertices can be colored with two colors such that no two adjacent vertices share the same color. Equivalently, the graph has no odd-length cycles.

BFS Coloring Approach ​

ts
function isBipartite(graph: number[][]): boolean {
  const n = graph.length;
  const color: number[] = new Array(n).fill(-1); // -1 = uncolored

  for (let i = 0; i < n; i++) {
    if (color[i] !== -1) continue; // already colored

    // BFS from node i
    const queue: number[] = [i];
    color[i] = 0;

    while (queue.length > 0) {
      const node = queue.shift()!;

      for (const neighbor of graph[node]) {
        if (color[neighbor] === -1) {
          color[neighbor] = 1 - color[node]; // alternate color
          queue.push(neighbor);
        } else if (color[neighbor] === color[node]) {
          return false; // same color on adjacent nodes — not bipartite
        }
      }
    }
  }

  return true;
}

When to Use ​

  • Is Graph Bipartite? (LC 785) -- direct application
  • Possible Bipartition (LC 886) -- model dislikes as edges, check bipartiteness
  • 2-coloring problems in general
  • Quick test: if you find an odd cycle, the graph is NOT bipartite

9. BFS Shortest Path (Source → Destination) ​

When you need the shortest path between two specific nodes in an unweighted graph.

ts
function shortestPath(
  graph: Map<number, number[]>,
  src: number,
  dest: number
): number {
  const visited = new Set<number>([src]);
  const queue: [number, number][] = [[src, 0]]; // [node, distance]

  while (queue.length > 0) {
    const [node, distance] = queue.shift()!;

    if (node === dest) return distance;

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1]);
      }
    }
  }

  return -1; // unreachable
}

10. Shortest Path in Weighted DAG (Topological Sort Method) ​

For DAGs, topological sort + relaxation is faster than Dijkstra — O(V + E) vs O((V+E) log V).

ts
function shortestPathDAG(
  n: number,
  edges: [number, number, number][], // [from, to, weight]
  source: number
): (number | null)[] {
  // Build weighted adjacency list
  const graph = new Map<number, [number, number][]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v, w] of edges) {
    graph.get(u)!.push([v, w]);
  }

  // Step 1: Topological sort via DFS
  const visited = new Set<number>();
  const stack: number[] = [];

  function topoSort(node: number): void {
    visited.add(node);
    for (const [neighbor] of graph.get(node)!) {
      if (!visited.has(neighbor)) topoSort(neighbor);
    }
    stack.push(node); // post-order
  }

  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) topoSort(i);
  }

  // Step 2: Relax edges in topological order
  const dist: (number | null)[] = new Array(n).fill(null);
  dist[source] = 0;

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (dist[node] === null) continue;

    for (const [neighbor, weight] of graph.get(node)!) {
      const newDist = dist[node]! + weight;
      if (dist[neighbor] === null || newDist < dist[neighbor]!) {
        dist[neighbor] = newDist;
      }
    }
  }

  return dist;
}

When to Use ​

  • Shortest path in a DAG (build system dependencies with costs, critical path)
  • Faster than Dijkstra when you know the graph is acyclic

11. Bellman-Ford Algorithm ​

Finds shortest path from a source, handles negative weights, and detects negative cycles.

Relaxes all edges V-1 times. If any edge can still be relaxed after that, a negative cycle exists.

ts
function bellmanFord(
  n: number,
  edges: [number, number, number][], // [from, to, weight]
  source: number
): { dist: number[]; hasNegativeCycle: boolean } {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

  // Relax all edges V-1 times
  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;
      }
    }
  }

  // Check for negative cycles (one more relaxation pass)
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return { dist, hasNegativeCycle: true };
    }
  }

  return { dist, hasNegativeCycle: false };
}

Key Points ​

  • Time: O(V * E) — slower than Dijkstra but handles negative weights
  • If hasNegativeCycle is true, shortest paths are undefined (can decrease infinitely)
  • Use when the graph has negative edge weights (currency exchange, arbitrage detection)
  • Dijkstra is preferred when all weights are non-negative

When to Use ​

  • Negative edge weights
  • Detecting negative cycles (arbitrage in currency exchange)
  • When graph is small and Dijkstra's heap overhead isn't worth it

12. Floyd-Warshall Algorithm ​

Finds shortest paths between all pairs of vertices. DP approach: "can going through node k improve the path from i to j?"

ts
function floydWarshall(n: number, edges: [number, number, number][]): number[][] {
  const INF = Infinity;
  // Initialize distance matrix
  const dist: number[][] = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  // Fill known edges
  for (const [u, v, w] of edges) {
    dist[u][v] = w;
    // dist[v][u] = w; // uncomment for undirected
  }

  // DP: try every intermediate node k
  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];
        }
      }
    }
  }

  // Optional: detect negative cycles (dist[i][i] < 0)
  for (let i = 0; i < n; i++) {
    if (dist[i][i] < 0) {
      // Negative cycle exists involving node i
    }
  }

  return dist;
}

Key Points ​

  • Time: O(V^3), Space: O(V^2) — only practical for small graphs (V < 500)
  • Works with negative weights (but not negative cycles)
  • The k loop must be the outermost — this is the most common interview mistake
  • Best for: dense graphs where you need all-pairs distances

When to Use ​

  • "Find the city with smallest number of neighbors at a threshold distance" (LC 1334)
  • All-pairs shortest path on small graphs
  • Transitive closure of a graph

13. Minimum Spanning Tree ​

Prim's Algorithm ​

Greedy approach: start from any node, always add the cheapest edge connecting the tree to a non-tree node. Works like Dijkstra but tracks edge weight instead of total distance.

ts
function primMST(
  graph: Map<number, [number, number][]>, // node -> [neighbor, weight]
  n: number
): number {
  const visited = new Array(n).fill(false);
  // Min-heap of [weight, node]
  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
  heap.push([0, 0]); // start from node 0

  let totalCost = 0;

  while (heap.size > 0) {
    const [weight, node] = heap.pop()!;

    if (visited[node]) continue;
    visited[node] = true;
    totalCost += weight;

    for (const [neighbor, w] of graph.get(node) || []) {
      if (!visited[neighbor]) {
        heap.push([w, neighbor]);
      }
    }
  }

  return totalCost;
}

Kruskal's Algorithm ​

Sort all edges by weight, greedily add edges that don't create a cycle (using Union-Find).

ts
function kruskalMST(
  n: number,
  edges: [number, number, number][] // [from, to, weight]
): number {
  // Sort edges by weight ascending
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(n);
  let totalCost = 0;
  let edgesUsed = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      totalCost += w;
      edgesUsed++;
      if (edgesUsed === n - 1) break; // MST complete
    }
  }

  return totalCost;
}

Prim's vs Kruskal's ​

Prim'sKruskal's
ApproachGrow tree from a nodeSort edges globally
Data structureMin-heapUnion-Find
TimeO((V + E) log V)O(E log E)
Better forDense graphs (E ≈ V^2)Sparse graphs (E ≈ V)
Need all edges upfront?No (can stream)Yes (must sort)

When to Use ​

  • "Minimum cost to connect all points" (LC 1584)
  • "Connecting cities with minimum cost" (LC 1135)
  • Network design, cable laying, circuit wiring

14. Kosaraju's Algorithm (Strongly Connected Components) ​

A strongly connected component (SCC) is a maximal set of vertices where every vertex is reachable from every other vertex. Only applies to directed graphs.

Two-pass algorithm:

  1. Pass 1: DFS on original graph, push nodes to stack by finish time
  2. Pass 2: Build reversed graph, DFS in stack order — each DFS tree is one SCC
ts
function kosaraju(
  n: number,
  adj: number[][] // adj[i] = neighbors of node i
): number {
  const visited = new Array(n).fill(false);
  const stack: number[] = [];

  // Pass 1: DFS on original graph, record finish order
  function dfs1(node: number): void {
    visited[node] = true;
    for (const neighbor of adj[node]) {
      if (!visited[neighbor]) dfs1(neighbor);
    }
    stack.push(node); // push after all descendants processed
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs1(i);
  }

  // Build reversed graph
  const adjReversed: number[][] = Array.from({ length: n }, () => []);
  for (let u = 0; u < n; u++) {
    for (const v of adj[u]) {
      adjReversed[v].push(u);
    }
  }

  // Pass 2: DFS on reversed graph in stack order
  visited.fill(false);
  let sccCount = 0;

  function dfs2(node: number): void {
    visited[node] = true;
    for (const neighbor of adjReversed[node]) {
      if (!visited[neighbor]) dfs2(neighbor);
    }
  }

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (!visited[node]) {
      dfs2(node);
      sccCount++;
    }
  }

  return sccCount;
}

Key Points ​

  • Time: O(V + E) — two DFS passes
  • Why it works: finishing order from Pass 1 ensures that in Pass 2 (on reversed graph), DFS can't "escape" the current SCC
  • Use when you need to find groups of mutually reachable nodes (social network clusters, dependency groups)

15. Grid Pattern: Rotting Oranges (Multi-Source BFS) ​

Classic multi-source BFS problem — all rotten oranges spread simultaneously.

ts
function orangesRotting(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number][] = [];
  let fresh = 0;

  // Find all rotten oranges and count fresh ones
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      if (grid[r][c] === 1) fresh++;
    }
  }

  if (fresh === 0) return 0;

  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  let time = 0;
  let idx = 0;

  while (idx < queue.length && fresh > 0) {
    const size = queue.length - idx; // current level size
    for (let i = 0; i < size; i++) {
      const [r, c] = queue[idx++];
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] === 1
        ) {
          grid[nr][nc] = 2;
          queue.push([nr, nc]);
          fresh--;
        }
      }
    }
    time++;
  }

  return fresh === 0 ? time : -1;
}

Key Insight ​

  • Multi-source BFS = add ALL starting points to the queue at level 0, then expand level by level
  • Each level = 1 unit of time
  • This pattern also applies to: Walls and Gates (LC 286), Shortest Bridge (LC 934)

16. Shortest Path Algorithm Decision Guide ​

ScenarioAlgorithmWhy
Unweighted graphBFSO(V + E), simplest
Weighted, non-negativeDijkstraO((V+E) log V), greedy + heap
Weighted DAGTopo Sort + RelaxO(V + E), fastest for DAGs
Negative weightsBellman-FordO(V*E), handles negatives
All-pairs, small graphFloyd-WarshallO(V^3), simple DP
All-pairs, sparse graphRun Dijkstra from each nodeO(V*(V+E) log V)

17. Practice Problems ​

ProblemLeetCode #DifficultyKey TechniqueQuick Approach
Number of Islands200MediumBFS/DFS flood fillIterate grid, DFS/BFS to mark connected '1's as visited
Rotting Oranges994MediumMulti-source BFSEnqueue all rotten oranges, BFS level-by-level, count time
Course Schedule207MediumCycle detection (directed)Build directed graph from prerequisites, detect cycle via topo sort or 3-color DFS
Course Schedule II210MediumTopological sortKahn's algorithm; return empty if cycle detected (order.length < numCourses)
Clone Graph133MediumBFS/DFS + hashmapBFS/DFS traversal; use Map<Node, Node> to track old-to-new mapping
Network Delay Time743MediumDijkstraBuild weighted graph, run Dijkstra from source, return max distance (or -1 if unreachable)
Is Graph Bipartite?785MediumBFS coloringBFS from each uncolored node, alternate 0/1 colors, fail if adjacent nodes share color
Word Ladder127HardBFS shortest pathEach word is a node, edges connect words differing by 1 char; BFS from begin to end word
Pacific Atlantic Water Flow417MediumMulti-source DFSDFS inward from Pacific border and Atlantic border separately; intersect reachable sets
Surrounded Regions130MediumBoundary DFSDFS from border 'O's to mark safe cells; flip remaining 'O's to 'X'
Min Cost to Connect All Points1584MediumPrim's / Kruskal's MSTBuild complete graph with Manhattan distances, run MST algorithm
City With Smallest Number of Neighbors1334MediumFloyd-Warshall / DijkstraAll-pairs shortest path, count neighbors within threshold per city
Cheapest Flights Within K Stops787MediumBellman-Ford (modified)Run K+1 relaxation passes instead of V-1; tracks hop count
Number of Connected Components323MediumUnion-Find / DFSUnion all edges, return uf.count

Problem-by-Problem Notes ​

200 - Number of Islands: Classic flood fill. Iterate every cell; when you hit a '1', DFS/BFS to mark the entire island, increment count. O(m * n) time.

994 - Rotting Oranges: Multi-source BFS. Enqueue all rotten oranges at time 0, BFS level-by-level. Each level = 1 minute. Track fresh count; if fresh > 0 after BFS exhausts, return -1.

207 - Course Schedule: Model as directed graph (prerequisite -> course). If there's a cycle, you can't finish all courses. Use Kahn's: if topo sort doesn't include all nodes, return false.

210 - Course Schedule II: Same as 207 but return the actual ordering. Kahn's gives you the order directly; return empty array if cycle detected.

133 - Clone Graph: BFS or DFS. Maintain a Map<Node, ClonedNode>. For each node, clone it, then connect its neighbors (cloning them if not yet cloned).

743 - Network Delay Time: Textbook Dijkstra. Build weighted adjacency list, run Dijkstra from node k, return the maximum distance. If any node is unreachable (Infinity), return -1.

785 - Is Graph Bipartite?: BFS with 2-coloring. Try to color each component. If any edge connects same-colored nodes, return false.

127 - Word Ladder: BFS where each word is a node. For efficiency, generate all possible 1-char transformations and check against a word set rather than checking all pairs.

417 - Pacific Atlantic Water Flow: Reverse the problem. Instead of flowing from cell to ocean, DFS from ocean borders inward (to cells with height >= current). A cell that reaches both oceans is in the answer.

130 - Surrounded Regions: Boundary-first approach. DFS/BFS from every 'O' on the border to mark it safe. After that, any remaining 'O' is surrounded and should be flipped to 'X'.

1584 - Min Cost to Connect All Points: Build a complete graph with Manhattan distances. Run Prim's (start from any point, greedily add cheapest edge) or Kruskal's (sort all edges, Union-Find).

1334 - City With Smallest Number of Neighbors at a Threshold: Floyd-Warshall for all-pairs shortest paths. For each city count neighbors with dist[i][j] <= threshold. Return city with smallest count (highest index on tie).

787 - Cheapest Flights Within K Stops: Modified Bellman-Ford — run only K+1 relaxation passes. Use a copy of the dist array each round to avoid cascading relaxations within a single pass.

323 - Number of Connected Components: Union-Find or DFS. With Union-Find: union all edges, return uf.count. With DFS: count number of DFS trees when iterating all nodes.

Frontend interview preparation reference.