> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Android Unlock Patterns Python Solution

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

LeetCode 351, [Medium](/catalog/medium). Topics: [Bit Manipulation](/catalog/topics/bit-manipulation), [Dynamic Programming](/catalog/topics/dynamic-programming), [Backtracking](/catalog/topics/backtracking), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/android-unlock-patterns/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
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

![Unlock patterns](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0300-0399/0351.Android%20Unlock%20Patterns/images/android-unlock.png)

```
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](https://github.com/wislertt/leetcode-py/blob/main/leetcode/android_unlock_patterns/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/android_unlock_patterns/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.