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:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
You have a lock in front of you with 4 circular wheels. Each wheel has
10slots:'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
deadendsdead 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
targetrepresenting the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or-1if 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 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:
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4targetwill not be in the listdeadends.targetanddeadends[i]consist of digits only.
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:
(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:
(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:
(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:
(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 (5)
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.