FastPrepOpen the Lock
Problem · Breadth First Search

Open the Lock

Learn this problem
● MediumAmazon logoAmazonNEW GRADPHONE SCREEN
See Amazon hiring insights

Problem statement

A lock has four circular wheels. Each wheel shows one digit from 0 through 9. In one move, you may rotate exactly one wheel one step forward or backward; digits wrap between 0 and 9.

The lock starts at "0000". The array deadends lists combinations that immediately block the lock and cannot be entered. Return the minimum number of moves needed to reach target, or -1 if it is impossible.

Function

openLock(deadends: String[], target: String) → int

Examples

Example 1

deadends = ["0201","0101","0102","1212","2002"]target = "0202"return = 6

One shortest route is 0000, 1000, 1100, 1200, 1201, 1202, 0202.

Example 2

deadends = ["8888"]target = "0009"return = 1

Rotate the last wheel backward once to move directly from 0000 to 0009.

Example 3

deadends = ["0000"]target = "8888"return = -1

The starting combination is blocked, so no move can be made.

Constraints

  • 0 <= deadends.length <= 500.
  • Every combination in deadends and target has exactly four decimal digits.
  • All strings in deadends are unique.

More Amazon problems

drafts saved locally
public int openLock(String[] deadends, String target) {
  // write your code here
}
deadends["0201","0101","0102","1212","2002"]
target"0202"
expected6
checking account