Open the Lock

LeetCode 753 | Difficulty: Medium

Medium

Problem Description

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.

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 dead end "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.

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.

Topics: Array, Hash Table, String, Breadth-First Search

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 232 ms)

Metric	Value
Runtime	232 ms
Memory	29.5 MB
Date	2019-12-27

Solution

public class Solution {
    public int OpenLock(string[] deadends, string target) {
        HashSet<string> begin = new HashSet<string>();
    HashSet<string> end = new HashSet<string>();
    HashSet<string> deads = new HashSet<string>(deadends);
    begin.Add("0000");
    end.Add(target);
    int level = 0;
    
    while(begin.Count != 0 && end.Count != 0)
    {
        HashSet<string> temp = new HashSet<string>();
        foreach (string s in begin)
        {
            if(end.Contains(s)) return level;
            if(deads.Contains(s)) continue;
            deads.Add(s);
            for (int i = 0; i < 4; i++)
            {
                char c = s[i];
                string s1 = s.Substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + s.Substring(i + 1);
                string s2 = s.Substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + s.Substring(i + 1);
                if(!deads.Contains(s1))
                    temp.Add(s1);
                if(!deads.Contains(s2))
                    temp.Add(s2);
            }
        }
        level++;
        begin = end;
        end = temp;
    }
    return -1;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: We can think of this problem as a shortest path problem on a graph: there are 10000 nodes (strings '0000' to '9999'), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so '0' and '9' differ by 1), and if both nodes are not in deadends.