How do you solve Open the Lock on LeetCode?

Open the Lock (LeetCode #752) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Each wheel can be treated as an independent dimension, leading to a combinatorial explosion of states.

What is the brute force solution for Open the Lock?

The brute force approach for Open the Lock is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible combinations of the lock's states and checking each one to see if it matches the target. This method is simple but inefficient, as it explores many unnecessary paths. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Open the Lock?

Open the Lock uses the following concepts: Array, Hash Table, String, Breadth-First Search. The recommended patterns to study are: Breadth-First Search, Graph Traversal.

What are the interview tips for Open the Lock?

Always clarify the problem constraints and edge cases, like deadends. Think about how to represent the problem as a graph or state space. Explain your thought process clearly while coding, especially your choice of data structures.

What are common mistakes when solving Open the Lock?

Not checking if the initial state '0000' is a deadend. Failing to mark states as visited, leading to infinite loops.

#752

Open the Lock

Medium

ArrayHash TableStringBreadth-First SearchBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a breadth-first search (BFS) strategy to explore the shortest path to the target. By treating each lock state as a node in a graph, we can efficiently find the minimum number of moves required.

⚙️

Algorithm

5 steps

1Step 1: Initialize a queue with the starting state '0000' and a set for visited states.
2Step 2: For each state, generate all possible next states by turning each wheel up or down.
3Step 3: Check if the next state is the target or a deadend.
4Step 4: If valid, add it to the queue and mark it as visited.
5Step 5: Continue until the target is found or all possibilities are exhausted.

solution.py25 lines

1# Full working Python code
2from collections import deque
3
4def openLock(deadends, target):
5    dead_set = set(deadends)
6    if '0000' in dead_set:
7        return -1
8    queue = deque(['0000'])
9    visited = set(['0000'])
10    turns = 0
11    while queue:
12        for _ in range(len(queue)):
13            current = queue.popleft()
14            if current == target:
15                return turns
16            for i in range(4):
17                for move in [-1, 1]:
18                    next_state = list(current)
19                    next_state[i] = str((int(current[i]) + move) % 10)
20                    next_state = ''.join(next_state)
21                    if next_state not in visited and next_state not in dead_set:
22                        visited.add(next_state)
23                        queue.append(next_state)
24        turns += 1
25    return -1

ℹ

Complexity note: The time complexity is linear with respect to the number of states explored, which is limited to 10,000. The space complexity is also linear because we store visited states and the queue.

1Each wheel can be treated as an independent dimension, leading to a combinatorial explosion of states.
2Using BFS guarantees that the first time we reach the target, it is through the shortest path.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.