Problem

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

  1. Each pattern must connect at least m keys and at most n keys.
  2. All the keys must be distinct.
  3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
  4. The order of keys used matters.

Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6 Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2 Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6 Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Examples

Example 1

Input: m = 1, n = 1
Output: 9

Solution

Method 1 - Using DFS

To solve this problem, we can use a depth-first search (DFS) approach to explore all possible patterns on the Android lock screen while adhering to the rules for a valid pattern. To efficiently manage the paths and avoid invalid jumps, we’ll use a skip array to keep track of intermediate keys that must be passed through.

Steps

Here are the steps:

  1. Grid and Skip Array Setup:
    • Represent the 3x3 grid as numbers 1 to 9.
    • Use a skip array where skip[i][j] indicates the key that must be passed through when moving from i to j.
  2. DFS Traversal:
    • Implement DFS to explore all possible patterns starting from each key.
    • Use a visited array to ensure each key is visited only once in a given pattern.
    • Track patterns of length from m to n.
  3. Count Valid Patterns:
    • Increment the count when the current pattern length is between m and n.

Skip Array

The skip array keeps track of mandatory intermediate keys for each pair.

skip[1][3] = skip[3][1] = 2;  // Key 2 is between keys 1 and 3 in a straight line
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;  // Key 5 is between keys 1 and 9 in a diagonal
skip[3][7] = skip[7][3] = 5;
skip[4][6] = skip[6][4] = 5;
skip[2][8] = skip[8][2] = 5;

Code

Java
class Solution {
	public int numberOfPatterns(int m, int n) {
		boolean[] visited = new boolean[10];
		int[][] skip = new int[10][10];

		// Fill the skip array
		// 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;
		// Diagonal skips
		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;

		int totalPatterns = 0;

		for (int i = 1; i <= 9; i++) {
			totalPatterns += dfs(i, 1, m, n, visited, skip);
		}

		return totalPatterns;
	}

	private int dfs(int current, int length, int m, int n, boolean[] visited, int[][] skip) {
		if (length > n) {
			return 0;
		}

		if (length >= m) {
			totalPatterns++;
		}

		visited[current] = true;
		int count = 0;

		for (int next = 1; next <= 9; next++) {
			int currentSkipped = skip[current][next];
			if (!visited[next] && (currentSkipped == 0 || visited[currentSkipped])) {
				count += dfs(next, length + 1, m, n, visited, skip);
			}
		}

		visited[current] = false;
		return count;
	}
}
Python
def numberOfPatterns(m: int, n: int) -> int:
    def is_valid_move(used, i, j, skip):
        # Returns True if moving from i to j satisfies the skipping constraint
        return used[j] or (skip[i][j] == 0 or used[skip[i][j]])

    def dfs(used, skip, curr, remain):
        if remain < 0:
            return 0
        if remain == 0:
            return 1
        used[curr] = True
        res = 0
        for i in range(1, 10):
            if not used[i] and is_valid_move(used, curr, i, skip):
                res += dfs(used, skip, i, remain - 1)
        used[curr] = False
        return res

    # Initialize the intermediate skip array
    skip = [[0] * 10 for _ in range(10)]
    skip[1][3] = skip[3][1] = 2
    skip[1][7] = skip[7][1] = 4
    skip[1][9] = skip[9][1] = 5
    skip[2][8] = skip[8][2] = 5
    skip[3][7] = skip[7][3] = 5
    skip[3][9] = skip[9][3] = 6
    skip[4][6] = skip[6][4] = 5
    skip[7][9] = skip[9][7] = 8

    used = [False] * 10
    total_count = 0

    # Run DFS for each starting point 1-9
    for length in range(m, n + 1):
        total_count += dfs(used, skip, 1, length - 1) * 4
        total_count += dfs(used, skip, 2, length - 1) * 4
        total_count += dfs(used, skip, 5, length - 1)

    return total_count

Complexity

  • ⏰ Time complexity: O(9^n) - as at each step, time complexity can be modeled as a tree where each node has at most 9 children
  • 🧺 Space complexity: O(n) assuming recursion stack