752. Open the Lock

Problem Statement

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Examples

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
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 deadend "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: 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
Explanation: We cannot reach the target without getting stuck in a deadend.

Constraints

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target and deadends[i] consist of digits only.

Solution Approach

This is a shortest path problem that can be solved using BFS. We need to find the minimum number of moves to reach the target from “0000” while avoiding deadends.

Key Insights:

State space: Each lock state is a 4-digit string (0000-9999)
Transitions: For each position, we can turn up (+1) or down (-1)
Shortest path: BFS guarantees minimum number of moves
Deadends: Act as obstacles that block certain states
Wrapping: 9 → 0 and 0 → 9 (circular nature)

Algorithm:

BFS from “0000”: Use queue to explore all possible states
Level-by-level: Each level represents one move
State transitions: Generate all 8 possible next states (4 positions × 2 directions)
Avoid deadends: Skip states that are in deadends set
Visited tracking: Prevent revisiting states

Solution

Solution: BFS Shortest Path

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deads (deadends.begin(), deadends.end());
        unordered_set<string> visited;
        if(deads.contains("0000")) return -1;
        queue<string> q;
        q.push("0000");
        visited.insert("0000");
        int steps = 0;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                string curr = q.front();
                q.pop();
                if(curr == target) return steps;
                for(int i = 0; i < 4; i++) {
                    for(int dir = -1; dir <=1; dir+=2) {
                        string next = curr;
                        next[i] = (curr[i] - '0' + dir + 10) % 10 + '0';
                        if(!deads.contains(next) && !visited.contains(next)) {
                            q.push(next);
                            visited.insert(next);
                        }
                    }
                }
            }
            steps++;
        }   
        return -1;
    }
};

Algorithm Explanation:

Initialize: Create deadends set and visited set
Check start: If “0000” is a deadend, return -1 immediately
BFS setup: Start with “0000” in queue
Level processing: Process all states at current level
State transitions: For each position, try both directions (+1 and -1)
Wrapping: Use modulo arithmetic for circular nature
Validation: Check if next state is valid (not deadend, not visited)
Target check: Return steps when target is reached

Example Walkthrough:

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

Level 0: ["0000"] → steps = 0
Level 1: ["1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"] → steps = 1
Level 2: ["2000", "1100", "1900", "0200", "0800", "0110", "0190", "0020", "0080", "0011", "0019", "0002", "0008"] → steps = 2
Level 3: Continue exploring...
...
Level 6: ["0202"] → Found target! Return 6

Path: "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"

Key Implementation Details:

// Circular wrapping for digits
next[i] = (curr[i] - '0' + dir + 10) % 10 + '0';

// For dir = -1: (0 - 1 + 10) % 10 = 9 (0 → 9)
// For dir = +1: (9 + 1 + 10) % 10 = 0 (9 → 0)

Complexity Analysis

Time Complexity: O(10^4) = O(1)

State space: At most 10,000 states (0000-9999)
BFS traversal: Each state visited at most once
Transitions: 8 transitions per state
Total: O(10,000 × 8) = O(80,000) = O(1) constant time

Space Complexity: O(10^4) = O(1)

Queue: O(10,000) - maximum states in queue
Visited set: O(10,000) - stores visited states
Deadends set: O(500) - stores deadend states
Total: O(10,000) = O(1) constant space

Key Points

BFS for shortest path: Guarantees minimum number of moves
State space: 4-digit strings represent lock states
Circular wrapping: Handle 0 ↔ 9 transitions correctly
Deadend avoidance: Skip invalid states
Visited tracking: Prevent infinite loops
Level counting: Each BFS level represents one move

Alternative Approaches

Bidirectional BFS

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deads(deadends.begin(), deadends.end());
        if(deads.contains("0000") || deads.contains(target)) return -1;
        
        unordered_set<string> begin, end, visited;
        begin.insert("0000");
        end.insert(target);
        int steps = 0;
        
        while(!begin.empty() && !end.empty()) {
            if(begin.size() > end.size()) swap(begin, end);
            
            unordered_set<string> next;
            for(string curr : begin) {
                if(end.contains(curr)) return steps;
                if(deads.contains(curr) || visited.contains(curr)) continue;
                
                visited.insert(curr);
                for(int i = 0; i < 4; i++) {
                    for(int dir = -1; dir <= 1; dir += 2) {
                        string next_state = curr;
                        next_state[i] = (curr[i] - '0' + dir + 10) % 10 + '0';
                        if(!deads.contains(next_state) && !visited.contains(next_state)) {
                            next.insert(next_state);
                        }
                    }
                }
            }
            begin = next;
            steps++;
        }
        return -1;
    }
};

127. Word Ladder - Similar BFS shortest path
433. Minimum Genetic Mutation - String transformation
126. Word Ladder II - Find all shortest paths