Android Unlock Patterns
Android devices feature a unique lock screen with a 3x3 grid of dots. Users can set an "unlock pattern" by connecting the dots in a specific sequence, forming line segments where each segment's endpoints are consecutive dots in the sequence.
A sequence of k dots is considered a valid unlock pattern if the following conditions are met:
- All dots in the sequence are distinct.
- If a line segment connecting two consecutive dots passes through the center of another dot, that dot must have already appeared in the sequence.
No skipping through non-selected dots is allowed. For example:
- Connecting dots 2 and 9 without having dots 5 or 6 in the sequence is valid because the line does not pass through the center of either of those dots.
- However, connecting dots 1 and 3 without dot 2 in the sequence is invalid because the line passes through the center of dot 2.
Here are some examples of valid and invalid unlock patterns:
- Invalid: [4, 1, 3, 6] because the line between 1 and 3 passes through dot 2, which was not in the sequence.
- Invalid: [4, 1, 9, 2] because the line between 1 and 9 passes through dot 5, which was not in the sequence.
- Valid: [2, 4, 1, 3, 6] because the line between 1 and 3 meets the condition with dot 2 having already appeared in the sequence.
- Valid: [6, 5, 4, 1, 9, 2] because the line between 1 and 9 meets the condition with dot 5 having already appeared in the sequence.
The goal is to return the number of unique and valid unlock patterns with at least m keys and at most n keys.
Two patterns are considered unique if there is a difference in the dots included in the sequence or the order in which they appear.
Example 1:
Input: m = 1, n = 1
Output: 9
Example 2:
Input: m = 1, n = 2
Output: 65
Constraints:
1 ≤ m, n ≤ 9
Summary
Android's unlock pattern system has become a popular method to protect smartphones from unauthorized access. In this article, we present an algorithm to compute the number of valid pattern combinations. This approach will introduce intermediate users to concepts such as backtracking and array manipulation.
Solution
Approach #1: (Backtracking)
Algorithm
The algorithm uses a backtracking technique to enumerate all possible combinations of numbers from 1 to 9, where the length of the pattern is between m and n.
During the recursive solution tree generation, the algorithm prunes branches that lead to invalid patterns, counting only those that satisfy the rules.
The process of generating a valid pattern follows these steps:
- Select a digit i that has not yet been used in the pattern. This is tracked with a "used" array to store available digits.
- Keep the last inserted digit last. The algorithm ensures that the most recently added digit stays at the end of the sequence.
- Check the validity of the current pattern based on the following conditions:
- Knight's move: If there is a knight's move (as in chess) from the last digit to i, or if i and the last digit are adjacent in a row or column, the sum of both digits should be odd.
- Middle element: If the line connecting the digits i and last passes through the center, the middle digit must have already been selected.
- Diagonal ends: If i and the last digit are positioned at the two ends of the diagonal, digit 5 must have been previously selected.
- Diagonal adjacency: If i and last are adjacent digits in a diagonal, this condition is also valid.
- Valid pattern generation: If any of the conditions above is satisfied, digit i becomes part of the current valid pattern, and the algorithm proceeds with the next available digit until the pattern is fully generated.
- Backtracking: If none of the conditions are satisfied, the algorithm rejects the current digit i, backtracks, and searches for other valid digits from the unused ones.
public class Solution {
private boolean used[] = new boolean[9];
public int numberOfPatterns(int m, int n) {
int res = 0;
for (int len = m; len <= n; len++) {
res += calcPatterns(-1, len);
for (int i = 0; i < 9; i++) {
used[i] = false;
}
}
return res;
}
private boolean isValid(int index, int last) {
if (used[index])
return false;
// first digit of the pattern
if (last == -1)
return true;
// knight moves or adjacent cells (in a row or in a column)
if ((index + last) % 2 == 1)
return true;
// indexes are at both end of the diagonals for example 0,0, and 8,8
int mid = (index + last) / 2;
if (mid == 4)
return used[mid];
// adjacent cells on diagonal - for example 0,0 and 1,0 or 2,0 and 1,1
if ((index % 3 != last % 3) && (index / 3 != last / 3)) {
return true;
}
// all other cells which are not adjacent
return used[mid];
}
private int calcPatterns(int last, int len) {
if (len == 0)
return 1;
int sum = 0;
for (int i = 0; i < 9; i++) {
if (isValid(i, last)) {
used[i] = true;
sum += calcPatterns(i, len - 1);
used[i] = false;
}
}
return sum;
}
}
Time and Space Complexity
Time Complexity: O(n!)
Space Complexity: O(n)
