351. Android Unlock Patterns

Problem Description

The problem belongs to the category of backtracking problems that simulate the process of constructing the unlock patterns of an Android device, which has a distinctive 3 x 3 grid with dots. A user has to draw a pattern by connecting dots without repeating any dot. The challenge is to count all unique and valid unlock patterns that consist of at least m and at most n dots.

The constraints for a pattern to be valid are:

Distinct Dots: Every dot can only appear once in a pattern.
Line Segment Passing: If a line connecting two dots passes through the center of another dot, then that center dot must have already been used in the pattern.

The task involves finding all such unique patterns that obey the above rules and counting them, which may sound simple but can be quite complex to approach due to the possibilities and constraints involved.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's a detailed step-by-step approach to arrive at the recommended algorithm:

Is it a graph?

Yes: The problem can be visualized as a graph where nodes represent the keys on the Android lock screen and edges represent allowable moves between these keys.

Need to solve for kth smallest/largest?

No: The problem is not about finding a specific ordered element like the kth smallest/largest.

Involves Linked Lists?

No: The problem does not involve manipulating or dealing with linked lists.

Does the problem have small constraints?

Yes: The problem describes finding all unique patterns from a minimum of m keys to a maximum of n keys, which are relatively small numbers (generally n <= 9).

Brute force / Backtracking?

Yes: Given small constraints and the need to explore every possible combination or sequence of moves that fulfills certain conditions (e.g., passing through certain keys), backtracking is a suitable approach to generate and check each possible pattern efficiently.

Conclusion: Following the flowchart, it suggests using a Backtracking approach to efficiently explore and generate all valid unlock patterns given the constraints and the graph-like structure of the problem where nodes are key points and edges are allowable paths.

Intuition

The core idea of the solution is to use backtracking, a common technique to explore all the possibilities in a systematic way. Backtracking allows us to build a solution step-by-step and backtrack as soon as we realize that the current path will not lead to a solution. This way, we efficiently explore the search space of all possible patterns.

To simplify the problem, we use the following strategies:

Symmetry: The 3 x 3 grid has symmetrical properties that we can exploit to reduce computation. For example, starting from corner points (1, 3, 7, 9) or starting from edge midpoints (2, 4, 6, 8) give rise to patterns that are essentially similar. Therefore, computing for one corner and multiplying the result by 4 (since there are 4 corners) and doing the same for the edge midpoints is sufficient.
Cross Points: To address the constraint regarding the line segment passing, we create an auxiliary 'cross' matrix that records the cross point for each pair of dots. For instance, the pair (1, 3) has the cross point 2. During the exploration of patterns, we use this information to check if we are allowed to connect two dots straightaway or if we need to have passed through certain dots first.

Approaching the problem this way breaks down the complex task into smaller steps and uses reasoning to efficiently search for all possible solutions by considering the symmetry and constraints unique to the unlock pattern challenge.

In essence, we consider each dot as a starting point and explore all possible patterns emanating from it while keeping track of the visited dots and ensuring we adhere to the rules stated. We recursively build paths and count those that fall within the m to n range.

Learn more about Dynamic Programming and Backtracking patterns.

Solution Approach

The solution's approach can be divided into the following steps, each leveraging specific algorithms, data structures, or patterns commonly used in backtracking problems:

Defining the Cross Matrix: We start by defining a cross matrix where cross[i][j] represents the middle point (the point that should be previously visited) when drawing a line from dot i to dot j. This matrix is precomputed and hard-coded into the solution to comply with the constraint regarding the line segments.
Backtracking Function dfs: A recursive backtracking function dfs is implemented to explore all unique paths from any start dot. This function takes two parameters: the current dot i and a counter cnt that tracks the number of dots in the current pattern. The backtracking ends when the pattern's length exceeds n.
Maintaining vis Vector: We use a vis vector which is a list of boolean values indicating whether a dot has been visited (True) or not (False). This helps avoid reusing a dot in the same pattern, ensuring all dots are distinct.
Exploring (DFS) and Counting: For each dot, we perform a Depth-First Search (DFS) by recursively calling the dfs function on the next unvisited dot. If the current dot count is between m and n (inclusive), we increment our count of valid patterns (ans). The number of patterns that start from a certain dot can be obtained by simply returning ans at the end of exploring from that dot.
Respecting the Constraints: While exploring, we check if moving from the current dot i to the next dot j directly is valid or not by using the cross matrix. If it passes over a dot that hasn't been visited yet (vis[x] is False where x is the cross point), then we skip this path.
Symmetric Property Exploitation: The solution uses symmetry in the grid by calling the dfs function for only three distinct starting points - a corner, an edge midpoint, and the center. The counts for the corner and edge midpoints are then multiplied by 4 because there are four symmetric instances for corners and edge midpoints on the grid. The center is considered only once as it is unique.
Computing the Final Result: The final answer is the sum of patterns starting from the corner (returned value from dfs multiplied by 4), patterns starting from an edge midpoint (also multiplied by 4), and patterns starting from the center.

By following this approach, we systematically explore the entire search space while diligently sticking to the problem's rules and exploiting the grid's symmetric property to avoid redundant computation. This results in a computationally efficient solution to the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a simplified example to illustrate the solution. Imagine we are interested in finding valid patterns that consist of exactly 2 dots on the 3 x 3 grid. For simplicity, we'll start with a single starting point, which is the top-left corner dot 1. Here's how the backtracking process with the aforementioned approach looks like:

We begin by defining the cross matrix with NULL values indicating no cross points. Since our example only considers patterns with 2 dots, we don't need to worry much about cross points here.
The backtracking function dfs starts with dot 1. We mark dot 1 as visited in the vis vector.
We call dfs with the starting dot 1 and cnt initialized to 1 since we've already included dot 1 in our pattern.
From dot 1, we explore the next possible dots. Let's try to move to dot 2. Since it has not been visited and does not require passing through a middle dot, we recurse with dfs(2, cnt+1).
Inside dfs(2, 2), we check if cnt equals n (which is 2 in our hypothetical case). As it does, we increment our pattern count ans by 1 for this valid sequence [1, 2]. There's no further recursion since we've reached the maximum dots allowed.
We backtrack and try the next possibility, moving to dot 3. Since it's valid and doesn't cross over any unvisited dots, we call dfs(3, cnt+1) and increment our count with the sequence [1, 3].
We continue this process trying all possible dots (4, 5, 6, 7, 8, 9) and counting the number of valid patterns of length 2 starting with dot 1. For each valid move, we increment ans.
Since we're only calculating patterns starting from dot 1 in this example, there's no need for symmetry exploitation. But in a full solution, we would multiply the ans from this step by 4 to account for patterns starting from corners (1, 3, 7, 9) due to the symmetric property.
The final answer for 2-dot patterns starting from the corner would be the value of ans obtained from all the recursive dfs calls starting with dot 1.

So, assuming our grid only allowed patterns to be exactly 2 dots starting from dot 1, the ans would represent the number of valid patterns, and the process highlighted here would enumerate them all. In a complete solution, patterns starting from different symmetrical points on the grid and of varying lengths between m and n would all be similarly explored to get the final count.

Solution Implementation

1class Solution:
2    def numberOfPatterns(self, m: int, n: int) -> int:
3        def dfs(current: int, count: int = 1) -> int:
4            # If the count exceeds n, no further patterns can be formed
5            if count > n:
6                return 0
7
8            # Mark the current number as visited
9            visited[current] = True
10          
11            # Initialize answer as 1 if the current pattern length is within the range [m, n]
12            patterns_count = int(m <= count)
13          
14            # Explore all possible next moves
15            for next_num in range(1, 10):
16                cross_num = cross[current][next_num]
17              
18                # Check if next_num is not visited and if there's no need to cross over a non-visited number
19                if not visited[next_num] and (cross_num == 0 or visited[cross_num]):
20                    patterns_count += dfs(next_num, count + 1)
21          
22            # Backtrack by marking current number as not visited
23            visited[current] = False
24          
25            return patterns_count
26
27        # Initialize a matrix that records the number that must be crossed to go from one number to another
28        cross = [[0] * 10 for _ in range(10)]
29      
30        # Setting the cross numbers that need to be crossed between non-adjacent keys
31        cross[1][3] = cross[3][1] = 2
32        cross[1][7] = cross[7][1] = 4
33        cross[1][9] = cross[9][1] = 5
34        cross[2][8] = cross[8][2] = 5
35        cross[3][7] = cross[7][3] = 5
36        cross[3][9] = cross[9][3] = 6
37        cross[4][6] = cross[6][4] = 5
38        cross[7][9] = cross[9][7] = 8
39      
40        # Flags to keep track of visited numbers
41        visited = [False] * 10
42      
43        # Start the patterns from numbers 1, 2, and 5
44        # Multiply the return values by 4 for symmetrical positions (1,3,7,9) and (2,4,6,8)
45        return dfs(1) * 4 + dfs(2) * 4 + dfs(5)
46

1class Solution {
2    // Variable to store the minimum pattern length
3    private int minPatternLength;
4    // Variable to store the maximum pattern length
5    private int maxPatternLength;
6    // Matrix to store the jump-over number between two keys
7    private int[][] crossOverPoints = new int[10][10];
8    // Array to keep track of visited keys
9    private boolean[] visited = new boolean[10];
10
11    public int numberOfPatterns(int m, int n) {
12        this.minPatternLength = m;
13        this.maxPatternLength = n;
14        // Initialize the crossover point between pairs of keys
15        // where a third key has to be crossed over for a valid pattern
16        crossOverPoints[1][3] = crossOverPoints[3][1] = 2;
17        crossOverPoints[1][7] = crossOverPoints[7][1] = 4;
18        crossOverPoints[1][9] = crossOverPoints[9][1] = 5;
19        crossOverPoints[2][8] = crossOverPoints[8][2] = 5;
20        crossOverPoints[3][7] = crossOverPoints[7][3] = 5;
21        crossOverPoints[3][9] = crossOverPoints[9][3] = 6;
22        crossOverPoints[4][6] = crossOverPoints[6][4] = 5;
23        crossOverPoints[7][9] = crossOverPoints[9][7] = 8;
24        // Calculate the number of valid patterns starting from different positions
25        // Since the pattern is symmetric for positions 1, 3, 7, 9 and for positions 2, 4, 6, 8,
26        // multiply the result of their respective DFS by 4 and add the count for position 5
27        return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1);
28    }
29
30    // Helper method for depth-first search to find all valid patterns
31    private int dfs(int position, int length) {
32        // If current length exceeds the maximum pattern length, return 0 (as it's invalid)
33        if (length > maxPatternLength) {
34            return 0;
35        }
36        // Mark the current position as visited
37        visited[position] = true;
38        // If current length is within the pattern length bounds, increment the pattern count
39        int count = (length >= minPatternLength) ? 1 : 0;
40        // Explore all other keys as potential next steps in the pattern
41        for (int nextKey = 1; nextKey < 10; ++nextKey) {
42            int crossOverKey = crossOverPoints[position][nextKey];
43            // If the next key hasn't been visited and (there is no crossover point or the crossover point has been visited)
44            if (!visited[nextKey] && (crossOverKey == 0 || visited[crossOverKey])) {
45                // Continue the depth-first search from the next key
46                count += dfs(nextKey, length + 1);
47            }
48        }
49        // Backtrack: unmark the current position to allow it to be part of other patterns
50        visited[position] = false;
51        // Return the total pattern count
52        return count;
53    }
54}
55

1#include <vector>
2#include <functional>
3#include <cstring>
4
5class Solution {
6public:
7    /* This function counts the number of distinct patterns from m to n moves. */
8    int numberOfPatterns(int m, int n) {
9        // cross are the numbers that need to be visited before visiting an index for a valid pattern
10        int cross[10][10];
11        std::memset(cross, 0, sizeof(cross));
12        // visited array to keep track of visited numbers in the pattern
13        bool visited[10];
14        std::memset(visited, false, sizeof(visited));
15
16        // Manually setting the cross over numbers
17        cross[1][3] = cross[3][1] = 2;
18        cross[1][7] = cross[7][1] = 4;
19        cross[1][9] = cross[9][1] = 5;
20        cross[2][8] = cross[8][2] = 5;
21        cross[3][7] = cross[7][3] = 5;
22        cross[3][9] = cross[9][3] = 6;
23        cross[4][6] = cross[6][4] = 5;
24        cross[7][9] = cross[9][7] = 8;
25
26        // Depth-first search function to explore possible patterns
27        std::function<int(int, int)> dfs = [&](int index, int count) {
28            // If count exceeds n, stop exploring
29            if (count > n) {
30                return 0;
31            }
32            visited[index] = true; // Mark the index as visited
33            // If current count between m and n, include it in answer
34            int patterns = count >= m ? 1 : 0;
35            // Explore remaining numbers
36            for (int j = 1; j < 10; ++j) {
37                int requiredBefore = cross[index][j];
38                // Explore the next number if it has not been visited and the required number has been visited, if any
39                if (!visited[j] && (requiredBefore == 0 || visited[requiredBefore])) {
40                    patterns += dfs(j, count + 1);
41                }
42            }
43            visited[index] = false; // Backtrack, mark index as unvisited
44            return patterns; // Return the count of valid patterns
45        };
46
47        // Start DFS from 1, 2, 5 for symmetric patterns and sum up the results
48        return dfs(1, 1) * 4 // Corners, so counted 4 times
49               + dfs(2, 1) * 4 // Edges, so also counted 4 times
50               + dfs(5, 1);    // Center, counted once
51    }
52};
53

1// Function to calculate the number of unique patterns that can be drawn on an Android lock screen.
2// `m` is the minimum length of a pattern, `n` is the maximum length.
3function numberOfPatterns(m: number, n: number): number {
4    // Initialization of a matrix to track the crossing over number between two points.
5    const cross: number[][] = Array.from({ length: 10 }, () => Array(10).fill(0));
6  
7    // Tracks whether a digit has been visited.
8    const visited: boolean[] = Array(10).fill(false);
9  
10    // Define crossing over points which require to visit a middle point before reaching the destination.
11    cross[1][3] = cross[3][1] = 2;
12    cross[1][7] = cross[7][1] = 4;
13    cross[1][9] = cross[9][1] = 5;
14    cross[2][8] = cross[8][2] = 5;
15    cross[3][7] = cross[7][3] = 5;
16    cross[3][9] = cross[9][3] = 6;
17    cross[4][6] = cross[6][4] = 5;
18    cross[7][9] = cross[9][7] = 8;
19
20    // Depth-First Search to explore all possible combinations from a starting digit.
21    // `current` is the current digit being visited.
22    // `count` is the current length of the pattern.
23    const dfs = (current: number, count: number): number => {
24        if (count > n) return 0;
25      
26        visited[current] = true;
27        let patterns = 0;
28        if (count >= m) {
29            patterns++;
30        }
31      
32        for (let next = 1; next < 10; ++next) {
33            const requiredMiddlePoint = cross[current][next];
34            if (!visited[next] && (requiredMiddlePoint === 0 || visited[requiredMiddlePoint])) {
35                patterns += dfs(next, count + 1);
36            }
37        }
38      
39        visited[current] = false; // Backtrack
40        return patterns;
41    };
42
43    // Calculate patterns starting from each of the corner keys (1, 3, 7, 9) and edges (2, 4, 6, 8), and the center (5).
44    // Corners and edges are symmetric, so result is multiplied by 4.
45    return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1);
46}
47

Time and Space Complexity

Time Complexity

The provided code employs a Depth-First Search (DFS) strategy for traversing the space of all possible patterns that can be created on a 3x3 keypad, starting from digit 1, digit 2, and digit 5. The worst-case time complexity would be calculated under the condition that we visit each digit exactly once and go through all possible patterns. Since there are 9 digits and each DFS invocation can lead up to 8 further invocations (minus the visited numbers and the cross numbers that require a middle number to be visited first), the upper bound can initially seem to be O(9!). Yet, the time complexity is better due to the constraints that cut down the search space significantly - the cross matrix prevents jumps over unvisited keys.

Given that we invoke the DFS starting from 1, 2, and 5, these are our symmetrical starting points, and the answer will be the result from calling DFS from these start points, each multiplied by the number of symmetric equivalents on the keypad (corners are 4 times, edges are 4 times, and the center is unique):

Invoke dfs(1) and multiply the result by 4 (for the 4 corners).
Invoke dfs(2) and multiply the result by 4 (for the 4 edge middle points).
Invoke dfs(5) (the center).

Hence, we can simplify the naive factorial complexity as each corner and edge contribute equally.

Despite the upper bound given by the factorial, the actual time complexity is significantly less due to the constraints reducing the number of candidates at each step. However, providing an exact time complexity is difficult without empirical analysis or a more detailed combinatorial examination, which typically isn't expected for interview-style coding problems.

Space Complexity

The space complexity of the algorithm is O(n) due to the recursive nature of DFS, where n in this context is the maximum depth of the recursive stack, which corresponds to the maximum length of the pattern (up to 9). We also have additional data structures - vis (used to mark visited numbers) and cross (a matrix indicating the middle number that must be visited when going from one number to another in a direct line), but these are of fixed size and hence constitute O(1) additional space. Therefore, the space complexity remains O(n) where n stands for the number of recursive calls.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don’t know