Code Implementation

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        # skip[i][j] means the number between i and j must be visited before i->j is valid
        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] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5
        
        def dfs(visited, curr, remain):
            if remain == 0:
                return 1
            count = 0
            visited[curr] = True
            for nxt in range(1, 10):
                if not visited[nxt] and (skip[curr][nxt] == 0 or visited[skip[curr][nxt]]):
                    count += dfs(visited, nxt, remain - 1)
            visited[curr] = False
            return count

        res = 0
        visited = [False] * 10
        for l in range(m, n + 1):
            res += dfs(visited, 1, l - 1) * 4  # 1,3,7,9 are symmetric
            res += dfs(visited, 2, l - 1) * 4  # 2,4,6,8 are symmetric
            res += dfs(visited, 5, l - 1)      # 5 is unique
        return res
      

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        vector<vector<int>> skip(10, vector<int>(10, 0));
        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] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
        
        vector<bool> visited(10, false);

        function<int(int, int)> dfs = [&](int curr, int remain) {
            if (remain == 0) return 1;
            visited[curr] = true;
            int count = 0;
            for (int nxt = 1; nxt <= 9; ++nxt) {
                if (!visited[nxt] && (skip[curr][nxt] == 0 || visited[skip[curr][nxt]])) {
                    count += dfs(nxt, remain - 1);
                }
            }
            visited[curr] = false;
            return count;
        };

        int res = 0;
        for (int l = m; l <= n; ++l) {
            res += dfs(1, l - 1) * 4;
            res += dfs(2, l - 1) * 4;
            res += dfs(5, l - 1);
        }
        return res;
    }
};
      

public class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] skip = new int[10][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] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
        
        boolean[] visited = new boolean[10];
        int res = 0;
        for (int l = m; l <= n; l++) {
            res += dfs(visited, skip, 1, l - 1) * 4;
            res += dfs(visited, skip, 2, l - 1) * 4;
            res += dfs(visited, skip, 5, l - 1);
        }
        return res;
    }
    
    private int dfs(boolean[] visited, int[][] skip, int curr, int remain) {
        if (remain == 0) return 1;
        visited[curr] = true;
        int count = 0;
        for (int nxt = 1; nxt <= 9; nxt++) {
            if (!visited[nxt] && (skip[curr][nxt] == 0 || visited[skip[curr][nxt]])) {
                count += dfs(visited, skip, nxt, remain - 1);
            }
        }
        visited[curr] = false;
        return count;
    }
}
      

var numberOfPatterns = function(m, n) {
    const skip = Array.from({ length: 10 }, () => Array(10).fill(0));
    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] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;

    function dfs(visited, curr, remain) {
        if (remain === 0) return 1;
        visited[curr] = true;
        let count = 0;
        for (let nxt = 1; nxt <= 9; nxt++) {
            if (!visited[nxt] && (skip[curr][nxt] === 0 || visited[skip[curr][nxt]])) {
                count += dfs(visited, nxt, remain - 1);
            }
        }
        visited[curr] = false;
        return count;
    }

    let res = 0;
    for (let l = m; l <= n; l++) {
        let visited = Array(10).fill(false);
        res += dfs(visited, 1, l - 1) * 4;
        res += dfs(visited, 2, l - 1) * 4;
        res += dfs(visited, 5, l - 1);
    }
    return res;
};
      

Problem Description

The Android lock screen consists of a 3x3 grid of dots (numbered 1 to 9). A pattern is created by connecting dots with a finger, subject to certain rules:

• You can only move to an adjacent dot if it hasn't been used already in the pattern.
• If you move from one dot to another and the line passes through a third dot, you can only do so if that dot has already been visited.
• Each pattern must have at least m dots and at most n dots.
• Return the total number of valid unlock patterns for the given m and n.

Constraints:
1 <= m <= n <= 9

Thought Process

At first glance, the problem appears to be a permutation problem: how many ways can we select and order between m and n numbers from 1 to 9, without repetition? However, due to the "skip" rule (you can't jump over an unvisited dot), not all permutations are valid.

A brute-force solution would try every possible sequence of dots and check if it is valid, but this quickly becomes infeasible due to the number of possibilities and the complexity of the rules.

Instead, we look for symmetries and constraints that can help us optimize. Notably, the grid is symmetric—starting at any corner is equivalent, and so is starting at any edge. Also, we can precompute which moves are allowed or require a "skipped" dot to be visited first.

Recursion with backtracking is a natural fit, as we can build up patterns step-by-step, backtrack when we hit invalid moves, and count all valid patterns efficiently.

Solution Approach

• Step 1: Represent the Grid and Rules
  Model the 3x3 grid as numbers 1-9. For each pair of numbers, determine if there's a "skipped" dot between them that must be visited first. For example, to go from 1 to 3, you must have visited 2 if moving directly.
• Step 2: Precompute Skipped Dots
  Use a 2D array skip[i][j] to indicate which dot (if any) must be visited before moving from i to j.
• Step 3: Backtracking (DFS)
  Use a recursive DFS to try all possible patterns. At each step, mark the current dot as visited, then try to move to any unvisited dot, checking the skip condition. If a move is valid, recurse deeper.
• Step 4: Use Symmetry to Reduce Work
  Since the grid is symmetric, calculate the number of patterns starting from a corner, then multiply by 4 (for all corners), do the same for edges, and handle the center separately.
• Step 5: Aggregate Results
  For each pattern length from m to n, sum the counts from all possible starting points, applying symmetry multipliers.

Example Walkthrough

Let's consider m = 2 and n = 2 (all patterns of length 2).

1. Start at dot 1 (corner). Possible moves: 2, 4, 5, 6, 8 (since direct jumps to 3, 7, or 9 are blocked by the skip rule unless 2, 4, or 5 are already visited, which isn't the case at length 2).
2. For each possible move, record the pattern (e.g., 1-2, 1-4, etc.).
3. Repeat for starting dots 2 (edge), 5 (center), etc., applying the skip rules each time.
4. Multiply the results for corners and edges by their symmetry counts (4 each), and add the center's unique count.
5. The total is the sum of all valid 2-length patterns.

For example, from dot 1, 1-3 is invalid unless 2 is visited, which won't happen in a 2-length pattern. But 1-2 is valid. This logic is applied for all pairs.

Time and Space Complexity

• Brute-force: There are up to 9! permutations, which is 362,880. For each, we must check validity, making it infeasible.
• Optimized (Backtracking with Pruning): The number of recursive calls is much reduced, as invalid moves are pruned early. The total number of patterns is bounded (less than 9! total), and for each, we use O(1) extra space for the visited array.
• Time Complexity: O(9 × 8 × ... × (9 - n + 1)), but in practice much less due to pruning and symmetry.
• Space Complexity: O(9) for the visited array and skip matrix; recursion stack is at most depth 9.

Summary

The Android Unlock Patterns problem is a classic example of recursive backtracking with constraints. By precomputing which moves require a "skipped" dot and exploiting the symmetry of the grid, we efficiently count all valid patterns. The solution is elegant because it combines mathematical insight (symmetry) with algorithmic pruning (skip rules), allowing us to solve a seemingly complex combinatorial problem with concise code.