351 Android Unlock Patterns
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:
Each pattern must connect at least m keys and at most n keys.
All the keys must be distinct.
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.
The order of keys used matters.
Explanation:
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.
Example: Given m= 1,n = 1, return 9.
Approach 1: Brute Force
The Idea: For the first reader this problem may have some confusions due to the poor phrasing of the problem. One ambiguity to resolve from the diagram is that the digits are actually circles, and not framed in boxes. For example, digit 1 has the following options to take in the first step without crossing over other digits. The remaining digits have the following options:
Modeling this problem the correct way, I thought was the most challenging part of this problem. We can begin but first concretely define the rules for this problem. I have used a matrix to denote what the required number is in order to get to another number. For example, conditional[1][3] = 2
, which denotes, that in order to get 1 to 3, we must at least pass through 2.
There are two rules we have to satisfy in order to recur down the tree:
The path has to be unique (visit only once)
We cannot visit a digit in the phone that is required by the conditional UNLESS we already visited the element that is required by the conditional
Complexity: O(P^n) time, O(P) space, where P = Number of digits in the Pattern, and n = n-1, n-2, n-3 ... 0 (depends on digit). On average, we can say that n begins at 6, and decreases by 1 every level in the tree (but also sometimes potentially gain), so its hard to say.
Last updated