Android Unlock Patterns Python Solution

Tested Python solution for LeetCode 351 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 351, Medium. Topics: Bit Manipulation, Dynamic Programming, Backtracking, Bitmask. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 351   # by problem number
lcpy gen -s android_unlock_patterns   # by problem name

​

Problem

Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an “unlock pattern” by connecting the dots in a specific sequence, forming a series of joined line segments where each segment’s endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true:

• All the dots in the sequence are distinct.
• If the line segment connecting two consecutive dots in the sequence passes through the center of any other dot, the other dot must have previously appeared in the sequence. No jumps through the center non-selected dots are allowed.
  • For example, connecting dots 2 and 9 without dots 5 or 6 appearing beforehand is valid because the line from dot 2 to dot 9 does not pass through the center of either dot 5 or 6.
  • However, connecting dots 1 and 3 without dot 2 appearing beforehand is invalid because the line from dot 1 to dot 3 passes through the center of dot 2.

Given two integers m and n, return the number of unique and valid unlock patterns of the Android grid lock screen that consist of at least m keys and at most n keys.

Two unlock patterns are considered unique if there is a dot in one sequence that is not in the other, or the order of the dots is different.

​

Examples

Input: m = 1, n = 1
Output: 9

Input: m = 1, n = 2
Output: 65

​

Constraints

• 1 <= m, n <= 9
• m <= n

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from typing import ClassVar


class Solution:
    # Dot passed through when moving directly between two keys, if any.
    # Keyed on unordered pairs; 0 means the segment crosses no other dot.
    CROSS: ClassVar[dict[tuple[int, int], int]] = {
        (1, 3): 2,
        (1, 7): 4,
        (1, 9): 5,
        (3, 7): 5,
        (3, 9): 6,
        (7, 9): 8,
        (2, 8): 5,
        (4, 6): 5,
    }

    # Time: O(n!) branch factor bounded by the 9-dot grid — exhaustive DFS
    # Space: O(9) — bitmask visited set and recursion depth
    def number_of_patterns(self, m: int, n: int) -> int:
        def dfs(current: int, used: int, length: int) -> int:
            if length > n:
                return 0
            count = 1 if length >= m else 0
            for nxt in range(1, 10):
                if used & (1 << nxt):
                    continue
                crossed = Solution.CROSS.get((current, nxt), Solution.CROSS.get((nxt, current), 0))
                if crossed and not used & (1 << crossed):
                    continue
                count += dfs(nxt, used | (1 << nxt), length + 1)
            return count

        return sum(dfs(start, 1 << start, 1) for start in range(1, 10))

​

Complexity

Time	Space
O(n!) branch factor bounded by the 9-dot grid — exhaustive DFS	O(9) — bitmask visited set and recursion depth

​

Tags

NeetCode All.