LeetCode 752 Open the Lock - Example and Complexity Analysis

Start BFS from "0000".

Level 0: {"0000"}.

Level 1: all 8 neighbors of "0000" (except deadends). "1000", "9000", "0100", "0900", etc.

Level 2: neighbors of level 1 states (not visited, not deadends).

...continue until "0202" is found at level 6.

At most $10^4$ states (0000 to 9999). Each state has 8 neighbors. $O(10^4 \cdot 8)$ = $O(1)$ since bounded. Space: $O(10^4)$ for visited set.