LeetCode #752 — MEDIUM

Open the Lock

Move from brute-force thinking to an efficient approach using array strategy.

The Problem

Problem Statement

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.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Hash Map

Example 1

["0201","0101","0102","1212","2002"]
"0202"

Example 2

["8888"]
"0009"

Example 3

["8887","8889","8878","8898","8788","8988","7888","9888"]
"8888"

Core Insight

What unlocks the optimal approach

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

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #752: Open the Lock
class Solution {
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }
        Set<String> s = new HashSet<>(Arrays.asList(deadends));
        if (s.contains("0000")) {
            return -1;
        }
        Deque<String> q = new ArrayDeque<>();
        q.offer("0000");
        s.add("0000");
        int ans = 0;
        while (!q.isEmpty()) {
            ++ans;
            for (int n = q.size(); n > 0; --n) {
                String p = q.poll();
                for (String t : next(p)) {
                    if (target.equals(t)) {
                        return ans;
                    }
                    if (!s.contains(t)) {
                        q.offer(t);
                        s.add(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;
    }
}

// Accepted solution for LeetCode #752: Open the Lock
func openLock(deadends []string, target string) int {
	if target == "0000" {
		return 0
	}
	s := make(map[string]bool)
	for _, d := range deadends {
		s[d] = true
	}
	if s["0000"] {
		return -1
	}
	q := []string{"0000"}
	s["0000"] = true
	ans := 0
	next := func(t string) []string {
		s := []byte(t)
		var res []string
		for i, b := range s {
			s[i] = b - 1
			if s[i] < '0' {
				s[i] = '9'
			}
			res = append(res, string(s))
			s[i] = b + 1
			if s[i] > '9' {
				s[i] = '0'
			}
			res = append(res, string(s))
			s[i] = b
		}
		return res
	}
	for len(q) > 0 {
		ans++
		for n := len(q); n > 0; n-- {
			p := q[0]
			q = q[1:]
			for _, t := range next(p) {
				if target == t {
					return ans
				}
				if !s[t] {
					q = append(q, t)
					s[t] = true
				}
			}
		}
	}
	return -1
}

# Accepted solution for LeetCode #752: Open the Lock
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

        if target == '0000':
            return 0
        s = set(deadends)
        if '0000' in s:
            return -1
        q = deque(['0000'])
        s.add('0000')
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                p = q.popleft()
                for t in next(p):
                    if t == target:
                        return ans
                    if t not in s:
                        q.append(t)
                        s.add(t)
        return -1

// Accepted solution for LeetCode #752: Open the Lock
struct Solution;
use std::collections::HashSet;

impl Solution {
    fn open_lock(deadends: Vec<String>, target: String) -> i32 {
        let mut visited: HashSet<u32> = deadends.into_iter().map(Self::s2x).collect();
        let target = Self::s2x(target);
        let start = 0;
        if visited.contains(&start) {
            return -1;
        }
        let mut begin: HashSet<u32> = HashSet::new();
        let mut end: HashSet<u32> = HashSet::new();
        begin.insert(start);
        end.insert(target);
        let mut level = 0;
        while !begin.is_empty() && !end.is_empty() {
            let mut temp: HashSet<u32> = HashSet::new();
            for x in begin {
                if end.contains(&x) {
                    return level;
                } else {
                    visited.insert(x);
                    for y in Self::adj(x) {
                        if !visited.contains(&y) {
                            temp.insert(y);
                        }
                    }
                }
            }
            level += 1;
            begin = end;
            end = temp
        }
        -1
    }

    fn s2x(s: String) -> u32 {
        let mut res = 0;
        for (i, b) in s.bytes().map(|b| (b - b'0') as u32).enumerate() {
            res |= b << (i * 8);
        }
        res
    }

    fn x2s(x: u32) -> String {
        let mut v: Vec<u8> = vec![0; 4];
        for i in 0..4 {
            v[i] = ((x >> (i * 8)) & 0xff) as u8;
        }
        v.into_iter().map(|b| (b + b'0') as char).collect()
    }

    fn adj(x: u32) -> Vec<u32> {
        let mut res = vec![];
        for i in 0..4 {
            let b1 = (((x >> (i * 8) & 0xff) + 1) % 10) << (i * 8);
            let b2 = (((x >> (i * 8) & 0xff) + 9) % 10) << (i * 8);
            let mask = !(0xff << (i * 8));
            res.push((x & mask) | b1);
            res.push((x & mask) | b2);
        }
        res
    }
}

#[test]
fn test() {
    let deadends = vec_string!["0201", "0101", "0102", "1212", "2002"];
    let target = "0202".to_string();
    let res = 6;
    assert_eq!(Solution::open_lock(deadends, target), res);
}

// Accepted solution for LeetCode #752: Open the Lock
function openLock(deadends: string[], target: string): number {
    const vis = Array<boolean>(10_000);
    const q = [[0, 0, 0, 0, 0]];
    const t = +target;
    deadends.forEach(s => (vis[+s] = true));

    for (const [a, b, c, d, ans] of q) {
        const key = a * 1000 + b * 100 + c * 10 + d;
        if (vis[key]) {
            continue;
        }

        vis[key] = true;
        if (key === t) {
            return ans;
        }

        for (let i = 0; i < 4; i++) {
            const next = [a, b, c, d, ans + 1];
            const prev = [a, b, c, d, ans + 1];
            next[i] = (next[i] + 11) % 10;
            prev[i] = (prev[i] + 9) % 10;
            q.push(prev, next);
        }
    }

    return -1;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.