LeetCode 351 - Android Unlock Patterns

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem models the Android lock screen as a 3 x 3 grid containing digits 1 through 9. A valid unlock pattern is a sequence of distinct dots that follows a special movement rule.

The first rule is straightforward: each dot can only be used once in a pattern. This means every pattern is effectively a permutation of unique digits.

The second rule is the core challenge of the problem. When moving from one dot to another, if the straight line between them passes through the center of another dot, then that intermediate dot must already have been visited earlier in the pattern.

For example:

Moving from 1 to 3 passes through 2, so 2 must already be selected.
Moving from 1 to 9 passes through 5, so 5 must already be selected.
Moving from 2 to 9 is allowed directly because the line does not pass through the center of another dot.

The input consists of two integers:

m, the minimum allowed pattern length
n, the maximum allowed pattern length

The goal is to count how many unique valid patterns have lengths between m and n, inclusive.

The constraints are very small:

1 <= m, n <= 9

Since there are only 9 dots total, the complete search space is finite and relatively small. However, blindly generating all possible permutations still creates unnecessary work because many sequences become invalid early. This suggests that pruning invalid paths during construction is the key to an efficient solution.

Several edge cases are important:

Patterns of length 1 are always valid because no movement occurs.
Transitions like 1 -> 3, 1 -> 7, 3 -> 9, and 7 -> 9 require intermediate nodes.
Diagonal transitions like 1 -> 9 and 3 -> 7 require 5.
Some moves appear diagonal but do not pass through another center, such as 2 -> 9, so they are valid immediately.
Since n <= 9, every pattern length is bounded by the number of available dots.

Approaches

Brute Force Approach

The brute force idea is to generate every possible permutation of the digits 1 through 9 for lengths between m and n. For each generated sequence, we would validate whether every consecutive move satisfies the Android lock constraints.

This approach is correct because it exhaustively checks every possible candidate pattern and counts only the valid ones.

However, it is inefficient because the number of permutations grows rapidly. Even though the total search space is manageable for 9 digits, validating every permutation wastes time exploring sequences that become invalid very early.

For example, once we generate [1, 3], we already know the pattern is invalid unless 2 was previously visited. Continuing to extend such invalid sequences is unnecessary.

Optimal Approach

The better approach uses backtracking with pruning.

Instead of generating full permutations first and validating afterward, we build patterns incrementally. At every step, we only choose moves that are immediately valid.

The key insight is that every restricted move can be represented using an intermediate required node.

For example:

1 -> 3 requires 2
1 -> 9 requires 5
4 -> 6 requires 5

We can precompute these relationships in a skip matrix:

skip[a][b] = x means moving from a to b requires x to already be visited
skip[a][b] = 0 means no intermediate node is required

Then we perform DFS with backtracking:

Track visited nodes
Try every next valid move
Count patterns whose lengths fall between m and n

An additional optimization comes from symmetry:

1, 3, 7, 9 are symmetric
2, 4, 6, 8 are symmetric
5 is unique

So instead of computing all starting positions separately:

Compute patterns starting from 1 and multiply by 4
Compute patterns starting from 2 and multiply by 4
Compute patterns starting from 5 once

This significantly reduces repeated computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(9!)	O(9)	Generates permutations and validates afterward
Optimal	O(9!) worst case, much smaller in practice	O(9)	Uses DFS with pruning and symmetry optimization

Algorithm Walkthrough

Create a skip matrix of size 10 x 10.

The grid uses digits 1 through 9, so index 0 is unused for convenience.

Each entry stores the intermediate node required for a move.

For example:

skip[1][3] = 2
skip[1][9] = 5
skip[7][9] = 8

If no intermediate node is required, the value remains 0. 2. Create a visited array.

This tracks which dots have already been included in the current pattern.

Since dots cannot repeat, this structure is essential for enforcing uniqueness. 3. Define a DFS function.

The DFS function takes:

current, the current node
remaining, how many more nodes must be added

The function returns the number of valid patterns that can be formed from this state. 4. Handle the base case.

If remaining == 0, then a complete valid pattern has been constructed.

Return 1. 5. Mark the current node as visited.

This prevents revisiting the same node later in the recursion path. 6. Try every possible next node from 1 to 9.

For each candidate node:

Skip it if already visited.
Otherwise check movement validity.

A move is valid if:

No intermediate node is required, or
The required intermediate node has already been visited

This condition is checked using:

skip[current][next_node] == 0
or visited[skip[current][next_node]]

Recursively explore valid moves.

For every valid next node:

Recurse with remaining - 1

Accumulate the returned counts. 8. Backtrack.

Before returning, unmark the current node as visited.

This restores the state for other recursive branches. 9. Use symmetry optimization.

Instead of starting DFS from all 9 nodes individually:

Compute one corner result and multiply by 4
Compute one edge result and multiply by 4
Compute center result once

Sum results for all lengths from m to n.

For each valid length:

Count all patterns of that exact size
Add them to the final answer

Why it works

The algorithm explores every valid unlock pattern exactly once. The visited array guarantees no repeated nodes, while the skip matrix guarantees every move satisfies the Android lock constraints. Backtracking systematically enumerates all valid sequences, and symmetry multiplication preserves correctness because symmetric starting positions produce identical counts.

Python Solution

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

        visited = [False] * 10

        def dfs(current: int, remaining: int) -> int:
            if remaining == 0:
                return 1

            visited[current] = True
            patterns = 0

            for next_node in range(1, 10):
                intermediate = skip[current][next_node]

                if not visited[next_node]:
                    if intermediate == 0 or visited[intermediate]:
                        patterns += dfs(next_node, remaining - 1)

            visited[current] = False
            return patterns

        total_patterns = 0

        for length in range(m, n + 1):
            total_patterns += dfs(1, length - 1) * 4
            total_patterns += dfs(2, length - 1) * 4
            total_patterns += dfs(5, length - 1)

        return total_patterns

The implementation begins by constructing the skip matrix. This matrix encodes all movements that require an intermediate node. Every invalid direct jump can therefore be checked in constant time during DFS.

The visited array tracks which nodes are already part of the current pattern. Since unlock patterns cannot reuse dots, this array is critical for correctness.

The recursive dfs function explores all valid continuations from the current node. The parameter remaining indicates how many more nodes still need to be selected. When this value reaches zero, a complete valid pattern has been formed.

Inside the DFS loop, every candidate next node is tested. The move is legal if either:

no intermediate node exists, or
the required intermediate node has already been visited

After recursion finishes, the current node is unmarked. This is the backtracking step that restores the state for future recursive branches.

Finally, symmetry optimization reduces redundant computation. Since the four corners behave identically and the four edge centers behave identically, only three DFS computations are needed per pattern length.

Go Solution

func numberOfPatterns(m int, n int) int {
	skip := make([][]int, 10)
	for i := 0; i < 10; i++ {
		skip[i] = make([]int, 10)
	}

	skip[1][3], skip[3][1] = 2, 2
	skip[1][7], skip[7][1] = 4, 4
	skip[3][9], skip[9][3] = 6, 6
	skip[7][9], skip[9][7] = 8, 8

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

	visited := make([]bool, 10)

	var dfs func(int, int) int

	dfs = func(current int, remaining int) int {
		if remaining == 0 {
			return 1
		}

		visited[current] = true
		patterns := 0

		for nextNode := 1; nextNode <= 9; nextNode++ {
			intermediate := skip[current][nextNode]

			if !visited[nextNode] {
				if intermediate == 0 || visited[intermediate] {
					patterns += dfs(nextNode, remaining-1)
				}
			}
		}

		visited[current] = false
		return patterns
	}

	totalPatterns := 0

	for length := m; length <= n; length++ {
		totalPatterns += dfs(1, length-1) * 4
		totalPatterns += dfs(2, length-1) * 4
		totalPatterns += dfs(5, length-1)
	}

	return totalPatterns
}

The Go implementation follows the same structure as the Python solution. The main difference is that slices are used instead of Python lists.

The DFS function is implemented as a closure so it can access the shared visited and skip structures without additional parameters.

Since the maximum possible count easily fits within Go's int range, no special overflow handling is required.

Worked Examples

Example 1

Input: m = 1, n = 1

We only count patterns of length 1.

The algorithm computes:

Starting Group	Count
Corner nodes `(1,3,7,9)`	1 each
Edge nodes `(2,4,6,8)`	1 each
Center node `(5)`	1

Calculation:

Expression	Value
`dfs(1,0) * 4`	`1 * 4 = 4`
`dfs(2,0) * 4`	`1 * 4 = 4`
`dfs(5,0)`	`1`

Final answer:

4 + 4 + 1 = 9

Output:

Example 2

Input: m = 1, n = 2

We count all patterns of lengths 1 and 2.

Length 1 contributes:

Now consider length 2.

Starting from Corner Node `1`

Possible valid next moves:

Move	Valid?	Reason
`1 -> 2`	Yes	No intermediate
`1 -> 3`	No	Requires `2`
`1 -> 4`	Yes	No intermediate
`1 -> 5`	Yes	No intermediate
`1 -> 6`	Yes	No intermediate
`1 -> 7`	No	Requires `4`
`1 -> 8`	Yes	No intermediate
`1 -> 9`	No	Requires `5`

Total valid moves from 1:

Since all corners are symmetric:

5 * 4 = 20

Starting from Edge Node `2`

Valid moves:

Move	Valid?
`2 -> 1`	Yes
`2 -> 3`	Yes
`2 -> 4`	Yes
`2 -> 5`	Yes
`2 -> 6`	Yes
`2 -> 7`	Yes
`2 -> 8`	No
`2 -> 9`	Yes

Total:

All edge centers are symmetric:

7 * 4 = 28

Starting from Center Node `5`

Every move is valid.

Total:

Final Count

Length	Count
1	9
2	56

Total:

9 + 56 = 65

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(9!)	In the worst case, DFS explores permutations of 9 nodes
Space	O(9)	Recursion depth and visited array are bounded by 9

Although the theoretical upper bound is factorial, the actual runtime is much smaller because invalid moves are pruned immediately. The search space is heavily reduced by the movement constraints and symmetry optimization.

The space complexity remains constant relative to input size because the grid always contains exactly 9 nodes.

Test Cases

solution = Solution()

assert solution.numberOfPatterns(1, 1) == 9      # Single-node patterns
assert solution.numberOfPatterns(1, 2) == 65     # Example from problem statement
assert solution.numberOfPatterns(2, 2) == 56     # Only length-2 patterns
assert solution.numberOfPatterns(3, 3) == 320    # Standard known value
assert solution.numberOfPatterns(4, 4) == 1624   # Medium-length patterns
assert solution.numberOfPatterns(1, 9) == 389112 # All possible valid patterns

assert solution.numberOfPatterns(9, 9) == 140704 # Maximum pattern length
assert solution.numberOfPatterns(8, 9) > 0       # Large pattern lengths
assert solution.numberOfPatterns(5, 7) > 0       # Mid-range lengths

# Symmetry-related validation
assert solution.numberOfPatterns(2, 2) % 4 == 0  # Symmetric groups contribute evenly

Test	Why
`m=1, n=1`	Validates simplest base case
`m=1, n=2`	Confirms official example
`m=2, n=2`	Ensures exact-length counting works
`m=3, n=3`	Tests deeper DFS recursion
`m=4, n=4`	Verifies medium complexity patterns
`m=1, n=9`	Tests complete search space
`m=9, n=9`	Tests maximum recursion depth
`m=8, n=9`	Ensures large patterns are counted correctly
`m=5, n=7`	Validates multiple-length accumulation
Symmetry divisibility test	Confirms symmetry optimization consistency

Edge Cases

One important edge case is patterns of length 1. In this situation, no movement occurs, so every node independently forms a valid pattern. A buggy implementation might incorrectly require movement validation even when no transitions exist. The implementation handles this correctly because the DFS immediately returns 1 when remaining == 0.

Another critical edge case involves restricted jumps such as 1 -> 3 or 1 -> 9. These moves are only valid if the intermediate node has already been visited. Without properly checking the skip matrix, the algorithm would overcount invalid patterns. The implementation explicitly validates the intermediate node before allowing recursion.

A third important edge case occurs near maximum recursion depth, especially for m = 9 and n = 9. In this scenario, every node must appear exactly once. Recursive implementations that fail to backtrack correctly may accidentally keep nodes permanently marked as visited, causing missing counts. The solution avoids this problem by always unmarking the current node before returning from DFS.

Another subtle case involves moves that appear diagonal but do not cross a node center, such as 2 -> 9. Some naive geometric implementations incorrectly reject these moves. The skip matrix avoids this mistake because only truly restricted moves are encoded. Any pair not listed in the matrix is treated as immediately valid.

LeetCode 351 - Android Unlock Patterns

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Starting from Corner Node 1

Starting from Edge Node 2

Starting from Center Node 5

Final Count

Complexity Analysis

Test Cases

Edge Cases

Starting from Corner Node `1`

Starting from Edge Node `2`

Starting from Center Node `5`