# Open the Lock
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/open-the-lock)
Canonical: https://scaleengineer.com/dsa/problems/open-the-lock
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table, String
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Flipkart](https://scaleengineer.com/companies/flipkart), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Zepto](https://scaleengineer.com/companies/zepto), [CARS24](https://scaleengineer.com/companies/cars24)
---
## Problem
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.

# Approaches
## Standard Breadth-First Search (BFS)
This approach models the problem as finding the shortest path in an unweighted graph. The lock combinations are the nodes, and a single turn of a wheel represents an edge. Breadth-First Search (BFS) is a perfect algorithm for this because it explores the graph level by level, guaranteeing that the first time we reach the target, it will be via the shortest possible path.
**Time:** O(D + C * W), where D is the number of deadends, C is the total number of combinations (10^4), and W is the number of wheels (4). We visit each of the C states at most once. For each state, we generate 2*W neighbors. The initial processing of deadends takes O(D). · **Space:** O(D + C), where D is the number of deadends and C is the total number of combinations (10^4). The `queue` and `visited` set can store up to C combinations in the worst case. The `deadSet` stores D combinations.
**Pros:** Guaranteed to find the shortest path.; Relatively straightforward to implement.; Handles all cases correctly.
**Cons:** Can be slow if the shortest path is long, as the search frontier (the queue size) can grow exponentially with the number of turns.; Explores a potentially large number of states before reaching the target.
### Explanation
We start at the initial combination "0000". We use a queue to perform a level-order traversal of the state space graph. A `visited` set is crucial to keep track of combinations we've already processed, preventing cycles and redundant work. The `deadends` are pre-loaded into this `visited` set to treat them as inaccessible states. The search proceeds level by level. At each level, we explore all reachable combinations from the combinations of the previous level. The level number corresponds to the number of turns. If we encounter the `target` combination, we return the current level count. If the queue becomes empty before finding the target, it means the target is unreachable from the start.

```java
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        String start = "0000";
        if (deadSet.contains(start)) {
            return -1;
        }

        queue.offer(start);
        visited.add(start);
        int turns = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String currentLock = queue.poll();

                if (currentLock.equals(target)) {
                    return turns;
                }

                for (int j = 0; j < 4; j++) {
                    char[] currentChars = currentLock.toCharArray();
                    char originalChar = currentChars[j];

                    // Turn forward
                    currentChars[j] = (char) (((originalChar - '0' + 1) % 10) + '0');
                    String nextLock = new String(currentChars);
                    if (!visited.contains(nextLock) && !deadSet.contains(nextLock)) {
                        queue.offer(nextLock);
                        visited.add(nextLock);
                    }

                    // Turn backward
                    currentChars[j] = (char) (((originalChar - '0' + 9) % 10) + '0');
                    String prevLock = new String(currentChars);
                    if (!visited.contains(prevLock) && !deadSet.contains(prevLock)) {
                        queue.offer(prevLock);
                        visited.add(prevLock);
                    }
                    
                    currentChars[j] = originalChar; // backtrack for next wheel
                }
            }
            turns++;
        }

        return -1; // Target not reachable
    }
}
```
### Algorithm
- Initialize a `Queue` for BFS and add the starting combination "0000".
- Initialize a `Set` called `visited` to store visited combinations and add all `deadends` to it.
- If "0000" is in the `deadends` set, return -1 immediately.
- Add "0000" to the `visited` set.
- Initialize `turns = 0`.
- While the queue is not empty:
  - Get the number of nodes at the current level, `level_size`.
  - For `i` from 0 to `level_size - 1`:
    - Dequeue the current combination `curr`.
    - If `curr` equals the `target`, return `turns`.
    - Generate all 8 possible next combinations by turning each of the 4 wheels one step forward and one step backward.
    - For each `neighbor` combination:
      - If `neighbor` has not been visited and is not a deadend, add it to the queue and the `visited` set.
  - Increment `turns`.
- If the loop finishes without finding the target, return -1.

## Bidirectional Breadth-First Search (Bi-BFS)
This is an optimization over the standard BFS. Instead of searching only from the start ("0000") towards the target, we simultaneously search from the target back towards the start. The search stops when the two search frontiers meet. This significantly reduces the search space and, therefore, the execution time.
**Time:** O(D + C * W), where D is the number of deadends, C is the total number of combinations (10^4), and W is the number of wheels (4). The worst-case complexity is the same as standard BFS, but the average-case performance is much better, closer to O(D + B^(d/2)) where B is the branching factor and d is the path length, because the search space is effectively halved in depth. · **Space:** O(D + C), where D is the number of deadends and C is the total number of combinations (10^4). While the search frontiers (`beginSet`, `endSet`) are smaller, the `visited` set can still grow to O(C) in the worst case.
**Pros:** Much faster on average than standard BFS because it explores a significantly smaller portion of the state space.; Still guarantees the shortest path.
**Cons:** Slightly more complex to implement due to managing two search frontiers.; The performance gain is most significant when the branching factor is large and the path is relatively long.
### Explanation
We maintain two sets of nodes to visit: one starting from "0000" (`beginSet`) and another starting from `target` (`endSet`). We also use a single `visited` set to keep track of all nodes encountered by either search to prevent redundant explorations and to detect when the frontiers meet. In each step, we choose to expand the smaller of the two sets. This helps to keep the two search frontiers of roughly equal size, which is key to the efficiency of the algorithm. We expand all nodes in the chosen set, generating their neighbors. If a neighbor is already in the other set, it means we've found a meeting point and thus a path. The total number of turns is the sum of turns taken from the start and the end.

```java
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if (deadSet.contains(start)) {
            return -1;
        }
        if (start.equals(target)) {
            return 0;
        }

        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        Set<String> visited = new HashSet<>();

        beginSet.add(start);
        visited.add(start);
        endSet.add(target);
        visited.add(target);

        int turns = 0;
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                Set<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }

            Set<String> tempSet = new HashSet<>();
            for (String currentLock : beginSet) {
                for (int j = 0; j < 4; j++) {
                    char[] currentChars = currentLock.toCharArray();
                    char originalChar = currentChars[j];

                    // Turn forward
                    currentChars[j] = (char) (((originalChar - '0' + 1) % 10) + '0');
                    String nextLock = new String(currentChars);
                    if (endSet.contains(nextLock)) {
                        return turns + 1;
                    }
                    if (!visited.contains(nextLock) && !deadSet.contains(nextLock)) {
                        tempSet.add(nextLock);
                        visited.add(nextLock);
                    }

                    // Turn backward
                    currentChars[j] = (char) (((originalChar - '0' + 9) % 10) + '0');
                    String prevLock = new String(currentChars);
                    if (endSet.contains(prevLock)) {
                        return turns + 1;
                    }
                    if (!visited.contains(prevLock) && !deadSet.contains(prevLock)) {
                        tempSet.add(prevLock);
                        visited.add(prevLock);
                    }
                    
                    currentChars[j] = originalChar; // backtrack
                }
            }
            turns++;
            beginSet = tempSet;
        }

        return -1;
    }
}
```
### Algorithm
- Initialize a `Set` `deadSet` with all `deadends`.
- If "0000" is in `deadSet`, return -1.
- Initialize two `Set`s: `beginSet` with "0000" and `endSet` with `target`.
- Initialize a `visited` `Set` and add "0000" and `target` to it.
- Initialize `turns = 0`.
- While `beginSet` and `endSet` are not empty:
  - If `beginSet` is larger than `endSet`, swap them to always expand the smaller set.
  - Create a `tempSet` for the next level's nodes.
  - For each `node` in `beginSet`:
    - Generate all 8 `neighbors`.
    - For each `neighbor`:
      - If `endSet` contains the `neighbor`, a path is found. Return `turns + 1`.
      - If the `neighbor` is not in `deadSet` and not in `visited`:
        - Add `neighbor` to `tempSet`.
        - Add `neighbor` to `visited`.
  - Increment `turns`.
  - Replace `beginSet` with `tempSet`.
- If the loop finishes, the target is unreachable. Return -1.

# Solutions
### Java

```java
class Solution {
private
  String start;
private
  String target;
private
  Set<String> s = new HashSet<>();
public
  int openLock(String[] deadends, String target) {
    if ("0000".equals(target)) {
      return 0;
    }
    start = "0000";
    this.target = target;
    for (String d : deadends) {
      s.add(d);
    }
    if (s.contains(start)) {
      return -1;
    }
    return bfs();
  }
private
  int bfs() {
    Map<String, Integer> m1 = new HashMap<>();
    Map<String, Integer> m2 = new HashMap<>();
    Deque<String> q1 = new ArrayDeque<>();
    Deque<String> q2 = new ArrayDeque<>();
    m1.put(start, 0);
    m2.put(target, 0);
    q1.offer(start);
    q2.offer(target);
    while (!q1.isEmpty() && !q2.isEmpty()) {
      int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
      if (t != -1) {
        return t;
      }
    }
    return -1;
  }
private
  int extend(Map<String, Integer> m1, Map<String, Integer> m2,
             Deque<String> q) {
    for (int n = q.size(); n > 0; --n) {
      String p = q.poll();
      int step = m1.get(p);
      for (String t : next(p)) {
        if (m1.containsKey(t) || s.contains(t)) {
          continue;
        }
        if (m2.containsKey(t)) {
          return step + 1 + m2.get(t);
        }
        m1.put(t, step + 1);
        q.offer(t);
      }
    }
    return -1;
  }
private
  List<String> next(String t) {
    List res = new ArrayList<>();
    char[] chars = t.toCharArray();
    for (int i = 0; i < 4; ++i) {
      char c = chars[i];
      chars[i] = c == '0' ? '9' : (char)(c - 1);
      res.add(String.valueOf(chars));
      chars[i] = c == '9' ? '0' : (char)(c + 1);
      res.add(String.valueOf(chars));
      chars[i] = c;
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution { public: unordered_set < string > s ; string start ; string target ; int openLock ( vector < string >& deadends , string target ) { if ( target == "0000" ) return 0 ; for ( auto d : deadends ) s . insert ( d ); if ( s . count ( "0000" )) return - 1 ; this -> start = "0000" ; this -> target = target ; return bfs (); } int bfs () { unordered_map < string , int > m1 ; unordered_map < string , int > m2 ; m1 [ start ] = 0 ; m2 [ target ] = 0 ; queue < string > q1 { { start } }; queue < string > q2 { { target } }; while ( ! q1 . empty () && ! q2 . empty ()) { int t = q1 . size () <= q2 . size () ? extend ( m1 , m2 , q1 ) : extend ( m2 , m1 , q2 ); if ( t != - 1 ) return t ; } return - 1 ; } int extend ( unordered_map < string , int >& m1 , unordered_map < string , int >& m2 , queue < string >& q ) { for ( int n = q . size (); n > 0 ; -- n ) { string p = q . front (); int step = m1 [ p ]; q . pop (); for ( string t : next ( p )) { if ( s . count ( t ) || m1 . count ( t )) continue ; if ( m2 . count ( t )) return step + 1 + m2 [ t ]; m1 [ t ] = step + 1 ; q . push ( t ); } } return - 1 ; } vector < string > next ( string & t ) { vector < string > res ; for ( int i = 0 ; i < 4 ; ++ i ) { char c = t [ i ]; t [ i ] = c == '0' ? '9' : ( char ) ( c - 1 ); res . push_back ( t ); t [ i ] = c == '9' ? '0' : ( char ) ( c + 1 ); res . push_back ( t ); t [ i ] = c ; } return res ; } };
```

### Python

```python
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 def extend(m1, m2, q): for _ in range(len(q)): p = q . popleft() step = m1[p] for t in next(p): if t in s or t in m1: continue if t in m2: return step + 1 + m2[t] m1[t] = step + 1 q . append(t) return - 1 def bfs(): m1, m2 = {"0000": 0}, {target: 0} q1, q2 = deque([('0000')]), deque([(target)]) while q1 and q2: t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2) if t != - 1: return t return - 1 if target == '0000': return 0 s = set(deadends) if '0000' in s: return - 1 return bfs()

```