# LeetCode 351: Android Unlock Patterns

## Problem Restatement

We have a `3 x 3` Android lock screen.

The dots are numbered like this:

```text
1 2 3
4 5 6
7 8 9
```

Given two integers `m` and `n`, count how many valid unlock patterns have length at least `m` and at most `n`.

A pattern is a sequence of distinct dots.

A move from one dot to another is valid if either:

1. The line does not pass through another dot.
2. The line passes through another dot, but that middle dot has already been used.

For example, the move `1 -> 3` passes through `2`.

So `1 -> 3` is invalid unless `2` was already selected.

The move `1 -> 9` passes through `5`.

So `1 -> 9` is invalid unless `5` was already selected.

The order matters. Pattern `1 -> 2 -> 3` and pattern `3 -> 2 -> 1` are different patterns.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `m` and `n` |
| Output | Number of valid unlock patterns |
| Constraint | `1 <= m <= n <= 9` |
| Main rule | Dots cannot repeat |
| Special rule | A jump over a dot requires that dot to be used first |

Example function shape:

```python
def numberOfPatterns(m: int, n: int) -> int:
    ...
```

## Examples

For:

```python
m = 1
n = 1
```

Every single dot is a valid pattern.

There are `9` dots, so the answer is:

```python
9
```

For:

```python
m = 1
n = 2
```

All length `1` patterns are valid.

For length `2`, most pairs are valid, but some direct jumps are invalid.

Invalid length `2` moves include:

```text
1 -> 3
3 -> 1
1 -> 7
7 -> 1
3 -> 9
9 -> 3
7 -> 9
9 -> 7
1 -> 9
9 -> 1
3 -> 7
7 -> 3
2 -> 8
8 -> 2
4 -> 6
6 -> 4
```

Each of these crosses an unused middle dot.

So the answer for `m = 1, n = 2` is:

```python
65
```

## First Thought: Brute Force

A direct way is to generate every possible sequence of dots.

Since there are only `9` dots, the total number of sequences is limited.

For each sequence, we could check whether every move is valid.

This works, but it separates generation and validation. A cleaner method is to build only valid patterns from the start.

That leads to backtracking.

## Key Insight

At any point, the next dot is valid if:

```text
the dot has not been used
```

and either:

```text
the move does not cross a middle dot
```

or:

```text
the crossed middle dot has already been used
```

We can encode the crossing rule in a table.

Let `jump[a][b]` mean:

```text
the dot that must already be used before moving from a to b
```

If `jump[a][b] = 0`, then moving from `a` to `b` does not require any middle dot.

Important required middle dots:

| Move | Required dot |
|---|---|
| `1 <-> 3` | `2` |
| `1 <-> 7` | `4` |
| `3 <-> 9` | `6` |
| `7 <-> 9` | `8` |
| `1 <-> 9` | `5` |
| `3 <-> 7` | `5` |
| `2 <-> 8` | `5` |
| `4 <-> 6` | `5` |

All other moves either have no middle dot or pass through no numbered dot.

## Algorithm

Use DFS.

The DFS state contains:

| State | Meaning |
|---|---|
| `cur` | Current dot |
| `length` | Current pattern length |
| `used` | Which dots are already in the pattern |

At each DFS call:

1. Mark `cur` as used.
2. If `length >= m`, count the current pattern.
3. If `length == n`, stop extending.
4. Try every next dot from `1` to `9`.
5. A next dot is valid if it is unused and its required middle dot is either `0` or already used.
6. Recurse.
7. Unmark `cur` before returning.

We can also use symmetry.

The four corner dots are equivalent:

```text
1, 3, 7, 9
```

The four edge dots are equivalent:

```text
2, 4, 6, 8
```

The center dot is unique:

```text
5
```

So instead of starting DFS from all `9` dots, we compute:

```text
DFS from 1 * 4
DFS from 2 * 4
DFS from 5 * 1
```

## Correctness

The DFS only adds unused dots, so every counted pattern has distinct dots.

For each possible move from `cur` to `next_dot`, the algorithm checks the jump table.

If `jump[cur][next_dot] == 0`, the move has no required middle dot, so it is valid.

If `jump[cur][next_dot] != 0`, the move crosses a middle dot. The algorithm allows the move only when that middle dot has already been used. This matches the Android unlock rule exactly.

The DFS explores every valid continuation from each valid prefix. Since every valid pattern can be built one dot at a time while satisfying the same move rule, the DFS eventually reaches and counts every valid pattern whose length is between `m` and `n`.

The symmetry multiplication is valid because rotating or reflecting the grid maps corners to corners and edges to edges without changing the validity rules. Therefore all corner starts have the same count, and all edge starts have the same count.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(9!)` upper bound | DFS explores permutations of at most 9 dots |
| Space | `O(9)` | Recursion depth and used array are bounded by 9 |

The practical runtime is very small because the grid has only `9` dots.

## Implementation

```python
class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        jump = [[0] * 10 for _ in range(10)]

        jump[1][3] = jump[3][1] = 2
        jump[1][7] = jump[7][1] = 4
        jump[3][9] = jump[9][3] = 6
        jump[7][9] = jump[9][7] = 8

        jump[1][9] = jump[9][1] = 5
        jump[3][7] = jump[7][3] = 5
        jump[2][8] = jump[8][2] = 5
        jump[4][6] = jump[6][4] = 5

        used = [False] * 10

        def dfs(cur: int, length: int) -> int:
            used[cur] = True

            count = 1 if length >= m else 0

            if length < n:
                for nxt in range(1, 10):
                    required = jump[cur][nxt]

                    if used[nxt]:
                        continue

                    if required == 0 or used[required]:
                        count += dfs(nxt, length + 1)

            used[cur] = False
            return count

        total = 0
        total += dfs(1, 1) * 4
        total += dfs(2, 1) * 4
        total += dfs(5, 1)

        return total
```

## Code Explanation

We first build the `jump` table.

```python
jump = [[0] * 10 for _ in range(10)]
```

The table uses indices `1` through `9`, so size `10` keeps the indexing simple.

For example:

```python
jump[1][3] = jump[3][1] = 2
```

This means moving between `1` and `3` requires dot `2` to be used first.

The DFS marks the current dot:

```python
used[cur] = True
```

Then it counts the current pattern if its length is already within the allowed range:

```python
count = 1 if length >= m else 0
```

This is important because every prefix with length between `m` and `n` is a valid pattern by itself.

Then we try every possible next dot:

```python
for nxt in range(1, 10):
```

We skip used dots:

```python
if used[nxt]:
    continue
```

Then we check the jump rule:

```python
required = jump[cur][nxt]

if required == 0 or used[required]:
    count += dfs(nxt, length + 1)
```

If no middle dot is required, the move is valid.

If a middle dot is required, the move is valid only when that dot was already used.

Finally, we backtrack:

```python
used[cur] = False
```

This restores the state so other branches can use `cur` later.

The final answer uses symmetry:

```python
total += dfs(1, 1) * 4
total += dfs(2, 1) * 4
total += dfs(5, 1)
```

Dot `1` represents all four corners.

Dot `2` represents all four edge centers.

Dot `5` represents the center.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numberOfPatterns(1, 1) == 9
    assert s.numberOfPatterns(1, 2) == 65
    assert s.numberOfPatterns(2, 2) == 56
    assert s.numberOfPatterns(3, 3) == 320
    assert s.numberOfPatterns(1, 9) == 389497

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `m = 1, n = 1` | Every single dot is valid |
| `m = 1, n = 2` | Checks short patterns and invalid jumps |
| `m = 2, n = 2` | Counts only length `2` patterns |
| `m = 3, n = 3` | Known exact count for length `3` |
| `m = 1, n = 9` | Full range stress test |