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, which must meet the following conditions:

  1. All of the dots must be distinct.
  2. If the line segment connecting two consecutive dots in the pattern passes through the center of any other dot, the other dot must have previously appeared in the pattern. (No jumps through unvisited dots, except the center dot which can be jumped over if already visited.)
  3. The dots in the pattern must all be connected.

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

Two unlock patterns are considered different if the two sequences of dots are different.

Thinking Process

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, which must meet the following conditions:

  1. All of the dots must be distinct.
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Examples

Example 1:

Input: m = 1, n = 1
Output: 9
Explanation: There are 9 patterns of length 1 (each dot individually).

Example 2:

Input: m = 1, n = 2
Output: 65
Explanation: There are 9 patterns of length 1 + 56 patterns of length 2.

Grid Layout

The 3×3 grid is numbered as follows:

0  1  2
3  4  5
6  7  8

Constraints

  • 1 <= m <= n <= 9

Algorithm Breakdown

Grid Representation

The 3×3 grid is represented as a 1D array:

0  1  2     → indices 0, 1, 2
3  4  5     → indices 3, 4, 5
6  7  8     → indices 6, 7, 8

Coordinates:

  • Row: idx / 3
  • Column: idx % 3

Validation Cases

  1. Adjacent Dots: (idx + last) % 2 == 1
    • Examples: 0→1, 1→2, 0→3, 3→6
    • Always valid (no middle dot)
  2. Through Center: mid == 4
    • Examples: 0→8, 2→6, 1→7, 3→5
    • Valid only if center (4) is visited
  3. Same Row: idx / 3 == last / 3 and idx % 3 != last % 3
    • Examples: 0→2, 3→5, 6→8
    • Valid only if middle dot is visited
  4. Same Column: idx % 3 == last % 3 and idx / 3 != last / 3
    • Examples: 0→6, 1→7, 2→8
    • Valid only if middle dot is visited
  5. Diagonal: Different row and column
    • Examples: 1→3, 1→5, 3→1, 5→1
    • Always valid (no middle dot)

Why (idx + last) % 2 == 1 Works

This formula identifies adjacent dots in the grid:

  • Adjacent horizontally: 0→1 (0+1=1), 1→2 (1+2=3)
  • Adjacent vertically: 0→3 (0+3=3), 3→6 (3+6=9)
  • Sum is odd → adjacent
  • Sum is even → may need to check middle

Time & Space Complexity

  • Time Complexity:
    • Worst case: O(9!) for length 9 patterns
    • For length m to n: Sum of permutations P(9,k) for k from m to n
    • Practical: Much better due to validation pruning
  • Space Complexity: O(9) for used array and recursion stack

Key Points

  1. Backtracking: Explore all valid patterns recursively
  2. Validation: Complex logic to handle jump-over rule
  3. Symmetry: Could optimize by using symmetry (1,3,7,9 are symmetric; 2,4,6,8 are symmetric)
  4. Pruning: Validation function prunes invalid paths early
  5. Reset: Clear used array for each length to avoid interference

Optimization Opportunities

Symmetry Optimization

Since the grid is symmetric, we can count patterns starting from symmetric positions once and multiply:

class Solution:
    def numberOfPatterns(self, m, n):
        self.used = [False] * 9
        self.rtn = 0

        for length in range(m, n + 1):
            self.rtn += self.claPatterns(-1, length)

        return self.rtn

    def isValid(self, idx, last):
        if self.used[idx]:
            return False

        if last == -1:
            return True

        # middle point between last and idx
        mid = (idx + last) // 2

        # if move is not a straight line skip middle check
        if (idx + last) % 2 == 1:
            return True

        # special center case
        if mid == 4:
            return not self.used[mid]

        # same row or same column check
        if (idx % 3 != last % 3) and (idx // 3 != last // 3):
            return True

        return not self.used[mid]

    def claPatterns(self, last, length):
        if length == 0:
            return 1

        total = 0

        for i in range(9):
            if self.isValid(i, last):
                self.used[i] = True
                total += self.claPatterns(i, length - 1)
                self.used[i] = False

        return total

This reduces computation by ~4x for corners and edges.

Edge Cases

  1. m = n = 1: Return 9 (each dot individually)
  2. m = n = 9: Return number of Hamiltonian paths
  3. m = 1, n = 9: Return all possible patterns
  4. Single length: Patterns of exactly length m

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Backtracking, Recursion, Dynamic Programming, Medium

Key Takeaways

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.

References

Template Reference