Problem summary
Given the 3×3 Android lock screen grid numbered like this:
1 2 3 4 5 6 7 8 9
A pattern is a sequence of distinct keys (no repeats) where each move from key a to key b must follow this rule:
- If the straight line between a and b passes through another key c, then c must have been already used in the pattern; otherwise the move is invalid.
- If the straight line does not pass through any other key, the move is always valid.
- Examples of invalid moves at the start: 1 -> 3 (passes through 2) unless 2 was already used; 1 -> 9 (passes through 5) unless 5 used.
Given integers m and n (1 ≤ m ≤ n ≤ 9), return the number of valid unlock patterns with length between m and n inclusive.
Approach in simple English
We need to count all valid sequences (permutations without repetition) of lengths from m to n that follow the straight-line rule.
Brute force idea
- Generate all permutations and test validity; this is possible because there are at most 9! = 362880 permutations, but we can do far better using backtracking with constraints checked incrementally.
Efficient approach (backtracking with skip checks and symmetry)
- Precompute a skip matrix skip[a][b] which gives the intermediate key that lies exactly between a and b when such a key exists; otherwise skip[a][b] = 0. For example:
- 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[4][6] = skip[6][4] = 5
- skip[7][9] = skip[9][7] = 8
- and so on
- Use DFS/backtracking from a chosen starting key, tracking visited keys and remaining length to build.
- From current key curr, you may go to next if next has not been visited AND (skip[curr][next] == 0 OR visited[ skip[curr][next] ] is true).
- To avoid repeating symmetric work, exploit board symmetry:
- Keys 1, 3, 7, 9 (corners) are symmetric — they produce the same count of patterns when used as starting points.
- Keys 2, 4, 6, 8 (edges) are symmetric.
- Key 5 (center) is unique.
- So compute:
- patterns starting from 1 (corner) and multiply by 4
- patterns starting from 2 (edge) and multiply by 4
- patterns starting from 5 (center) multiply by 1
- This reduces DFS calls substantially.
- For each start key, run DFS for every length L from 1 to n (or better: DFS that counts all completions for remaining lengths and we accumulate only lengths within [m, n]).
Implementation outline
- Build skip matrix.
- For each representative start (1, 2, 5) run DFS and scale using symmetry multipliers.
- DFS signature: dfs(curr, remain, visited, skip)
- If remain == 0, return 1 (a valid pattern of the required remaining length is formed).
- Sum over all next in 1..9 that satisfy rules; mark visited next, recurse with remain-1, then unmark visited.
We sum answers for all lengths L between m and n by calling dfs with remain = L-1 after marking the starting key visited (because starting key consumes one position).
Java code (clean, production-ready)
public class Solution {
// skip[a][b] = the key that lies between a and b when moving in a straight line,
// or 0 if no such intermediate key exists.
private int[][] skip = new int[10][10];
public int numberOfPatterns(int m, int n) {
// fill skip matrix
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;
// other entries remain 0
boolean[] visited = new boolean[10]; // index 1..9 used
int total = 0;
// corners: 1,3,7,9 are symmetric
for (int len = m; len <= n; len++) {
int cornerCount = dfs(1, len - 1, visited); // patterns starting at 1 with remain = len-1
int edgeCount = dfs(2, len - 1, visited); // starting at 2
int centerCount = dfs(5, len - 1, visited); // starting at 5
total += cornerCount * 4;
total += edgeCount * 4;
total += centerCount;
}
return total;
}
// dfs(curr, remain, visited)
// curr: current key (1..9)
// remain: how many more keys to add (0 means current pattern length is the target length)
// visited: boolean array marking used keys
private int dfs(int curr, int remain, boolean[] visited) {
if (remain == 0) return 1;
visited[curr] = true;
int sum = 0;
for (int next = 1; next <= 9; next++) {
if (!visited[next]) {
int mid = skip[curr][next];
// move allowed if there is no middle key, or the middle key was already visited
if (mid == 0 || visited[mid]) {
sum += dfs(next, remain - 1, visited);
}
}
}
visited[curr] = false;
return sum;
}
// simple main for quick check
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.numberOfPatterns(1, 1)); // expect 9 (each single key)
System.out.println(s.numberOfPatterns(1, 2)); // common test
}
}
Dry run (short, for clarity)
Case m = 1, n = 1
- We count all patterns of length 1: each key alone is valid, so answer = 9.
- Code behavior:
- For len = 1, remain = 0.
- dfs(1,0) returns 1, dfs(2,0) returns 1, dfs(5,0) returns 1.
- total = cornerCount4 + edgeCount4 + centerCount = 14 + 14 + 1 = 9.
Case m = 1, n = 2
- Patterns of length 1: 9
- Patterns of length 2: count all valid pairs where second key is distinct and obeys skip rule (e.g., 1->3 is invalid unless 2 already used, so invalid for length 2). The code enumerates all such pairs via DFS.
- The code loops len=1 and len=2, sums counts. The DFS enforces skip rules, so only valid transitions are counted.
If you want values for specific inputs (for example m = 1, n = 2 or m = 4, n = 9), I can run through calculations for those exact cases or provide a small table.
Complexity
- Time complexity: roughly O(9! / (9 – L)!) summed over lengths L from m to n — in practice the symmetry optimization and the skip pruning reduce work significantly. Upper bound is O(9!) if you enumerated all permutations, but actual runtime is much smaller and easily acceptable for constraints (m,n up to 9).
- Space complexity: O(9) for the visited array and recursion depth.
Edge cases and notes
- m and n satisfy 1 ≤ m ≤ n ≤ 9 per problem statement. If input violates this, validate and handle appropriately.
- The skip matrix must be symmetric and correctly filled; mistakes there produce wrong counts.
- Using symmetry (corner4, edge4, center) drastically reduces DFS calls — the implementation shown uses that symmetry to speed up counting.