⚡Flashcard Drill➔
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

  1. Precompute the skip table: moving between two dots that are two apart in a line requires the midpoint to be visited.
  2. There are only a few such pairs: the four edges through the centre, the two diagonal pairs, and the two vertical/horizontal pairs.
  3. DFS from each starting dot, tracking the visited set; at each step try all unvisited dots whose midpoint (if any) is already visited.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems