#752

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Open the Lock

Solve the Open the Lock problem using array scanning plus hash lookup to efficiently find the shortest unlock sequence.

array hash table string breadth first search

Problem Statement

You are presented with a 4-wheel lock, each wheel labeled 0 through 9. The wheels can rotate forward or backward by one, and wrap around, meaning turning '9' forward yields '0' and '0' backward yields '9'. Each turn changes only one wheel at a time, representing a single move.

The lock begins at the state "0000". You are given a list of forbidden codes called deadends; if the lock reaches any of these, it freezes and cannot be turned further. Given a target code, determine the minimum number of moves required to reach it from "0000" without hitting deadends, or return -1 if it is impossible.

Examples

Example 1

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Output: 6

A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid, because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2

Input: deadends = ["8888"], target = "0009"

Output: 1

We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

Output: -1

We cannot reach the target without getting stuck.

Constraints

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target will not be in the list deadends.
target and deadends[i] consist of digits only.

Solution Approach

Model the lock as a graph

Represent each 4-digit string as a node. Each valid wheel turn generates edges to neighboring nodes. Deadends are removed from consideration using a hash set to prevent visiting them.

Breadth-First Search (BFS) traversal

Use BFS starting from "0000", enqueuing each new state after a valid turn. Track visited states with a hash set to avoid revisiting. Each BFS level corresponds to one move in the lock.

Generate neighbors efficiently

For each node, iterate over the 4 wheels and compute both increment and decrement moves, wrapping around at '0' and '9'. Skip states in deadends or already visited. Array scanning of positions plus hash lookup for deadends ensures optimal performance.

Complexity Analysis

Metric	Value
Time	O(4(d + 10^4))
Space	O(4(d + 10^4))

Time complexity is O(4(d + 10^4)) because each of the 4 wheels can change per node, with at most 10^4 possible states, and d deadends. Space complexity is O(4(d + 10^4)) for the BFS queue and visited/deadend hash sets.

What Interviewers Usually Probe

Look for a BFS pattern and early pruning using deadend hash set.
Expect recognition that each state has up to 8 neighbors due to wheel increments and decrements.
Consider wraparound behavior and edge cases like starting or ending on a deadend.

Common Pitfalls or Variants

Common pitfalls

Failing to account for wraparound when incrementing '9' or decrementing '0'.
Revisiting states without checking visited hash set, causing infinite loops.
Miscounting moves by including deadend transitions or skipping BFS levels.

Follow-up variants

Solve using bidirectional BFS from both start and target for faster convergence.
Consider a lock with N wheels instead of 4, adjusting BFS accordingly.
Introduce weighted moves, where some wheel turns cost more, and find minimum total cost.

FAQ

What is the best approach to solve Open the Lock using array scanning plus hash lookup?

Use BFS to explore all valid lock states from "0000" to target, while using hash sets to skip deadends and visited nodes.

Can Open the Lock be solved without BFS?

DFS can be used, but BFS ensures the minimal number of moves; DFS may explore longer paths first, causing inefficiency.

How do I handle wraparound for each wheel in Open the Lock?

When incrementing '9', wrap to '0'; when decrementing '0', wrap to '9'. Consider both directions for each wheel.

What should I do if the starting state is a deadend?

Immediately return -1, since no moves can be made from a deadend state.

How does array scanning plus hash lookup improve performance for Open the Lock?

Array scanning generates neighbor states efficiently while hash lookup quickly checks for deadends and visited nodes, avoiding redundant processing.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def next(s):
            res = []
            s = list(s)
            for i in range(4):
                c = s[i]
                s[i] = '9' if c == '0' else str(int(c) - 1)
                res.append(''.join(s))
                s[i] = '0' if c == '9' else str(int(c) + 1)
                res.append(''.join(s))
                s[i] = c
            return res

        if target == '0000':
            return 0
        s = set(deadends)
        if '0000' in s:
            return -1
        q = deque([('0000')])
        s.add('0000')
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                p = q.popleft()
                for t in next(p):
                    if t == target:
                        return ans
                    if t not in s:
                        q.append(t)
                        s.add(t)
        return -1

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def next(s):
            res = []
            s = list(s)
            for i in range(4):
                c = s[i]
                s[i] = '9' if c == '0' else str(int(c) - 1)
                res.append(''.join(s))
                s[i] = '0' if c == '9' else str(int(c) + 1)
                res.append(''.join(s))
                s[i] = c
            return res

        if target == '0000':
            return 0
        s = set(deadends)
        if '0000' in s:
            return -1
        q = deque([('0000')])
        s.add('0000')
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                p = q.popleft()
                for t in next(p):
                    if t == target:
                        return ans
                    if t not in s:
                        q.append(t)
                        s.add(t)
        return -1

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def next(s):
            res = []
            s = list(s)
            for i in range(4):
                c = s[i]
                s[i] = '9' if c == '0' else str(int(c) - 1)
                res.append(''.join(s))
                s[i] = '0' if c == '9' else str(int(c) + 1)
                res.append(''.join(s))
                s[i] = c
            return res

        if target == '0000':
            return 0
        s = set(deadends)
        if '0000' in s:
            return -1
        q = deque([('0000')])
        s.add('0000')
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                p = q.popleft()
                for t in next(p):
                    if t == target:
                        return ans
                    if t not in s:
                        q.append(t)
                        s.add(t)
        return -1

Continue Practicing

#721 accounts merge #839 similar string groups #1202 smallest string with swaps