Leetcode - Minimum Lock Turns

Medium

Jan 13, 2026

#graph

#bfs

Minimum Lock Turns

Given a starting lock combination (e.g. 0000) find the minimum number of turns required for each wheel to get to a target (e.g. 0202) in the presence of potentially blocked states.

Example 1:

Input: start = "0000", target = "0202", blocked = ["0201","0101","0102","1212","2002"]
Output: 6

Example 2:

Input: start = "1234", target = "1236", blocked = []
Output: 2

Example 3:

Input: start = "5555", target = "5559", blocked = ["5556", "5557", "5558"]
Output: 6

Notes

Intuition

Each lock combination is a graph node with 8 neighbors (4 wheels × 2 directions). BFS from start to target finds the minimum number of turns, avoiding blocked combinations.

Implementation

Generate neighbors by turning each wheel up or down (using mod 10 for wraparound). Start BFS with (start_combo, 0) in the queue and a visited set. For each state, try all neighbors—skip if visited or blocked. If a neighbor is the target, return turns + 1. Otherwise, add to queue and visited.

Edge-cases

Check if start equals target (return 0) or if start is blocked (return -1) before starting BFS.

Time: O(10⁴) — at most 10,000 possible states
Space: O(10⁴) — visited set and queue

Complexity

Solution

from typing import List
from collections import deque

class Solution:
    def neighbours(self, combo: str) -> List[str]:
        result = []
        for i in range(len(combo)):
            up_n = [int(c) for c in combo]
            down_n = [int(c) for c in combo]
            up_n[i] = (up_n[i] + 1) % 10
            down_n[i] = (down_n[i] - 1) % 10
            result.append("".join([str(n) for n in up_n]))
            result.append("".join([str(n) for n in down_n]))
        return result

    def minLockTurns(self, start: str, target: str, blocked: List[str]) -> int:
        block = set(blocked)
        if start in block:
            return -1
        if start == target:
            return 0

        q = deque([(start, 0)])
        visited = { start }
        while q:
            curr, turns = q.popleft()
            for n in self.neighbours(curr):
                if n in visited or n in block:
                    continue
                if n == target:
                    return turns + 1
                visited.add(n)
                q.append((n, turns + 1))
        return -1

if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()