NeetCode #517LC-351MediumBacktracking
← Back to All Problems#517 · #351 · Android Unlock Patterns(安卓系统手势解锁)
📌 Problem Statement & Constraints
Android unlock patterns are drawn on a 3x3 grid of dots using 4 to 9 distinct dots. A move may skip over an already-visited dot, but cannot jump over an unvisited one. Given
m and n, return the number of valid patterns of length between m and n inclusive. Constraints: 1 <= m, n <= 9.💡 Core Algorithmic Approaches
- Precompute the skip table: moving between two dots that are two apart in a line requires the midpoint to be visited.
- There are only a few such pairs: the four edges through the centre, the two diagonal pairs, and the two vertical/horizontal pairs.
- DFS from each starting dot, tracking the visited set; at each step try all unvisited dots whose midpoint (if any) is already visited.
- Count patterns whose length is in
[m, n].
💻 Benchmark Python3 Implementation
class Solution:
def numberOfPatterns(self, m: int, n: int) -> int:
# skip[a][b] = the dot that must be visited to move directly from a to b
skip = [[0] * 10 for _ in range(10)]
skip[1][3] = skip[3][1] = 2
skip[1][7] = skip[7][1] = 4
skip[3][9] = skip[9][3] = 6
skip[7][9] = skip[9][7] = 8
skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = 5
visited = [False] * 10
def dfs(cur: int, length: int) -> int:
if length > n:
return 0
total = 1 if length >= m else 0 # this pattern counts if long enough
for nxt in range(1, 10):
if visited[nxt]:
continue
mid = skip[cur][nxt]
if mid and not visited[mid]:
continue # cannot jump over an unvisited dot
visited[nxt] = True
total += dfs(nxt, length + 1)
visited[nxt] = False
return total
res = 0
for start in range(1, 10):
visited[start] = True
res += dfs(start, 1)
visited[start] = False
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(9!): bounded by the number of orderings of the dots, heavily pruned.
💾 Space Complexity
O(1) for the skip table and the visited array.
⚠️ Interview Pitfalls & Follow-ups
- Omitting the skip table: patterns like 1-3 (jumping over 2) would be wrongly allowed.
- Treating all skips as requiring the midpoint: only the specific pairs listed have midpoints; all other moves are direct.
- Counting only patterns of exactly length
n: the range[m, n]is inclusive. - Assuming the pattern must start at dot 1: any dot may start.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.