Android Unlock Patterns

XXX. Android Lock Pattern

DFS

Backtracking

Problem Statement:

Calculate the number of possible Android unlock patterns of length between m and n, where dots must be connected following specific rules.

• Pattern must be of length m to n
• Must pass through middle point to connect opposite corners
• Cannot skip over unvisited points

Implementation:

public class Solution {
    public int numberOfPatterns(int m, int n) {
        // Skip array represents the number that must be visited
        // to go from index i to index j
        int[][] skip = new int[10][10];
        
        // Initialize skip array with required points
        skip[1][3] = skip[3][1] = 2;            // Horizontal skips
        skip[1][7] = skip[7][1] = 4;            // Vertical skips
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        // Diagonal skips
        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];      // Track visited numbers
        int count = 0;
        
        // Try all pattern lengths from m to n
        for (int i = m; i <= n; i++) {
            // Multiply by 4 due to symmetry:
            // 2,4,6,8 are symmetric
            count += dfs(2, visited, i - 1, skip) * 4;  
            // 1,3,7,9 are symmetric
            count += dfs(1, visited, i - 1, skip) * 4;  
            // 5 is unique
            count += dfs(5, visited, i - 1, skip);      
        }
        
        return count;
    }
    
    private int dfs(int num, boolean[] visited, int remain, int[][] skip) {
        // Base case: no more numbers needed
        if (remain == 0) return 1;
        
        visited[num] = true;           // Mark current number as visited
        int count = 0;
        
        // Try all possible next numbers
        for (int i = 1; i <= 9; i++) {
            // Can visit if:
            // 1. Number not visited
            // 2. No skip number exists OR skip number is visited
            if (!visited[i] && (skip[num][i] == 0 || visited[skip[num][i]])) {
                count += dfs(i, visited, remain - 1, skip);
            }
        }
        
        visited[num] = false;          // Restore state for backtracking
        return count;
    }
}

Python Solution:

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        # Initialize skip matrix
        skip = [[0] * 10 for _ in range(10)]
        
        # Set up horizontal and vertical skips
        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
        
        # Set up diagonal skips all through center (5)
        diagonals = [(1,9), (2,8), (3,7), (4,6)]
        for i, j in diagonals:
            skip[i][j] = skip[j][i] = 5
        
        def dfs(num: int, visited: set, remain: int) -> int:
            if remain == 0:
                return 1
                
            count = 0
            visited.add(num)
            
            for next_num in range(1, 10):
                if (next_num not in visited and 
                    (skip[num][next_num] == 0 or 
                     skip[num][next_num] in visited)):
                    count += dfs(next_num, visited, remain - 1)
                    
            visited.remove(num)
            return count
        
        count = 0
        visited = set()
        
        # Calculate patterns for each length
        for i in range(m, n + 1):
            count += dfs(2, visited, i - 1) * 4  # 2,4,6,8
            count += dfs(1, visited, i - 1) * 4  # 1,3,7,9
            count += dfs(5, visited, i - 1)      # center
            
        return count

C++ Solution:

class Solution {
private:
    int dfs(int num, vector& visited, int remain, 
            vector>& skip) {
        if (remain == 0) return 1;
        
        visited[num] = true;
        int count = 0;
        
        for (int i = 1; i <= 9; i++) {
            if (!visited[i] && 
                (skip[num][i] == 0 || visited[skip[num][i]])) {
                count += dfs(i, visited, remain - 1, skip);
            }
        }
        
        visited[num] = false;
        return count;
    }
    
public:
    int numberOfPatterns(int m, int n) {
        vector> skip(10, vector(10, 0));
        
        // Initialize skip array
        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;
        
        // Diagonal skips through center
        const vector> diagonals = {
            {1,9}, {2,8}, {3,7}, {4,6}
        };
        for (const auto& [i, j] : diagonals) {
            skip[i][j] = skip[j][i] = 5;
        }
        
        vector visited(10, false);
        int count = 0;
        
        for (int i = m; i <= n; i++) {
            count += dfs(2, visited, i - 1, skip) * 4;  // Corners
            count += dfs(1, visited, i - 1, skip) * 4;  // Edges
            count += dfs(5, visited, i - 1, skip);      // Center
        }
        
        return count;
    }
};

Complexity:

Time Complexity: O(n!), as we try all possible combinations
Space Complexity: O(n) for recursion stack

Key Points:

• **Skip Array**:
  • Tracks required points between two positions
  • Handles both straight and diagonal lines
  • Zero means direct connection possible
• **Pattern Symmetry**:
  • Corner numbers (1,3,7,9) are symmetric
  • Edge numbers (2,4,6,8) are symmetric
  • Center (5) is unique