Leetcode 351. Android Unlock Patterns

Problem Description

In this problem, we are required to generate and count all possible unlock patterns on the Android 3x3 lock screen. An unlock pattern is a sequence of connected distinct keys in the lock screen.

A common Android lock screen is a three by three grid, where each cell represents a number and a valid pattern is denoted by connecting keys in different cells.

Below is the representation of an Android lock screen:

There are a couple of rules defining 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 been selected in the pattern. No jumps through non-selected key is allowed.
4. The order of keys used matters.

Let's go through a couple of examples:

For instance:

It would be invalid to make the following pattern: 4 - 1 - 3 - 6 because the line from 1 - 3 passes through key 2 which had not been selected in the pattern.

Similarly, this pattern is also invalid: 4 - 1 - 9 - 2 as the line from 1 - 9 passes through key 5 which was not selected earlier in the pattern.

On the other hand, 2 - 4 - 1 - 3 - 6 is a valid move since the line from 1 - 3 passes through key 2, which had been selected in the pattern.

Also, 6 - 5 - 4 - 1 - 9 - 2 is valid because the line from 1 - 9 passes through key 5, which had been selected in the pattern.

Approach to the solution

This problem can be solved using depth-first search (DFS). The basic idea is to search all possible patterns from each key and count the ones that follow the rules and have a length between m and n.

Different patterns need to be symmetrically handled in order to optimize the problem-solving process. The optimization is based on the fact that the screen is symmetric. Keys 1, 3, 7, 9 are symmetric, and the cases of keys 2, 4, 6, 8 are also the same. The case of key 5 is special and only needs to be counted once.

We need to handle jumps across keys, for example, from key 1 to 9, it passes the key 5, the rule says it's only valid if 5 has been selected before. We can add this rule in the search process.

The across vector is used to keep track of the keys that are on the path between two keys. The seen vector tracks whether a key has been used in the current pattern. These are used in the dfs function to determine if a move to a key is valid.

Python Solution

1
2python
3class Solution:
4    def numberOfPatterns(self, m: int, n: int) -> int:
5        self.m = m
6        self.n = n
7        self.used = [False]*10
8
9        # Define jumps between all pairs of keys
10        self.jumps = [[0]*10 for _ in range(10)]
11        self.jumps[1][3] = self.jumps[3][1] = 2
12        self.jumps[4][6] = self.jumps[6][4] = 5
13        self.jumps[7][9] = self.jumps[9][7] = 8
14        self.jumps[1][7] = self.jumps[7][1] = 4
15        self.jumps[2][8] = self.jumps[8][2] = 5
16        self.jumps[3][9] = self.jumps[9][3] = 6
17        self.jumps[1][9] = self.jumps[9][1] = 5
18        self.jumps[3][7] = self.jumps[7][3] = 5
19
20        count = 0
21        count += self.dfs(1, 1) * 4  # 1, 3, 7, 9 are symmetric
22        count += self.dfs(2, 1) * 4  # 2, 4, 6, 8 are symmetric
23        count += self.dfs(5, 1)  # 5
24
25        return count
26
27    def dfs(self, num, length):
28        if length > self.n:
29            return 0
30        if self.m <= length <= self.n:
31            count = 1
32        else:
33            count = 0
34
35        self.used[num] = True
36        for next in range(1, 10):
37            jump = self.jumps[num][next]
38            if not self.used[next] and (jump == 0 or self.used[jump]):
39                count += self.dfs(next, length + 1)
40        self.used[num] = False
41
42        return count

In the above solution, a depth-first search function dfs is defined that tries to find all patterns from a given number. The function iteratively tries to move from the current number to all numbers that haven't been used yet and that are reachable according to the rules. If the pattern length is within the range [m, n], it's counted as a valid pattern.

Java Solution

1
2java
3class Solution {
4    private int[][] jumps;
5    private boolean[] visited;
6
7    public int numberOfPatterns(int m, int n) {
8        jumps = new int[10][10];
9        jumps[1][3] = jumps[3][1] = 2;
10        jumps[4][6] = jumps[6][4] = 5;
11        jumps[7][9] = jumps[9][7] = 8;
12        jumps[1][7] = jumps[7][1] = 4;
13        jumps[2][8] = jumps[8][2] = 5;
14        jumps[3][9] = jumps[9][3] = 6;
15        jumps[1][9] = jumps[9][1] = 5;
16        jumps[3][7] = jumps[7][3] = 5;
17        visited = new boolean[10];
18        int count = 0;
19        count += dfs(1, 1, 0, m, n) * 4; // 1, 3, 7, 9 are symmetric
20        count += dfs(2, 1, 0, m, n) * 4; // 2, 4, 6, 8 are symmetric
21        count += dfs(5, 1, 0, m, n); // 5
22        return count;
23    }
24
25    private int dfs(int num, int len, int count, int m, int n) {
26        if (len >= m) ++count;
27        ++len;
28        if (len > n) return count;
29        visited[num] = true;
30        for (int next = 1; next <= 9; ++next) {
31            int jump = jumps[num][next];
32            if (!visited[next] && (jump == 0 || visited[jump])) {
33                count = dfs(next, len, count, m, n);
34            }
35        }
36        visited[num] = false;
37        return count;
38    }
39}

The Java solution follows the same logic as the Python solution.

C# Solution

1
2csharp
3public class Solution {
4    private int[,] jumps;
5    private bool[] visited;
6    private int m;
7    private int n;
8    public int NumberOfPatterns(int m, int n) {
9        jumps = new int[10, 10];
10        visited = new bool[10];
11        this.m = m;
12        this.n = n;
13        jumps[1, 3] = jumps[3, 1] = 2;
14        jumps[1, 7] = jumps[7, 1] = 4;
15        jumps[1, 9] = jumps[9, 1] = 5;
16        jumps[2, 8] = jumps[8, 2] = 5;
17        jumps[3, 7] = jumps[7, 3] = 5;
18        jumps[3, 9] = jumps[9, 3] = 6;
19        jumps[4, 6] = jumps[6, 4] = 5;
20        jumps[7, 9] = jumps[9, 7] = 8;
21
22        int count = 0;
23        count += DFS(1, 1, 0) * 4;
24        count += DFS(2, 1, 0) * 4;
25        count += DFS(5, 1, 0);
26
27        return count;
28        
29    }
30
31    private int DFS(int num, int len, int result) 
32    {
33        if (len >= m) ++result;
34        ++len;
35        if (len > n) return result;
36        visited[num] = true;
37        for (int next = 1; next <= 9; ++next) 
38        {
39            int jump = jumps[num, next];
40            if (!visited[next] && (jump == 0 || visited[jump]))
41            {
42                result = DFS(next, len, result);
43            }
44        }
45        visited[num] = false;
46        return result;
47    }
48}

The C# solution closely follows the Python and Java solutions. The major difference comes into play due to language-specific syntaxes such as how multi-dimensional arrays are declared and accessed.

JavaScript Solution

1
2javascript
3class Solution {
4
5  count = 0;
6  board = Array.from({ length: 3 }, () => Array.from({ length: 3 }));
7
8  numberOfPatterns(m, n) {
9    this.visited = Array.from({ length: 9 }, () => false);
10    this.m = m;
11    this.n = n;
12    this.count = 0;
13
14    for (let length = 1; length <= 9; ++length) {
15      this.dfs(-1, length);
16      this.visited = Array.from({ length: 9 }, () => false);
17    }
18
19    return this.count;
20  }
21
22  dfs(prev, length) {
23    if (length === 0) {
24      ++this.count;
25      return;
26    }
27    for (let i = 0; i < 9; ++i) {
28      if (this.isValid(i, prev)) {
29        this.visited[i] = true;
30        this.dfs(i, length - 1);
31        this.visited[i] = false;
32      }
33    }
34  }
35
36  isValid(index, last) {
37    if (this.visited[index]) return false;
38    if (last === -1) return true;
39    if ((index + last) % 2 === 1) return true;
40
41    let mid = Math.floor((index + last) / 2);
42    if (index % 3 !== last % 3 && Math.floor(index / 3) !== Math.floor(last / 3)) {
43      return this.visited[mid];
44    }
45    return true;
46  }
47}
48
49const solution = new Solution();
50console.log(solution.numberOfPatterns(1, 2));

The JavaScript solution follows the same depth-first search principle. The major difference comes in the way the environment is set up for the DFS and how the DFS is done.

Time & Space Complexity Analysis

The solutions in Python, Java, C#, and JavaScript have a time complexity of O(N!) because we perform a depth-first search from each of the 9 keys, where N is the given input size. As depth-first search could potentially visit all the permutations of the keys, this leads to a time complexity of O(N!). The space complexity is O(N) which is used to store the current unlock pattern trace and the jumping keys table. This N space is required for each DFS traversal.We have provided solutions for the problem in four programming languages, namely Python, Java, C#, and Javascript. All these solutions use Depth First Search (DFS) to explore all possible combinations and permutations of key sequences that can form valid patterns.

In summary, if you need to create a solution for this problem in other languages, you can follow these same steps:

1. Define your depth-first search (DFS) function that explores all valid moves from a given number, according to the defined rules.

2. Run this DFS function from all each of the 9 keys symmetrically. In other words, call the function for the keys 1, 2, and 5 only, and then multiply the result by 4 for the keys 1 and 2 to account for the symmetry.

Please consider that the above methods have a time complexity of O(N!), where N is the possible permutations of the keys, and a space complexity of O(N), because we are maintaining the stack for DFS traversal and for storing the valid unlock patterns. Thus, while these solutions are accurate, they may be slow for large inputs.

Possible improvements:

If you want to optimize the method, you may consider using more sophisticated techniques such as dynamic programming to reduce the time complexity. This technique can be useful to avoid redundant calculations by storing intermediate results, but it will make the logic more complex and difficult to understand.