752. Open the Lock

Open the Lock (LeetCode 752) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Bidirectional BFS (BFS optimization for known source & target) subpattern.

• NeetCode 250 · #153 of 250 · Graphs

How to solve Open the Lock

Open the Lock is a Bidirectional BFS Optimization problem, part of Graph Traversal Patterns (DFS & BFS). Optimize BFS by searching from both source and target simultaneously. Reduce time complexity significantly.

Work towards the solution in these steps:

1. Treat each four-digit string as a state, and consider the states reachable with one wheel turn.
2. For each state, generate two possible changes for each of its four positions, taking wraparound into account.
3. Use a visited set so that a state is not processed repeatedly, and do not enqueue forbidden states.

The reference solution runs in O(deadends.length + 10^4) time and O(deadends.length + 10^4) space.

The Open the Lock solution and editorial walks through the full approach with reference code.

Problem statement

A lock state is a four-character string whose characters are digits from 0 through 9. The lock begins in state "0000". Turning one wheel by one step changes exactly one character: a digit can increase or decrease by 1, and the ends wrap around, so 9 can become 0 and 0 can become 9.

Every string in deadends is a forbidden state. The lock may not enter a forbidden state, and if the starting state is forbidden, the target cannot be reached. Return the minimum number of wheel turns needed to reach target from "0000"; return -1 if target is unreachable.

Example 1:

Input: deadends = ["1000","0009"], target = "1001" Output: 2 Explanation: Turn the first wheel from 0 to 1, then turn the last wheel from 0 to 1. Neither intermediate state is forbidden.

Example 2:

Input: deadends = [], target = "0000" Output: 0 Explanation: The lock already matches the target, so no turns are needed.

Example 3:

Input: deadends = ["1000","9000","0100","0900","0010","0090","0001","0009"], target = "2222" Output: -1 Explanation: All eight states reachable in one turn from the starting state are forbidden, so the lock cannot make any move.

Constraints:

- 0 <= deadends.length <= 500 - Every string in deadends has length 4. - Every character in each string in deadends is a digit from 0 through 9. - All strings in deadends are distinct. - target has length 4. - Every character in target is a digit from 0 through 9.

Topics and companies

Topics: Graph, Breadth-First Search, Queue, Shortest Path, String.

How to practise Open the Lock on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(deadends.length + 10^4) time and O(deadends.length + 10^4) space.

Open Open the Lock in the code editor, or read the Open the Lock editorial for a worked solution with its approach and complexity analysis.

Where Open the Lock sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Bidirectional BFS (BFS optimization for known source & target) subpattern
• The full DSA patterns sheet

Problems related to Open the Lock

Other problems that use the same Bidirectional BFS (BFS optimization for known source & target) and Graph Traversal Patterns (DFS & BFS) techniques:

• Bus Routes — Hard, same subpattern
• Word Ladder II — Hard, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• All Paths from Source Lead to Destination — Medium, same pattern
• Build a Matrix With Conditions — Hard, same pattern

Open the Lock FAQ