Open the Lock

MediumGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A lock has four circular wheels, each showing a digit 0-9. The lock starts at "0000". One **move** turns a single wheel one step up or down; wheels wrap around, so 9 turns up to 0 and 0 turns down to 9. You are given deadends, a list of four-digit codes. If the lock ever shows a dead-end code (including the starting code), it jams and cannot be turned further. Return the minimum number of moves to reach target without ever showing a dead end, or -1 if it is impossible. If target is "0000" and that code is not a dead end, the answer is 0.

Examples

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
One shortest route is 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202, avoiding every dead end.
Input: deadends = ["8888"], target = "0009"
Output: 1
Turn the last wheel down once: 0000 -> 0009.

Constraints

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4 and target.length == 4
  • deadends[i] and target consist of digits only
  • target is not guaranteed to be absent from deadends

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems