Quick Overview

This question evaluates the ability to model the lock as a state-space and apply graph traversal and shortest-path techniques (breadth-first search) to determine minimal move sequences under constraints.

Solve Open the Lock BFS

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question LeetCode 752. Open the Lock – Given an initial lock state "0000", a target combination, and a list of deadend combinations that cannot be used, each move rotates one digit ±1 (with wrap-around), find the minimum number of moves to reach the target. https://leetcode.com/problems/open-the-lock/description/

Quick Answer: This question evaluates the ability to model the lock as a state-space and apply graph traversal and shortest-path techniques (breadth-first search) to determine minimal move sequences under constraints.

You have a lock with 4 circular wheels. Each wheel has 10 slots: '0'..'9'. The wheels rotate freely and wrap around: '9' -> '0' and '0' -> '9'. Each move turns exactly one wheel one slot (±1). The lock starts at "0000". You are given a list of `deadends` — combinations that, if any wheel is ever set to such a value, will jam the lock so it can never be opened from there. You are also given a `target` combination. Return the minimum total number of moves required to turn the lock from "0000" to `target`, or -1 if it is impossible. Function signature: `solution(deadends, target)` where `deadends` is a list of 4-character strings and `target` is a 4-character string.

Constraints

  • 1 <= deadends.length <= 500
  • Each deadends[i] and target has exactly 4 digits ('0'..'9').
  • Each move turns one wheel by ±1 with wrap-around ('9'->'0', '0'->'9').
  • If "0000" is itself a deadend, the lock can never move and the answer is -1.
  • target may equal "0000" (answer 0).

Examples

Input: (["0201", "0101", "0102", "1212", "2002"], "0202")

Expected Output: 6

Explanation: A valid 6-move sequence is 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202. Note 0102 is a deadend, so the more direct route 0000 -> 0001 -> 0002 -> 0102 ... is blocked, forcing the longer 6-move path.

Input: (["8888"], "0009")

Expected Output: 1

Explanation: Turn the last wheel down once: 0 -> 9 wraps around, so 0000 -> 0009 in a single move. The deadend 8888 is never on the path.

Hints

  1. Model each 4-digit combination as a node in an unweighted graph; an edge connects two combinations that differ by a single ±1 wheel turn. Minimum moves on an unweighted graph = shortest path, which is exactly what BFS finds.
  2. From any state, generate its 8 neighbors by turning each of the 4 wheels up and down by one, using modulo 10 for wrap-around (so digit 9 goes to 0 and 0 goes to 9).
  3. Treat deadends as blocked nodes you may never enter (skip them when expanding), and use a visited set so you never revisit a combination. Handle the edge cases first: if "0000" is a deadend return -1, and if target == "0000" return 0.

Loading coding console...