BFS Shortest Path in an Unweighted Graph (Authoritative) — Open the Lock

Use BFS to find the minimum number of moves in an implicit unweighted graph (LeetCode 752: Open the Lock).

Language Selection

Choose your preferred programming language

Showing: Python

BFS Shortest Path in an Unweighted Graph (Authoritative) — Open the Lock

Problem Statement

You have a lock with 4 wheels. Each wheel shows a digit '0'–'9' and wraps around:

  • Turning up: 9 → 0
  • Turning down: 0 → 9

The lock starts at "0000".

You are given:

  • deadends: a list of forbidden 4-digit states. If the lock ever shows a deadend state, you cannot use that state (you can’t move from it).
  • target: a 4-digit string.

In one move, you can turn one wheel by one step (up or down).

Return the minimum number of moves needed to reach target from "0000" without entering any deadend state. If it’s impossible, return -1.

Examples

Example 1

  • deadends = ["0201","0101","0102","1212","2002"]
  • target = "0202"
  • Output: 6

Explanation: A shortest sequence exists with 6 moves (there may be multiple shortest sequences).

Example 2 (blocked start)

  • deadends = ["0000"]
  • target = "8888"
  • Output: -1

Example 3 (already at target)

  • deadends = []
  • target = "0000"
  • Output: 0

Intuition — what insight unlocks the solution?

This is the textbook pattern: BFS shortest path in an unweighted graph.

  • Each lock state (like "0381") is a node.
  • A single wheel turn is an edge with cost 1.
  • We need the minimum number of moves, i.e., the shortest path length.

Because all edges have equal weight (1), BFS explores states in increasing distance order, guaranteeing that the first time we reach target, we’ve found the optimal answer.

This is an implicit graph: we never build all nodes/edges upfront; we generate up to 8 neighbors per state on the fly.

Approach

Approach 1: Brute force / naive search (DFS) — not correct for shortest path

A natural first thought is to try DFS/backtracking from "0000" until you hit target.

Why it fails in interviews:

  • DFS can go deep and find a long path before a short one.
  • Even with visited, DFS does not guarantee the first time you reach target is the shortest.

So DFS is not the right tool for shortest path in an unweighted graph.

Approach 2 (Optimal): BFS from "0000"

Step-by-step

  1. Put all deadends into a hash set for O(1) lookups.
  2. If "0000" is a deadend, return -1 immediately.
  3. If target == "0000", return 0.
  4. Run BFS:
    • Queue starts with ("0000", 0).
    • Maintain a visited set; mark "0000" visited immediately.
  5. While the queue isn’t empty:
    • Pop the front state and its distance.
    • If it’s target, return the distance.
    • Generate its 8 neighbors by turning each wheel +1 and -1 (with wrap-around).
    • For each neighbor: if it’s not a deadend and not visited, mark visited and enqueue with distance + 1.
  6. If BFS finishes without finding target, return -1.

Why this works

  • BFS processes nodes in layers: distance 0, then 1, then 2, …
  • Since every move costs 1, the first time we dequeue target is the shortest number of moves.

Solution

Python:

from collections import deque
from typing import List


class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        start = "0000"

        if start in dead:
            return -1
        if target == start:
            return 0

        def neighbors(state: str):
            # Generate up to 8 neighbors by turning each of 4 wheels +/- 1.
            s = list(state)
            for i in range(4):
                digit = ord(s[i]) - ord('0')

                for delta in (-1, 1):
                    nd = (digit + delta) % 10
                    old = s[i]
                    s[i] = chr(ord('0') + nd)
                    yield "".join(s)
                    s[i] = old

        q = deque([(start, 0)])
        visited = {start}

        while q:
            state, dist = q.popleft()
            for nxt in neighbors(state):
                if nxt in dead or nxt in visited:
                    continue
                if nxt == target:
                    return dist + 1
                visited.add(nxt)  # mark visited at enqueue-time to avoid duplicates
                q.append((nxt, dist + 1))

        return -1

Java:

import java.util.*;

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>();
        Collections.addAll(dead, deadends);

        String start = "0000";
        if (dead.contains(start)) return -1;
        if (start.equals(target)) return 0;

        Queue<String> queue = new ArrayDeque<>();
        Queue<Integer> distQ = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();

        queue.add(start);
        distQ.add(0);
        visited.add(start);

        while (!queue.isEmpty()) {
            String cur = queue.poll();
            int dist = distQ.poll();

            for (String nxt : neighbors(cur)) {
                if (dead.contains(nxt) || visited.contains(nxt)) continue;
                if (nxt.equals(target)) return dist + 1;

                visited.add(nxt); // mark at enqueue-time
                queue.add(nxt);
                distQ.add(dist + 1);
            }
        }

        return -1;
    }

    private List<String> neighbors(String state) {
        List<String> res = new ArrayList<>(8);
        char[] s = state.toCharArray();

        for (int i = 0; i < 4; i++) {
            char original = s[i];
            int digit = original - '0';

            // turn down
            int down = (digit + 9) % 10;
            s[i] = (char) ('0' + down);
            res.add(new String(s));

            // turn up
            int up = (digit + 1) % 10;
            s[i] = (char) ('0' + up);
            res.add(new String(s));

            // restore
            s[i] = original;
        }

        return res;
    }
}

Go:

package main

import (
	"container/list"
)

func openLock(deadends []string, target string) int {
	dead := make(map[string]bool, len(deadends))
	for _, d := range deadends {
		dead[d] = true
	}

	start := "0000"
	if dead[start] {
		return -1
	}
	if target == start {
		return 0
	}

	visited := map[string]bool{start: true}

	type node struct {
		state string
		dist  int
	}

	q := list.New()
	q.PushBack(node{state: start, dist: 0})

	for q.Len() > 0 {
		front := q.Front()
		q.Remove(front)
		cur := front.Value.(node)

		for _, nxt := range neighbors(cur.state) {
			if dead[nxt] || visited[nxt] {
				continue
			}
			if nxt == target {
				return cur.dist + 1
			}
			visited[nxt] = true // enqueue-time
			q.PushBack(node{state: nxt, dist: cur.dist + 1})
		}
	}

	return -1
}

func neighbors(state string) []string {
	res := make([]string, 0, 8)
	s := []byte(state)

	for i := 0; i < 4; i++ {
		orig := s[i]
		digit := int(orig - '0')

		// down
		down := (digit + 9) % 10
		s[i] = byte('0' + down)
		res = append(res, string(s))

		// up
		up := (digit + 1) % 10
		s[i] = byte('0' + up)
		res = append(res, string(s))

		s[i] = orig
	}
	return res
}

JavaScript:

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
function openLock(deadends, target) {
  const dead = new Set(deadends);
  const start = "0000";

  if (dead.has(start)) return -1;
  if (target === start) return 0;

  const visited = new Set([start]);
  const queue = [[start, 0]];
  let head = 0; // avoid O(n) shift()

  const neighbors = (state) => {
    const res = [];
    const arr = state.split("");

    for (let i = 0; i < 4; i++) {
      const digit = arr[i].charCodeAt(0) - 48;

      for (const delta of [-1, 1]) {
        const nd = (digit + delta + 10) % 10;
        const old = arr[i];
        arr[i] = String.fromCharCode(48 + nd);
        res.push(arr.join(""));
        arr[i] = old;
      }
    }
    return res;
  };

  while (head < queue.length) {
    const [state, dist] = queue[head++];

    for (const nxt of neighbors(state)) {
      if (dead.has(nxt) || visited.has(nxt)) continue;
      if (nxt === target) return dist + 1;

      visited.add(nxt); // enqueue-time
      queue.push([nxt, dist + 1]);
    }
  }

  return -1;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int OpenLock(string[] deadends, string target) {
        var dead = new HashSet<string>(deadends);
        string start = "0000";

        if (dead.Contains(start)) return -1;
        if (target == start) return 0;

        var visited = new HashSet<string>() { start };
        var q = new Queue<(string state, int dist)>();
        q.Enqueue((start, 0));

        while (q.Count > 0) {
            var (state, dist) = q.Dequeue();

            foreach (var nxt in Neighbors(state)) {
                if (dead.Contains(nxt) || visited.Contains(nxt)) continue;
                if (nxt == target) return dist + 1;

                visited.Add(nxt); // mark at enqueue-time
                q.Enqueue((nxt, dist + 1));
            }
        }

        return -1;
    }

    private IEnumerable<string> Neighbors(string state) {
        char[] s = state.ToCharArray();

        for (int i = 0; i < 4; i++) {
            char original = s[i];
            int digit = original - '0';

            // down
            int down = (digit + 9) % 10;
            s[i] = (char)('0' + down);
            yield return new string(s);

            // up
            int up = (digit + 1) % 10;
            s[i] = (char)('0' + up);
            yield return new string(s);

            s[i] = original;
        }
    }
}

Complexity Analysis

Let V be the number of reachable states (at most 10,000), and each state has up to 8 neighbors, so E ≤ 8V.

  • Time: O(V + E), which is effectively O(V) here because E = O(V) (constant-degree graph). We enqueue/dequeue each state at most once, and we try a constant number of neighbor moves per state.
  • Space: O(V) for the visited set and the BFS queue in the worst case.

Common Mistakes

  1. Using DFS and claiming it finds the shortest path (it doesn’t in unweighted graphs).
  2. Not handling "0000" as a deadend (must return -1 immediately).
  3. Marking visited too late (marking when dequeued instead of when enqueued can cause many duplicates in the queue).
  4. Wrap-around bugs (0 → 9 and 9 → 0).
  5. Off-by-one in step counting (fix by storing dist per queue entry, or doing level-order BFS carefully).
  6. Using a list for deadends (membership becomes O(n); use a hash set).

Related / Follow-up Problems

  • 127. Word Ladder (BFS over word states)
  • 433. Minimum Genetic Mutation
  • 909. Snakes and Ladders
  • 1091. Shortest Path in Binary Matrix (grid BFS)
  • Follow-up: Bidirectional BFS (often faster in practice; same correctness)
  • If edges have weights: use Dijkstra (or 0-1 BFS if weights are only 0/1)