Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgrid-graph-bfs

Open the Lock

Problem (restated)

A 4-wheel lock shows digits 0000-9999. Each move turns one wheel ±1. Avoid deadends. Return minimum turns from 0000 to target, or -1.

Intuition

Each state has up to 8 neighbors. BFS from 0000; deadends start as visited.

Approaches

BFS on dial states

Tested only

Time O(10^4)Space O(10^4)

Idea. Queue of (state, dist). Generate ±1 per wheel with wrap; skip seen/dead.

Walkthrough. target 0202 often needs 6 turns when no blocking deadends on the path.

Trade-offs. BFS is optimal; bidirectional BFS helps on larger state spaces.

Solution

export function openLock(deadends: string[], target: string): number {
  const dead = new Set(deadends);
  if (dead.has("0000")) return -1;
  if (target === "0000") return 0;
  const q: [string, number][] = [["0000", 0]];
  const seen = new Set<string>(["0000"]);
  const neighbors = (s: string): string[] => {
    const out: string[] = [];
    const a = s.split("");
    for (let i = 0; i < 4; i++) {
      const d = Number(a[i]);
      for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
        a[i] = String(nd);
        out.push(a.join(""));
        a[i] = String(d);
      }
    }
    return out;
  };
  while (q.length) {
    const [cur, dist] = q.shift()!;
    for (const nxt of neighbors(cur)) {
      if (seen.has(nxt) || dead.has(nxt)) continue;
      if (nxt === target) return dist + 1;
      seen.add(nxt);
      q.push([nxt, dist + 1]);
    }
  }
  return -1;
}

export function openLock(deadends: string[], target: string): number {
  const dead = new Set(deadends);
  if (dead.has("0000")) return -1;
  if (target === "0000") return 0;
  const q: [string, number][] = [["0000", 0]];
  const seen = new Set<string>(["0000"]);
  const neighbors = (s: string): string[] => {
    const out: string[] = [];
    const a = s.split("");
    for (let i = 0; i < 4; i++) {
      const d = Number(a[i]);
      for (const nd of [(d + 1) % 10, (d + 9) % 10]) {
        a[i] = String(nd);
        out.push(a.join(""));
        a[i] = String(d);
      }
    }
    return out;
  };
  while (q.length) {
    const [cur, dist] = q.shift()!;
    for (const nxt of neighbors(cur)) {
      if (seen.has(nxt) || dead.has(nxt)) continue;
      if (nxt === target) return dist + 1;
      seen.add(nxt);
      q.push([nxt, dist + 1]);
    }
  }
  return -1;
}

Template connection

Graph BFS on implicit state graph.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?