Overview

Session opened with a heap spaced repetition review (Kth Largest in a Stream), then covered BFS and DFS end-to-end: mental models, when to use each, two implementations, and three problems. The connecting insight across all problems was that BFS level depth equals distance from source — the same invariant that powers level-order traversal also powers shortest-path search.

Concept

BFS uses a queue (FIFO) and visits nodes level by level — all nodes at distance k before any at distance k+1.

DFS uses a stack or recursion and dives deep before backtracking.

Complexity: O(V + E) on a graph; O(n·m) on a grid.

The level invariant (why BFS = shortest path)

At the top of every while iteration, the queue contains exactly the nodes at one level and nothing else. Proof by induction:

• Base: seed queue with root only. One level. ✓
• Step: processing level k enqueues only level k+1 children; we stop before touching them. ✓

Consequence: the first time BFS reaches a destination, it arrived via the shortest route — every shorter route was fully explored in prior levels.

Mark visited on enqueue, not dequeue

The standard BFS pattern adds a node to the visited set (or mutates it) when it is enqueued, not when it is dequeued. This prevents the same node from entering the queue multiple times, avoiding redundant work and potential bugs.

Implementation

BFS on a graph

export type Graph = Map<string, string[]>

export function bfs(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>([start])
  const queue: string[] = [start]
  const result: string[] = []

  while (queue.length > 0) {
    const current = queue.shift()!
    result.push(current)
    for (const neighbor of graph.get(current) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor) // mark on enqueue
        queue.push(neighbor)
      }
    }
  }

  return result
}

James’s first attempt used a for loop whose update expression was empty (infinite loop) and threw on revisited nodes rather than skipping them. Both fixed above.

Problems

Kth Largest Element in a Stream (spaced repetition)

Problem: Design a class that tracks a stream of integers and returns the Kth largest at any time.

Approach: Maintain a min-heap of size k. The root is always the Kth largest.

• add(n): if n <= heap.peek and heap is full, ignore. Otherwise push and sift up; if size > k, extract min (sift down). O(log k).
• Initialization: add each of n initial elements maintaining heap size k. O(n log k) — not O(k log k); n is the length of initial, which may be much larger than k.

Sift directions: push → sift up; extract min → replace root with last, sift down. James initially had these reversed.

Level-Order Traversal

Problem: Given a binary tree, return nodes grouped by level: [[3],[9,20],[15,7]].

Approach: BFS with the queue-length snapshot pattern. At the top of each while iteration, everything in the queue belongs to the current level.

export type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null }

export function levelOrder(root: TreeNode | null): number[][] {
  if (root == null) return [] // not [[]] — no root means no levels

  const queue: TreeNode[] = [root]
  const result: number[][] = []

  while (queue.length > 0) {
    const levelSize = queue.length // snapshot: all nodes at this level
    const level: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

James’s first attempt tagged each entry { level, node } — valid, but the snapshot pattern avoids the wrapper type and is the standard interview idiom. He also returned [[]] for null root (should be []) and included a now-redundant if (root != null) guard after the early return.

No visited set needed on a tree — each node has exactly one parent, so it can never enter the queue twice.

Number of Islands

Problem: Count islands in a '1'/'0' grid. An island is a group of adjacent land cells.

Approach: Iterate every cell. On an unvisited '1', increment count and DFS to mark the entire island visited by mutating '1' → '0'.

/**
 * @note mutates `grid` as it works
 */
export function numIslands(grid: string[][]): number {
  let result = 0

  for (let i = 0; i < grid.length; i++) {
    const row = grid[i]
    for (let j = 0; j < row.length; j++) {
      if (row[j] === '0') continue
      result++
      markIslandComplete(grid, i, j)
    }
  }

  return result
}

function markIslandComplete(grid: string[][], i: number, j: number): void {
  const value = (grid[i] ?? [])[j]
  if (value == null || value === '0') return
  grid[i][j] = '0' // mark before recursing — critical
  markIslandComplete(grid, i, j - 1)
  markIslandComplete(grid, i, j + 1)
  markIslandComplete(grid, i - 1, j)
  markIslandComplete(grid, i + 1, j)
}

James’s first attempt omitted grid[i][j] = '0' before the recursive calls — the cell was never marked visited, causing infinite recursion. He caught the bug himself when prompted.

(grid[i] ?? [])[j] elegantly handles both out-of-bounds rows and negative column indices in one expression (JavaScript returns undefined for negative array indices).

Shortest Path in a Grid

Problem: Given a binary grid (0 = open, 1 = blocked), return the shortest path length from (0,0) to (m-1, n-1), or -1 if none exists.

Why BFS, not DFS: DFS commits to one direction and may find a long path before a short one; you’d have to exhaust all paths to be sure. BFS explores by distance, so the first time it reaches the destination is guaranteed to be the shortest route.

Distance = level. Shortest path length is identical to the BFS level at which the destination is first dequeued.

export function shortestPath(grid: number[][]): number {
  const m = grid.length
  const n = grid[0]?.length ?? 0
  if (grid[0][0] === 1) return -1

  grid[0][0] = 1 // mark start visited on enqueue
  const queue: Array<[number, number]> = [[0, 0]]
  let distance = 0

  while (queue.length > 0) {
    const levelSize = queue.length
    distance++

    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue.shift()!
      if (r === m - 1 && c === n - 1) return distance

      // down and right first: constant-factor heuristic toward bottom-right
      for (const [dr, dc] of [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
      ]) {
        const nr = r + dr,
          nc = c + dc
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 0) {
          grid[nr][nc] = 1 // mark visited on enqueue
          queue.push([nr, nc])
        }
      }
    }
  }

  return -1 // no path found
}

James’s bugs: off-by-one on destination (j === m → j === m-1; k === n → k === n-1), and losing the -1 return at the end during refactoring. He intentionally ordered directions down/right first as a constant-factor heuristic — doesn’t change O(n·m) but reduces average checks in typical bottom-right-destination grids.

The direction array [[1,0],[0,1],[-1,0],[0,-1]] is a standard idiom for 4-directional grid traversal. Worth memorizing.

export function bfs(graph: Map<string, string[]>, start: string): string[] {
  const queue: string[] = [start]
  const visited = new Set<string>([])
  const result: string[] = []
  for (let current = queue.shift(); current != null; ) {
    if (visited.has(current)) {
      throw new Error(`bfs detected cycle at ${current}`)
    }
    visited.add(current)
    result.push(current)
    const neighbors = graph.get(current) ?? []
    queue.push(...neighbors)
  }
  return result
}

function markIslandComplete(grid, i, j) {
  const value = (grid[i] ?? [])[j]
  if (value == null || value === '0') return
  markIslandComplete(grid, i, j - 1)
  // ... (missing grid[i][j] = '0')
}

export function shortestPath(grid: number[][]): number {
  // ... (off-by-one: j === m should be j === m-1, return distance at end should be -1)
}