Android Unlock Patterns - Leetcode Solution

The Android Unlock Patterns problem on LeetCode is a problem that asks you to count the number of possible patterns that can be created by connecting the dots on an Android lock screen. The problem is a medium-level problem and it requires you to come up with an efficient solution.

Problem Statement:

Given an Android lock screen pattern, count the number of possible patterns that can be created by connecting the dots.

The Android lock screen is made up of nine dots arranged in a 3x3 matrix. To create a pattern, the user connects dots with a line, starting from one dot and ending on another. The user can only connect dots that are adjacent to each other and the dots cannot be visited twice in the same pattern. Also, if the user connects a dot to another dot that is not adjacent, the user must first connect the dots that are in between before connecting the final dot.

For example, the following is a valid pattern:

1 - 2 - 3 | | | 4 - 5 - 6 | | | 7 - 8 - 9

However, the following is not a valid pattern:

1 - 3 | | 2 4

The problem is asking you to count the number of possible patterns that can be created on the Android lock screen given the above constraints.

Solution:

To solve this problem, we can use DFS (depth-first search) algorithm. We can start with a particular dot and recursively explore every possible combination of patterns that can be created from that dot. We can then move on to the next dot and repeat the process until all dots have been used.

To implement this algorithm, we can create a 3x3 matrix representing the dots on the Android lock screen. We can use a boolean array to keep track of which dots have been used in a particular pattern. We can also use a 2D array to represent which dots are adjacent to each other.

We can start by selecting a particular dot as the starting point and then recursively explore all possible patterns that can be created from that dot. We can then move on to the next dot and repeat the process until we have exhausted all the dots on the Android lock screen. We can count the number of patterns that we have explored and return the final count.

Here is the code for the solution:

class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] skip = new int[10][10];
        boolean[] visited = new boolean[10];
        int count = 0;
        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[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = 5;
        skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = 5;
        count += dfs(1, 1, 0, m, n, skip, visited) * 4;
        count += dfs(2, 1, 0, m, n, skip, visited) * 4;
        count += dfs(5, 1, 0, m, n, skip, visited);
        return count;
    }
    
    private int dfs(int num, int len, int count, int m, int n, int[][] skip, boolean[] visited) {
        if (len >= m) count++;
        len++;
        if (len > n) return count;
        visited[num] = true;
        for (int next = 1; next <= 9; next++) {
            int jump = skip[num][next];
            if (!visited[next] && (jump == 0 || visited[jump])) {
                count = dfs(next, len, count, m, n, skip, visited);
            }
        }
        visited[num] = false;
        return count;
    }
}

Time Complexity: O(9^(N-1)), where N is the number of dots on the Android lock screen. Since there are at most 9 dots, the worst-case scenario would be that we visit all the dots on the screen. In each recursive call, we explore at most 9 possible patterns.

Space Complexity: O(N). We are storing the skip array, visited array, and the count variable which require O(N) space. Additionally, the dfs function has a call stack depth of at most N, which also takes O(N) space.

Overall, this algorithm is an efficient solution to the Android Unlock Patterns problem on LeetCode.

1