NUHMAN.com

🧩 Problem Statement

Given two integers m and n, return the number of valid unlock patterns of the Android lock screen, which consist of minimum m keys and maximum n keys.

⚠️ Rules:

• Each pattern must connect at least m keys and at most n keys.
• All the keys must be distinct.
• If the line passes through a non-selected key, then the pattern is invalid unless that key has already been used.
• The order of the pattern matters.

Think of the 3x3 Android lock screen numbered like this:

1 2 3
4 5 6
7 8 9

🔢 Examples

python

Input: m = 1, n = 1
Output: 9
Explanation: Each single key (1 through 9) forms a valid pattern.

💡 Intuition

We treat this as a backtracking problem where:

• We try starting from each digit.
• Recursively build patterns by visiting unused keys.
• Ensure each move is valid using a predefined skip map.

📐 Skip Table Design

Some movements require an intermediate digit to be visited first. For example:

• 1 -> 3 is invalid unless 2 has been used.
• 1 -> 9 is invalid unless 5 has been used.

We use a 10x10 skip table to encode these constraints.

✅ Python Solution Using DFS

python

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        # Create skip array
        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[2][8] = skip[8][2] = \
        skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5

        visited = [False] * 10

        def dfs(current, remaining):
            if remaining == 0:
                return 1
            count = 0
            visited[current] = True
            for next_key in range(1, 10):
                if not visited[next_key] and (skip[current][next_key] == 0 or visited[skip[current][next_key]]):
                    count += dfs(next_key, remaining - 1)
            visited[current] = False
            return count

        result = 0
        # Use symmetry to reduce computation
        for length in range(m, n + 1):
            result += dfs(1, length - 1) * 4  # 1, 3, 7, 9 are symmetric
            result += dfs(2, length - 1) * 4  # 2, 4, 6, 8 are symmetric
            result += dfs(5, length - 1)      # center is unique
        return result

🔍 Step-by-Step Breakdown

1. Create the skip table for all key pairs that require an intermediate digit.
2. DFS function tries every valid move recursively and tracks visited digits.
3. Use symmetry to reduce repetitive computations.
4. For every length between m and n, start DFS from representative digits.

⏱️ Time & Space Complexity

MetricValueTimeO(9!) (due to backtracking, but optimized with pruning)SpaceO(9) for visited array

🔁 Symmetry Optimization

• Digits 1, 3, 7, 9 are symmetric ⇒ Multiply their result by 4.
• Digits 2, 4, 6, 8 are symmetric ⇒ Multiply their result by 4.
• Digit 5 is at the center ⇒ Unique pattern.

✅ Conclusion

LeetCode 351: Android Unlock Patterns blends graph traversal, pruning, and pattern generation into a challenging but insightful problem. You’ll master:

• Recursive backtracking
• Pattern constraints with condition checks
• Efficient state tracking with visited arrays
• Smart use of symmetry to reduce work