LeetCode 351: Android Unlock Patterns

A clear explanation of Android Unlock Patterns using backtracking, a jump table, and symmetry optimization.

leetcodebacktrackingdfsmatrixandroid-unlock-patterns

Problem Restatement

We have a 3 x 3 Android lock screen.

The dots are numbered like this:

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:

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

Examples

For:

m = 1
n = 1

Every single dot is a valid pattern.

There are 9 dots, so the answer is:

9

For:

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:

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:

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:

the dot has not been used

and either:

the move does not cross a middle dot

or:

the crossed middle dot has already been used

We can encode the crossing rule in a table.

Let jump[a][b] mean:

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:

1, 3, 7, 9

The four edge dots are equivalent:

2, 4, 6, 8

The center dot is unique:

5

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

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

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.

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

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

For example:

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:

used[cur] = True

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

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:

for nxt in range(1, 10):

We skip used dots:

if used[nxt]:
    continue

Then we check the jump rule:

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:

used[cur] = False

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

The final answer uses symmetry:

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

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