Android Unlock Patterns solution and explanation
Google
9 more videos on this problem
LeetCode 351. Android Unlock PatternsHappy Coding · 25:34 · 6K views
Number of Unlock patterns | Android Unlock PatternsKnowledge Center · 28:02 · 5K views
351. Android Unlock Patterns | English | MediumSimple Code - 단순코드 · 10:51 · 2K views
Leetcode 351. Android Unlock Patterns. 详细解析Alina L · 19:03 · 2K views
351. Android Unlock Patterns - Week 2/5 Leetcode August ChallengeProgramming Live with Larry · 38:53 · 649 views
Android Unlock Patterns | Leetcode #351Surjit Singh · 9:39 · 508 views
LeetCode 351 Java -- BacktrackingHow we live in Texas · 5:37 · 182 views
351. Android Unlock Patterns | Korean | MediumSimple Code - 단순코드 · 11:48 · 89 views
Android Unlock Patterns | DFS, Skip Matrix | Crack FAANG/MAANG InterviewsCore Bytes · 10:02 · 23 views
Leetcode 351. Android Unlock Patterns in Python | Python Leetcode | Python Coding Tutorial | ASMRCode is Art · 3:45 · 8 views
The problem
Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an "unlock pattern" by connecting the dots in a specific sequence, forming a series of joined line segments where each segment's endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true:
- All the dots in the sequence are distinct.
- If the line segment connecting two consecutive dots in the sequence passes through the center of any other dot, the other dot must have previously appeared in the sequence. No jumps through the center non-selected dots are allowed.
- For example, connecting dots
2and9without dots5or6appearing beforehand is valid because the line from dot2to dot9does not pass through the center of either dot5or6. - However, connecting dots
1and3without dot2appearing beforehand is invalid because the line from dot1to dot3passes through the center of dot2.
- For example, connecting dots
Here are some example valid and invalid unlock patterns:
- The 1st pattern
[4,1,3,6]is invalid because the line connecting dots1and3pass through dot2, but dot2did not previously appear in the sequence. - The 2nd pattern
[4,1,9,2]is invalid because the line connecting dots1and9pass through dot5, but dot5did not previously appear in the sequence. - The 3rd pattern
[2,4,1,3,6]is valid because it follows the conditions. The line connecting dots1and3meets the condition because dot2previously appeared in the sequence. - The 4th pattern
[6,5,4,1,9,2]is valid because it follows the conditions. The line connecting dots1and9meets the condition because dot5previously appeared in the sequence.
Given two integers m and n, return the number of unique and valid unlock patterns of the Android grid lock screen that consist of at least m keys and at most n keys.
Two unlock patterns are considered unique if there is a dot in one sequence that is not in the other, or the order of the dots is different.
Example 1:
Input: m = 1, n = 1 Output: 9
Example 2:
Input: m = 1, n = 2 Output: 65
Constraints:
1 <= m, n <= 9
Approach overview
Problem Overview: Count how many valid unlock patterns can be formed on the Android 3x3 lock screen using lengths between m and n. A pattern cannot revisit a key, and moves that jump over another key are only allowed if that intermediate key has already been used.
Approach 1: Brute Force Backtracking (O(9!))
The straightforward strategy generates every possible path on the 3×3 grid using depth‑first search. Start from each digit (1–9), mark it visited, and recursively try the remaining digits while respecting the Android rule: if a move crosses another key (for example 1 → 3 crossing 2), that intermediate key must already be visited. A small lookup table called skip stores these required intermediate nodes. The search continues until the path length reaches n, counting patterns whose length is at least m. Time complexity is O(9!) in the worst case because permutations of keys are explored, and space complexity is O(9) for the recursion stack and visited array.
Approach 2: Symmetry Optimized Backtracking (O(9!))
The grid has strong symmetry. Corners (1,3,7,9) behave the same, edges (2,4,6,8) behave the same, and the center (5) is unique. Instead of running DFS from all nine digits, run it once from a representative of each group and multiply the result. For example, compute patterns starting from 1 and multiply by four for the corners. Do the same for 2 multiplied by four for edges, and handle 5 once. The same skip matrix enforces the rule about crossing intermediate keys. This reduces redundant exploration while keeping the same theoretical complexity O(9!), with space O(9). This approach is what most production solutions use because it cuts the constant factor dramatically.
Approach 3: Bitmask + DP State Exploration (O(9 * 2^9))
A more algorithmic perspective models the problem as state transitions. Each state is defined by the current key and a bitmask representing visited keys. From a state (node, mask), iterate over all possible next digits and check whether the move is valid using the same intermediate-key rule. Memoizing results for identical states avoids recomputation. The number of states is bounded by 9 * 2^9, giving time complexity around O(9 * 2^9) and space complexity O(9 * 2^9). This version connects naturally to dynamic programming and bitmask techniques.
Recommended for interviews: Symmetry‑optimized backtracking is the expected solution. It demonstrates control of DFS, constraint handling, and pruning using problem structure. Interviewers like seeing the skip matrix plus the symmetry observation because it reduces work from nine starting searches to three. Mentioning the bitmask state idea also shows familiarity with backtracking and DP tradeoffs.
Solution
class Solution:
def numberOfPatterns(self, m: int, n: int) -> int:
def dfs(i: int, cnt: int = 1) -> int:
if cnt > n:
return 0
vis[i] = True
ans = int(cnt >= m)
for j in range(1, 10):
x = cross[i][j]
if not vis[j] and (x == 0 or vis[x]):
ans += dfs(j, cnt + 1)
vis[i] = False
return ans
cross = [[0] * 10 for _ in range(10)]
cross[1][3] = cross[3][1] = 2
cross[1][7] = cross[7][1] = 4
cross[1][9] = cross[9][1] = 5
cross[2][8] = cross[8][2] = 5
cross[3][7] = cross[7][3] = 5
cross[3][9] = cross[9][3] = 6
cross[4][6] = cross[6][4] = 5
cross[7][9] = cross[9][7] = 8
vis = [False] * 10
return dfs(1) * 4 + dfs(2) * 4 + dfs(5)class Solution {
private int m;
private int n;
private int[][] cross = new int[10][10];
private boolean[] vis = new boolean[10];
public int numberOfPatterns(int m, int n) {
this.m = m;
this.n = n;
cross[1][3] = cross[3][1] = 2;
cross[1][7] = cross[7][1] = 4;
cross[1][9] = cross[9][1] = 5;
cross[2][8] = cross[8][2] = 5;
cross[3][7] = cross[7][3] = 5;
cross[3][9] = cross[9][3] = 6;
cross[4][6] = cross[6][4] = 5;
cross[7][9] = cross[9][7] = 8;
return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1);
}
private int dfs(int i, int cnt) {
if (cnt > n) {
return 0;
}
vis[i] = true;
int ans = cnt >= m ? 1 : 0;
for (int j = 1; j < 10; ++j) {
int x = cross[i][j];
if (!vis[j] && (x == 0 || vis[x])) {
ans += dfs(j, cnt + 1);
}
}
vis[i] = false;
return ans;
}
}class Solution {
public:
int numberOfPatterns(int m, int n) {
int cross[10][10];
memset(cross, 0, sizeof(cross));
bool vis[10];
memset(vis, false, sizeof(vis));
cross[1][3] = cross[3][1] = 2;
cross[1][7] = cross[7][1] = 4;
cross[1][9] = cross[9][1] = 5;
cross[2][8] = cross[8][2] = 5;
cross[3][7] = cross[7][3] = 5;
cross[3][9] = cross[9][3] = 6;
cross[4][6] = cross[6][4] = 5;
cross[7][9] = cross[9][7] = 8;
function<int(int, int)> dfs = [&](int i, int cnt) {
if (cnt > n) {
return 0;
}
vis[i] = true;
int ans = cnt >= m ? 1 : 0;
for (int j = 1; j < 10; ++j) {
int x = cross[i][j];
if (!vis[j] && (x == 0 || vis[x])) {
ans += dfs(j, cnt + 1);
}
}
vis[i] = false;
return ans;
};
return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1);
}
};function numberOfPatterns(m: number, n: number): number {
const cross: number[][] = Array(10)
.fill(0)
.map(() => Array(10).fill(0));
const vis: boolean[] = Array(10).fill(false);
cross[1][3] = cross[3][1] = 2;
cross[1][7] = cross[7][1] = 4;
cross[1][9] = cross[9][1] = 5;
cross[2][8] = cross[8][2] = 5;
cross[3][7] = cross[7][3] = 5;
cross[3][9] = cross[9][3] = 6;
cross[4][6] = cross[6][4] = 5;
cross[7][9] = cross[9][7] = 8;
const dfs = (i: number, cnt: number): number => {
if (cnt > n) {
return 0;
}
vis[i] = true;
let ans = 0;
if (cnt >= m) {
++ans;
}
for (let j = 1; j < 10; ++j) {
const x = cross[i][j];
if (!vis[j] && (x === 0 || vis[x])) {
ans += dfs(j, cnt + 1);
}
}
vis[i] = false;
return ans;
};
return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1);
}func numberOfPatterns(m int, n int) int {
cross := [10][10]int{}
vis := [10]bool{}
cross[1][3] = 2
cross[1][7] = 4
cross[1][9] = 5
cross[2][8] = 5
cross[3][7] = 5
cross[3][9] = 6
cross[4][6] = 5
cross[7][9] = 8
cross[3][1] = 2
cross[7][1] = 4
cross[9][1] = 5
cross[8][2] = 5
cross[7][3] = 5
cross[9][3] = 6
cross[6][4] = 5
cross[9][7] = 8
var dfs func(int, int) int
dfs = func(i, cnt int) int {
if cnt > n {
return 0
}
vis[i] = true
ans := 0
if cnt >= m {
ans++
}
for j := 1; j < 10; j++ {
x := cross[i][j]
if !vis[j] && (x == 0 || vis[x]) {
ans += dfs(j, cnt+1)
}
}
vis[i] = false
return ans
}
return dfs(1, 1)*4 + dfs(2, 1)*4 + dfs(5, 1)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backtracking | O(9!) | O(9) | Understanding the full search space and Android movement rules |
| Symmetry Optimized Backtracking | O(9!) | O(9) | Best practical solution; reduces repeated DFS using grid symmetry |
| Bitmask Dynamic Programming | O(9 * 2^9) | O(9 * 2^9) | When modeling states formally or demonstrating DP with bitmasking |
Frequently asked questions
Is Android Unlock Patterns easy or hard?
Android Unlock Patterns is typically classified as Medium difficulty. The backtracking itself is straightforward, but the tricky part is encoding the intermediate key rule and recognizing the symmetry optimization to reduce redundant searches.
Android Unlock Patterns Python/Java solution
Implement a DFS function that tracks the current key, visited set, and remaining length. Use a skip matrix to validate moves such as 1→3 requiring 2 or 1→9 requiring 5. Run DFS from representative digits (1, 2, and 5) and multiply counts using symmetry. The same logic translates easily across Python, Java, C++, Go, and TypeScript.
How to solve Android Unlock Patterns in O(n)?
An exact O(n) solution does not exist because the algorithm must explore combinations of keys that form valid patterns. The closest efficient formulation uses backtracking with pruning or a DP state defined by (current key, visited bitmask). That DP approach runs in roughly O(9 * 2^9) states.
What is the best approach for Android Unlock Patterns?
Symmetry optimized backtracking is the most common solution. Use DFS with a visited array and a skip matrix that stores which intermediate key must be visited for certain moves. Start from three representative keys (corner, edge, center) and multiply results using grid symmetry. This keeps the logic simple while reducing redundant searches.
Is Android Unlock Patterns asked at Google/Amazon/Meta?
Android Unlock Patterns has appeared in interviews at companies that emphasize recursion and state search problems. Variations of the question have been reported in Google and other large tech company interviews because it tests backtracking, constraint validation, and optimization through symmetry.
What data structure is used in Android Unlock Patterns?
The solution typically uses a visited array or bitmask to track selected keys and a 10x10 skip matrix that records intermediate keys required between two digits. DFS recursion explores valid next moves while enforcing the skip rule.
What is the time complexity of Android Unlock Patterns?
The worst case time complexity is O(9!) because the algorithm explores permutations of the nine keys with pruning rules. In practice the search space is much smaller due to the Android movement constraints and symmetry optimization. Space complexity is O(9) for the recursion stack and visited tracking.