*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #752 (*Medium*): Open the Lock

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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, returnthe minimum total number of turns required to open the lock, or.`-1`

if it is impossible

####
*Examples:*

*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 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 can't reach the target without getting stuck.

Example 4: Input: deadends = ["0000"], target = "8888" Output: -1

####
*Constraints:*

*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.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

There are **10^4** combinations for the lock, and we can think of each one as a node on a graph. We then have to find the shortest path from **"0000"** to the **target** combination without going through one of the **deadends**.

In a normal problem dealing with a shortest path on a graph, we keep track of previously visited nodes in a boolean array of combinations (**seen**), so we can just go ahead and add all of the **deadends** into **seen** by converting the strings to numbers.

Then, we can solve the shortest path problem with a standard **queue**. We'll have an outer loop to keep track of the number of **turns** we've taken, while the inner loop will run the length of the current turn (**qlen**).

On each turn, we'll take the current **queue** entry (**curr**), then we'll iterate through the four digits and create both a **mask** for that digit as well as a **masked** version of **curr**. (For example, if **curr = 4213** and we're on the **2nd** digit, **mask** would be **1** and **masked** would be **4203**.) This way we can change the **mask** and add it back to **masked** to form the **next** combination. For each digit, we'll also have to attempt both the forward and backward move, so we can add **1** and then **9** to the **mask**, before applying **modulo 10**, to get the new values.

For each **next** combination, if it's our **target** we should **return turns**, and if it's been **seen**, we should **continue** to the next iteration. Otherwise, we should consider it **seen** and add it to the **queue**. If we ever completely empty the **queue**, then there are no more possible moves, so we should **return -1**.

We also need to remember to account for edge cases where **"0000"** is either a **deadend** or the **target**.

**Time Complexity: O(1e4) or O(1)**because there are always a maximum of**1e4**possible combinations**Space Complexity: O(2e4) or O(1)**for**seen**and the maximum length of the**queue**

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var openLock = function(deadends, target) {
if (target === "0000") return 0
let queue = [0], seen = new Uint8Array(10000)
for (let d of deadends)
seen[~~d] = 1
target = ~~target
if (seen[0]) return -1
for (let turns = 1; queue.length; turns++) {
let qlen = queue.length
for (let i = 0; i < qlen; i++) {
let curr = queue.shift()
for (let j = 1; j < 10000; j *= 10) {
let mask = ~~(curr % (j * 10) / j),
masked = curr - (mask * j)
for (let k = 1; k < 10; k += 8) {
let next = masked + (mask + k) % 10 * j
if (seen[next]) continue
if (next === target) return turns
seen[next] = 1
queue.push(next)
}
}
}
}
return -1
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if target == "0000": return 0
queue, target = deque([0]), int(target)
seen, turns = [0] * 10000, 1
for d in deadends: seen[int(d)] = 1
if seen[0]: return -1
while len(queue):
qlen = len(queue)
for i in range(qlen):
curr, j = queue.popleft(), 1
while j < 10000:
mask = curr % (j * 10) // j
masked = curr - (mask * j)
for k in range(1,10,8):
nxt = masked + (mask + k) % 10 * j
if seen[nxt]: continue
if nxt == target: return turns
seen[nxt] = 1
queue.append(nxt)
j *= 10
turns += 1
return -1
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int openLock(String[] deadends, String target) {
if (target.equals("0000")) return 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
boolean[] seen = new boolean[10000];
for (String el : deadends)
seen[Integer.parseInt(el)] = true;
int targ = Integer.parseInt(target);
if (seen[0]) return -1;
for (int turns = 1; !queue.isEmpty(); turns++) {
int qlen = queue.size();
for (int i = 0; i < qlen; i++) {
int curr = queue.poll();
for (int j = 1; j < 10000; j *= 10) {
int mask = curr % (j * 10) / j,
masked = curr - (mask * j);
for (int k = 1; k < 10; k += 8) {
int next = masked + (mask + k) % 10 * j;
if (seen[next]) continue;
if (next == targ) return turns;
seen[next] = true;
queue.add(next);
}
}
}
}
return -1;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
if (target == "0000") return 0;
queue<int> queue;
queue.push(0);
bool seen[10000]{false};
for (auto& d : deadends)
seen[stoi(d)] = true;
int targ = stoi(target);
if (seen[0]) return -1;
for (int turns = 1; queue.size(); turns++) {
int qlen = queue.size();
for (int i = 0; i < qlen; i++) {
int curr = queue.front();
queue.pop();
for (int j = 1; j < 10000; j *= 10) {
int mask = curr % (j * 10) / j,
masked = curr - (mask * j);
for (int k = 1; k < 10; k += 8) {
int next = masked + (mask + k) % 10 * j;
if (seen[next]) continue;
if (next == targ) return turns;
seen[next] = true;
queue.push(next);
}
}
}
}
return -1;
}
};
```

## Top comments (10)

I'm not really sure I understand your use of the words "convoluted", "over involved", and "vague" in the context of a single function with 20-30 lines of code, but... okay.

I'm also happy for you that, at 20+ years of software experience, you feel like you can walk out of an interview with a potential employer over this. Not all of us have that luxury, of course. And despite the fact that these types of problems are not necessarily the most ideal way to evaluate a potential employee, whiteboarding challenges have become somewhat of an industry standard interview experience.

As such, and your condescension aside, there are quite a lot of us who are simply forced to learn and hone these skills in order to have a better chance of getting a job in the industry, especially from one of the top companies.

More importantly, these posts are not made with an aim towards "self-gratification" (unlike your rather patronizing response). If they were, only the code would have been included. On the contrary, I write these posts (which each take a fair bit of time) with the aim of helping others to be able to see not just how the solution works, but also how to recognize which approach to look for and use in these and similar situations.

Since starting to make these posts, I've received a number of responses noting appreciation for the explanations. You'll excuse me if I consider their opinion to be more important to me than yours. Moreover, if the content of my posts bothers you, you can quite easily avoid them.

With all that said, you're entitled to your opinion; I, however, will consider your opinion to be "far too nonsensical to be significant for me."

@thebarefootdev there is no rule that a function must have maximum of 10 lines of code. Yes we must keep them short, but not limited with exact line numbers. There are thousands of functions in modern libraries written by top companies which have more than 10 lines of code.

Also in competitive programming challenges your task is to solve the problem quickly. You are not developing a software library and don't have the obligation to make it scalable. So, in this solution functions are quite simple and they do one thing.

Having been studied or worked +20 years in software doesn't mean you do and tell right things. There are people reading your posts.

Functions are quite simple and short, It is not right to endeavor that especially in this context.

How can I reply your "10 lines of function" argument without reading? That was your opinion and I wrote mine. Do not get offended by that.

Thank you @seanpgallivan for the solution, it was really helpful.