We have a lock with four wheels, each showing a digit from 0 to 9. The lock starts at "0000". In one move, we can rotate any single wheel one step forward or backward, with wrap-around between 0 and 9.
Some combinations are blocked and cannot be used. If the lock reaches any blocked combination, it gets stuck and can no longer be moved.
Given a target combination and a list of blocked combinations, find the minimum number of moves needed to reach the target from "0000" without ever entering a blocked state. If this is not possible, return -1.
Examples:
Input: barriers[] = ["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 stuck after the display becomes the barrier "0102".Input: barrier[] = ["0000"], target = "8888"
Output: -1
Explanation: The lock starts at "0000", which itself is a barrier. Since the lock becomes unusable immediately, no moves can be made. Therefore, it is impossible to reach the target combination, and the answer is -1.
Table of Content
[Naive Approach] Recursive Backtracking (DFS) – O(8^n) time and O(n) space
The simple idea is to try to explore all possible paths using DFS. From the current state, we generate all 8 neighbors and recursively move forward, tracking the minimum steps when we reach the target. We keep a visited set for the current path to avoid simple cycles, but overall the number of paths can still explode exponentially.
[Better Approach] Single - Ended BFS with Hashing
Here we treat each 4-digit string as a node and edges as single moves. We perform a normal BFS starting from "0000", exploring states level-by-level. The first time we reach the target, the current BFS depth gives the minimum number of moves. We use hash sets for barriers and visited states.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<string> getNeighbors(string &s) {
// generate neighbors by rotating each wheel
vector<string> r;
for (int i = 0; i < 4; i++) {
string a = s, b = s;
a[i] = (a[i] == '9') ? '0' : char(a[i] + 1);
b[i] = (b[i] == '0') ? '9' : char(b[i] - 1);
r.push_back(a);
r.push_back(b);
}
return r;
}
int unlockLock(vector<string>& barriers, string &target) {
// starting point
string start = "0000";
// blocked combinations
unordered_set<string> blocked(barriers.begin(), barriers.end());
// invalid starting conditions
if (blocked.count(start)) return -1;
if (start == target) return 0;
// BFS setup
unordered_set<string> vis;
queue<string> q;
vis.insert(start);
q.push(start);
int steps = 0;
// BFS traversal
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string cur = q.front();
q.pop();
for (string nx : getNeighbors(cur)) {
// skip blocked or visited
if (blocked.count(nx) || vis.count(nx)) continue;
// reached target
if (nx == target) return steps + 1;
vis.insert(nx);
q.push(nx);
}
}
steps++;
}
// unreachable
return -1;
}
int main() {
vector<string> barriers = {"0201","0101","0102","1212","2002"};
string target = "0202";
cout << unlockLock(barriers, target);
}
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// generate neighbors by rotating each wheel
static List<String> getNeighbors(String s) {
List<String> r = new ArrayList<>();
for (int i = 0; i < 4; i++) {
char[] a = s.toCharArray();
char[] b = s.toCharArray();
a[i] = (a[i] == '9') ? '0' : (char)(a[i] + 1);
b[i] = (b[i] == '0') ? '9' : (char)(b[i] - 1);
r.add(new String(a));
r.add(new String(b));
}
return r;
}
static int unlockLock(String[] barriers, String target) {
// starting point
String start = "0000";
// blocked combinations
Set<String> blocked = new HashSet<>(Arrays.asList(barriers));
// invalid starting conditions
if (blocked.contains(start)) return -1;
if (start.equals(target)) return 0;
// BFS setup
Set<String> vis = new HashSet<>();
Queue<String> q = new LinkedList<>();
vis.add(start);
q.add(start);
int steps = 0;
// BFS traversal
while (!q.isEmpty()) {
int sz = q.size();
while (sz-- > 0) {
String cur = q.poll();
for (String nx : getNeighbors(cur)) {
// skip blocked or visited
if (blocked.contains(nx) || vis.contains(nx)) continue;
// reached target
if (nx.equals(target)) return steps + 1;
vis.add(nx);
q.add(nx);
}
}
steps++;
}
// unreachable
return -1;
}
public static void main(String[] args) {
String[] barriers = {"0201","0101","0102","1212","2002"};
String target = "0202";
System.out.println(unlockLock(barriers, target));
}
}
from collections import deque
# generate neighbors by rotating wheels
def getNeighbors(s):
r = []
for i in range(4):
a = list(s)
b = list(s)
a[i] = '0' if a[i] == '9' else str(int(a[i]) + 1)
b[i] = '9' if b[i] == '0' else str(int(b[i]) - 1)
r.append("".join(a))
r.append("".join(b))
return r
# BFS to unlock lock
def unlockLock(barriers, target):
start = "0000"
blocked = set(barriers)
if start in blocked:
return -1
if start == target:
return 0
q = deque([start])
vis = {start}
steps = 0
# BFS loop
while q:
for _ in range(len(q)):
cur = q.popleft()
for nx in getNeighbors(cur):
# skip blocked or visited
if nx in blocked or nx in vis:
continue
# reached target
if nx == target:
return steps + 1
vis.add(nx)
q.append(nx)
steps += 1
return -1
if __name__ == "__main__":
barriers = ["0201","0101","0102","1212","2002"]
target = "0202"
print(unlockLock(barriers, target))
using System;
using System.Collections.Generic;
class GFG {
// generate neighbors by rotating wheels
static List<string> getNeighbors(string s) {
var r = new List<string>();
for (int i = 0; i < 4; i++) {
char[] a = s.ToCharArray();
char[] b = s.ToCharArray();
a[i] = (a[i] == '9') ? '0' : (char)(a[i] + 1);
b[i] = (b[i] == '0') ? '9' : (char)(b[i] - 1);
r.Add(new string(a));
r.Add(new string(b));
}
return r;
}
// BFS to unlock lock
static int unlockLock(string[] barriers, string target) {
string start = "0000";
var blocked = new HashSet<string>(barriers);
if (blocked.Contains(start)) return -1;
if (start == target) return 0;
var q = new Queue<string>();
var vis = new HashSet<string>();
q.Enqueue(start);
vis.Add(start);
int steps = 0;
// BFS loop
while (q.Count > 0) {
int sz = q.Count;
while (sz-- > 0) {
var cur = q.Dequeue();
foreach (var nx in getNeighbors(cur)) {
// skip blocked or visited
if (blocked.Contains(nx) || vis.Contains(nx))
continue;
// reached target
if (nx == target)
return steps + 1;
vis.Add(nx);
q.Enqueue(nx);
}
}
steps++;
}
return -1;
}
static void Main() {
string[] barriers = { "0201", "0101", "0102", "1212", "2002" };
string target = "0202";
Console.WriteLine(unlockLock(barriers, target));
}
}
// generate neighbors by rotating wheels
function getNeighbors(s) {
const r = [];
for (let i = 0; i < 4; i++) {
const a = s.split("");
const b = s.split("");
a[i] = a[i] === '9' ? '0' : String(Number(a[i]) + 1);
b[i] = b[i] === '0' ? '9' : String(Number(b[i]) - 1);
r.push(a.join(""));
r.push(b.join(""));
}
return r;
}
// BFS to unlock lock
function unlockLock(barriers, target) {
const start = "0000";
const blocked = new Set(barriers);
if (blocked.has(start)) return -1;
if (start === target) return 0;
const q = [start];
const vis = new Set([start]);
let steps = 0;
// BFS loop
while (q.length > 0) {
let sz = q.length;
while (sz--) {
const cur = q.shift();
for (const nx of getNeighbors(cur)) {
// skip blocked or visited
if (blocked.has(nx) || vis.has(nx)) continue;
// reached target
if (nx === target) return steps + 1;
vis.add(nx);
q.push(nx);
}
}
steps++;
}
return -1;
}
// Driver code
const barriers = ["0201","0101","0102","1212","2002"];
const target = "0202";
console.log(unlockLock(barriers, target));
Output
6
Time Complexity: O(10n × n), where n = 4
Auxiliary Space: O(b + 10n), where b = barriers size, n = 4
[Expected Approach 1] Optimized BFS Using Indexing
We can further optimize BFS by avoiding strings in hash sets for visited and barriers. Each 4-digit combination can be mapped to an integer in [0, 9999] (like "abcd" -> 1000*a + 100*b + 10*c + d). We then store blocked and vis in simple vector<bool> arrays which are faster and more memory-efficient than hash sets.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// encode string "1234" -> 1234
int encode(string &s) {
int v = 0;
for (char c : s) v = v * 10 + (c - '0');
return v;
}
// generate 8 neighbors by rotating wheels
vector<string> getNeighbors(string &s) {
vector<string> r;
r.reserve(8);
for (int i = 0; i < 4; i++) {
string a = s, b = s;
a[i] = (a[i] == '9') ? '0' : char(a[i] + 1);
b[i] = (b[i] == '0') ? '9' : char(b[i] - 1);
r.push_back(a);
r.push_back(b);
}
return r;
}
// BFS to find minimum steps
int unlockLock(vector<string>& barriers, string &target) {
string start = "0000";
if (start == target) return 0;
vector<bool> blocked(10000, false);
for (string &b : barriers)
blocked[encode(b)] = true;
if (blocked[encode(start)]) return -1;
vector<bool> vis(10000, false);
queue<string> q;
q.push(start);
vis[encode(start)] = true;
int steps = 0;
// BFS traversal
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string cur = q.front();
q.pop();
for (const string &next : getNeighbors(cur)) {
int id = encode(next);
if (blocked[id] || vis[id]) continue;
if (next == target) return steps + 1;
vis[id] = true;
q.push(next);
}
}
steps++;
}
return -1;
}
int main() {
vector<string> barriers = {"0201","0101","0102","1212","2002"};
string target = "0202";
cout << unlockLock(barriers, target);
}
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// encode string "1234" -> 1234
private static int encode(String s) {
int v = 0;
for (char c : s.toCharArray()) v = v * 10 + (c - '0');
return v;
}
// generate 8 neighbors by rotating wheels
private static List<String> getNeighbors(String s) {
List<String> r = new ArrayList<>();
for (int i = 0; i < 4; i++) {
char[] a = s.toCharArray();
char[] b = s.toCharArray();
a[i] = (a[i] == '9') ? '0' : (char) (a[i] + 1);
b[i] = (b[i] == '0') ? '9' : (char) (b[i] - 1);
r.add(new String(a));
r.add(new String(b));
}
return r;
}
// BFS to find minimum steps
public static int unlockLock(String[] barriers, String target) {
String start = "0000";
if (start.equals(target)) return 0;
// mark blocked states
boolean[] blocked = new boolean[10000];
for (String b : barriers) blocked[encode(b)] = true;
if (blocked[encode(start)]) return -1;
// visited states
boolean[] vis = new boolean[10000];
Queue<String> q = new LinkedList<>();
q.add(start);
vis[encode(start)] = true;
int steps = 0;
// BFS traversal
while (!q.isEmpty()) {
int sz = q.size();
while (sz-- > 0) {
String cur = q.poll();
for (String next : getNeighbors(cur)) {
int id = encode(next);
if (blocked[id] || vis[id]) continue;
if (next.equals(target)) return steps + 1;
vis[id] = true;
q.add(next);
}
}
steps++;
}
// target unreachable
return -1;
}
public static void main(String[] args) {
String[] barriers = {"0201", "0101", "0102", "1212", "2002"};
String target = "0202";
System.out.println(unlockLock(barriers, target));
}
}
from collections import deque
# encode string "1234" → 1234
def encode(s):
v = 0
for c in s:
v = v * 10 + int(c)
return v
# generate 8 neighbors by rotating wheels
def getNeighbors(s):
r = []
for i in range(4):
a = list(s)
b = list(s)
# rotate forward
a[i] = '0' if a[i] == '9' else str(int(a[i]) + 1)
# rotate backward
b[i] = '9' if b[i] == '0' else str(int(b[i]) - 1)
r.append("".join(a))
r.append("".join(b))
return r
# BFS to find minimum steps
def unlockLock(barriers, target):
start = "0000"
if start == target:
return 0
# mark blocked states
blocked = [False] * 10000
for b in barriers:
blocked[encode(b)] = True
if blocked[encode(start)]:
return -1
# visited states
vis = [False] * 10000
q = deque([start])
vis[encode(start)] = True
steps = 0
# BFS traversal
while q:
for _ in range(len(q)):
cur = q.popleft()
for next in getNeighbors(cur):
id = encode(next)
# skip blocked or visited
if blocked[id] or vis[id]:
continue
# reached target
if next == target:
return steps + 1
vis[id] = True
q.append(next)
steps += 1
# target unreachable
return -1
if __name__ == '__main__':
barriers = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"
print(unlockLock(barriers, target))
using System;
using System.Collections.Generic;
class GFG {
// BFS to find minimum steps
public int unlockLock(string[] barriers, string target) {
// starting combination
string start = "0000";
if (start == target) return 0;
// mark blocked states
bool[] blocked = new bool[10000];
foreach (string b in barriers)
blocked[encode(b)] = true;
if (blocked[encode(start)]) return -1;
// visited states
bool[] vis = new bool[10000];
Queue<string> q = new Queue<string>();
q.Enqueue(start);
vis[encode(start)] = true;
int steps = 0;
// BFS traversal
while (q.Count > 0) {
int sz = q.Count;
for (int i = 0; i < sz; i++) {
string cur = q.Dequeue();
foreach (string next in getNeighbors(cur)) {
int id = encode(next);
// skip blocked or visited
if (blocked[id] || vis[id]) continue;
// reached target
if (next == target) return steps + 1;
vis[id] = true;
q.Enqueue(next);
}
}
steps++;
}
// target unreachable
return -1;
}
// encode string "1234" -> 1234
private int encode(string s) {
int v = 0;
foreach (char c in s)
v = v * 10 + (c - '0');
return v;
}
// generate 8 neighbors by rotating wheels
private List<string> getNeighbors(string s) {
List<string> r = new List<string>();
for (int i = 0; i < 4; i++) {
char[] a = s.ToCharArray();
char[] b = s.ToCharArray();
// rotate forward
a[i] = (a[i] == '9') ? '0' : (char)(a[i] + 1);
// rotate backward
b[i] = (b[i] == '0') ? '9' : (char)(b[i] - 1);
r.Add(new string(a));
r.Add(new string(b));
}
return r;
}
static void Main() {
string[] barriers = { "0201", "0101", "0102", "1212", "2002" };
string target = "0202";
Console.WriteLine(unlockLock(barriers, target));
}
}
function encode(s) {
// encode string "1234" -> 1234
let v = 0;
for (let c of s) v = v * 10 + Number(c);
return v;
}
function getNeighbors(s) {
// generate 8 neighbors by rotating each wheel
const r = [];
for (let i = 0; i < 4; i++) {
let a = s.split(''), b = s.split('');
// rotate forward
a[i] = (a[i] === '9') ? '0' : String(+a[i] + 1);
// rotate backward
b[i] = (b[i] === '0') ? '9' : String(+b[i] - 1);
r.push(a.join(''));
r.push(b.join(''));
}
return r;
}
function unlockLock(barriers, target) {
const start = "0000";
if (start === target) return 0;
// blocked states
const blocked = Array(10000).fill(false);
for (let b of barriers) blocked[encode(b)] = true;
if (blocked[encode(start)]) return -1;
// visited states
const vis = Array(10000).fill(false);
const q = [start];
vis[encode(start)] = true;
let steps = 0;
// BFS traversal
while (q.length) {
const sz = q.length;
for (let i = 0; i < sz; i++) {
const cur = q.shift();
for (let nx of getNeighbors(cur)) {
let id = encode(nx);
// skip blocked or visited
if (blocked[id] || vis[id]) continue;
// reached target
if (nx === target) return steps + 1;
vis[id] = true;
q.push(nx);
}
}
steps++;
}
// target unreachable
return -1;
}
// Driver code
const barriers = ["0201","0101","0102","1212","2002"];
const target = "0202";
console.log(unlockLock(barriers, target));
Output
6
Time Complexity: O(b + 10n × n), where b = barriers size, n = 4
Auxiliary Space: O(10n),, where n = 4
[Expected Approach 2] Bidirectional BFS
Bidirectional BFS runs two BFS searches: one from "0000" and one from target. Each step, we expand the smaller frontier. When a state generated from one side already exists in the opposite side’s visited set, we know the paths meet there and we have found the minimum number of moves. This often explores many fewer states than normal BFS in practice.
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
// generate all 8 neighbors by rotating each wheel forward/backward
vector<string> nxts(const string &s) {
vector<string> r;
r.reserve(8);
for (int i = 0; i < 4; i++) {
string a = s, b = s;
// rotate forward
a[i] = (a[i] == '9') ? '0' : (char)(a[i] + 1);
// rotate backward
b[i] = (b[i] == '0') ? '9' : (char)(b[i] - 1);
r.push_back(a);
r.push_back(b);
}
return r;
}
// bidirectional BFS to find minimum steps to unlock
int unlockLock(vector<string>& barriers, string &target) {
string start = "0000";
// set of blocked combinations
unordered_set<string> blocked(barriers.begin(), barriers.end());
// invalid start or target, or already at target
if (blocked.count(start) || blocked.count(target)) return -1;
if (start == target) return 0;
// sets for bidirectional BFS
unordered_set<string> frontSet{start}, backSet{target};
unordered_set<string> visitedFront{start}, visitedBack{target};
int steps = 0;
// BFS loop
while (!frontSet.empty() && !backSet.empty()) {
// always expand the smaller frontier
if (frontSet.size() > backSet.size()) {
swap(frontSet, backSet);
swap(visitedFront, visitedBack);
}
unordered_set<string> nextFront;
for (auto &s : frontSet) {
for (auto &n : nxts(s)) {
// skip blocked states
if (blocked.count(n)) continue;
// if intersection found, shortest path achieved
if (visitedBack.count(n)) return steps + 1;
// add new state to next frontier
if (!visitedFront.count(n)) {
visitedFront.insert(n);
nextFront.insert(n);
}
}
}
frontSet = move(nextFront);
steps++;
}
// target unreachable
return -1;
}
int main() {
vector<string> barriers = {"0201","0101","0102","1212","2002"};
string target = "0202";
cout << unlockLock(barriers, target) << endl;
}
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// generate all 8 neighbors by rotating each wheel forward/backward
private static List<String> getNeighbors(String s){
List<String> r = new ArrayList<>();
for(int i = 0; i < 4; i++){
char[] a = s.toCharArray();
char[] b = s.toCharArray();
// rotate forward
a[i] = (a[i]=='9') ? '0' : (char)(a[i] + 1);
// rotate backward
b[i] = (b[i]=='0') ? '9' : (char)(b[i] - 1);
r.add(new String(a));
r.add(new String(b));
}
return r;
}
// bidirectional BFS to find minimum steps to unlock
public static int unlockLock(String[] barriers, String target) {
String start = "0000";
// set of blocked combinations
Set<String> blocked = new HashSet<>(Arrays.asList(barriers));
// invalid start or target, or already at target
if (blocked.contains(start) || blocked.contains(target)) return -1;
if (start.equals(target)) return 0;
// sets for bidirectional BFS
Set<String> frontSet = new HashSet<>(), backSet = new HashSet<>();
Set<String> visitedFront = new HashSet<>(), visitedBack = new HashSet<>();
frontSet.add(start);
backSet.add(target);
visitedFront.add(start);
visitedBack.add(target);
int steps = 0;
// BFS loop
while (!frontSet.isEmpty() && !backSet.isEmpty()) {
// always expand the smaller frontier
if (frontSet.size() > backSet.size()) {
Set<String> tmp = frontSet; frontSet = backSet; backSet = tmp;
tmp = visitedFront; visitedFront = visitedBack; visitedBack = tmp;
}
Set<String> nextFront = new HashSet<>();
for (String s : frontSet) {
for (String n : getNeighbors(s)) {
// skip blocked states
if (blocked.contains(n)) continue;
// if intersection found, shortest path achieved
if (visitedBack.contains(n)) return steps + 1;
// add new state to next frontier
if (!visitedFront.contains(n)) {
visitedFront.add(n);
nextFront.add(n);
}
}
}
frontSet = nextFront;
steps++;
}
// target unreachable
return -1;
}
public static void main(String[] args){
String[] barriers = {"0201","0101","0102","1212","2002"};
String target = "0202";
System.out.println(unlockLock(barriers, target));
}
}
from collections import deque
# generate all 8 neighbors by rotating each wheel forward/backward
def getNeighbors(s):
neighbors = []
for i in range(4):
a = list(s)
b = list(s)
# rotate forward
a[i] = '0' if a[i] == '9' else str(int(a[i]) + 1)
# rotate backward
b[i] = '9' if b[i] == '0' else str(int(b[i]) - 1)
neighbors.append("".join(a))
neighbors.append("".join(b))
return neighbors
# bidirectional BFS to find minimum steps to unlock
def unlockLock(barriers, target):
start = "0000"
# blocked combinations
blocked = set(barriers)
# invalid start/target or already at target
if start in blocked or target in blocked:
return -1
if start == target:
return 0
# sets for bidirectional BFS
frontSet = {start}
backSet = {target}
visitedFront = {start}
visitedBack = {target}
steps = 0
# BFS loop
while frontSet and backSet:
# always expand the smaller frontier
if len(frontSet) > len(backSet):
frontSet, backSet = backSet, frontSet
visitedFront, visitedBack = visitedBack, visitedFront
nextFront = set()
for s in frontSet:
for n in getNeighbors(s):
# skip blocked states
if n in blocked:
continue
# if intersection found, shortest path achieved
if n in visitedBack:
return steps + 1
# add new state to next frontier
if n not in visitedFront:
visitedFront.add(n)
nextFront.add(n)
frontSet = nextFront
steps += 1
# target unreachable
return -1
if __name__ == '__main__':
barriers = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"
print(unlockLock(barriers, target))
using System;
using System.Collections.Generic;
class GFG {
// bidirectional BFS to find minimum steps to unlock
public int unlockLock(string[] barriers, string target) {
string start = "0000";
// blocked combinations
HashSet<string> blocked = new HashSet<string>(barriers);
// invalid start/target or already at target
if (blocked.Contains(start) || blocked.Contains(target))
return -1;
if (start == target)
return 0;
// sets for bidirectional BFS
HashSet<string> frontSet = new HashSet<string> { start };
HashSet<string> backSet = new HashSet<string> { target };
HashSet<string> visitedFront = new HashSet<string> { start };
HashSet<string> visitedBack = new HashSet<string> { target };
int steps = 0;
// BFS loop
while (frontSet.Count > 0 && backSet.Count > 0) {
// always expand the smaller frontier
if (frontSet.Count > backSet.Count) {
var tmpSet = frontSet;
frontSet = backSet;
backSet = tmpSet;
var tmpVisited = visitedFront;
visitedFront = visitedBack;
visitedBack = tmpVisited;
}
HashSet<string> nextFront = new HashSet<string>();
foreach (string s in frontSet) {
foreach (string n in getNeighbors(s)) {
// skip blocked states
if (blocked.Contains(n))
continue;
// if intersection found
if (visitedBack.Contains(n))
return steps + 1;
if (!visitedFront.Contains(n)) {
visitedFront.Add(n);
nextFront.Add(n);
}
}
}
frontSet = nextFront;
steps++;
}
// target unreachable
return -1;
}
// generate all 8 neighbors by rotating each wheel
private List<string> getNeighbors(string s) {
List<string> neighbors = new List<string>();
for (int i = 0; i < 4; i++) {
char[] a = s.ToCharArray();
char[] b = s.ToCharArray();
// rotate forward
a[i] = (a[i] == '9') ? '0' : (char)(a[i] + 1);
// rotate backward
b[i] = (b[i] == '0') ? '9' : (char)(b[i] - 1);
neighbors.Add(new string(a));
neighbors.Add(new string(b));
}
return neighbors;
}
static void Main() {
string[] barriers = { "0201", "0101", "0102", "1212", "2002" };
string target = "0202";
Console.WriteLine(unlockLock(barriers, target));
}
}
// generate all 8 neighbors by rotating each wheel
function getNeighbors(s) {
const neighbors = [];
for (let i = 0; i < 4; i++) {
let a = s.split(''), b = s.split('');
// rotate forward
a[i] = (a[i] === '9') ? '0' : String(+a[i] + 1);
// rotate backward
b[i] = (b[i] === '0') ? '9' : String(+b[i] - 1);
neighbors.push(a.join(''));
neighbors.push(b.join(''));
}
return neighbors;
}
// bidirectional BFS to find minimum turns to unlock
function unlockLock(barriers, target) {
const start = "0000";
// blocked states
const blocked = new Set(barriers);
// invalid start/target or already at target
if (blocked.has(start) || blocked.has(target)) return -1;
if (start === target) return 0;
// sets for bidirectional BFS
let frontSet = new Set([start]);
let backSet = new Set([target]);
let visitedFront = new Set([start]);
let visitedBack = new Set([target]);
let steps = 0;
// BFS loop
while (frontSet.size > 0 && backSet.size > 0) {
// always expand the smaller frontier
if (frontSet.size > backSet.size) {
[frontSet, backSet] = [backSet, frontSet];
[visitedFront, visitedBack] = [visitedBack, visitedFront];
}
let nextFront = new Set();
for (let s of frontSet) {
for (let n of getNeighbors(s)) {
// skip blocked states
if (blocked.has(n)) continue;
// if intersection found, shortest path achieved
if (visitedBack.has(n)) return steps + 1;
// add new state to next frontier
if (!visitedFront.has(n)) {
visitedFront.add(n);
nextFront.add(n);
}
}
}
frontSet = nextFront;
steps++;
}
// target unreachable
return -1;
}
// Driver code
const barriers = ["0201","0101","0102","1212","2002"];
const target = "0202";
console.log(unlockLock(barriers, target));
Output
6
Time Complexity: O(b + 10n × n), where b = barriers size, n = 4
Auxiliary Space: O(b + 10n), where n = 4