We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Android Unlock Patterns

Number: 351

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a 3x3 grid representing the Android lock screen, count the number of valid unlock patterns that use at least m keys and at most n keys. A valid pattern must use distinct dots and if a line drawn between two consecutive dots passes through another dot, that intervening dot must have already been used in the pattern. Patterns are considered unique if the set or the order of the dots used differ.

Key Insights

  • Leverage symmetry: The grid’s corners, edges, and center exhibit symmetry which allows us to compute results for one cell in each symmetric group and then multiply appropriately.
  • Use DFS (depth-first search) with backtracking to explore all possible patterns.
  • Precompute a “skip” table that records the dot between two given dots if a jump is required. This table helps quickly decide if a move is valid—i.e., if the intervening dot is already visited.
  • Ensure that during the DFS recursion, a move is only allowed if it doesn’t violate the rule of "jumping" over a non-visited dot.
  • Use the constraints on m and n to count patterns of valid lengths.

Space and Time Complexity

Time Complexity: O(9!) in the worst-case scenario since we explore all possible permutations of the 9 dots. However, due to symmetry and early pruning with the skip condition, the practical runtime is considerably lower. Space Complexity: O(9) due to the recursion stack and space for tracking visited nodes.

Solution

The solution uses a DFS algorithm with backtracking. A 10-element visited boolean array (using 1-indexing for clarity) keeps track of which dots have been used. A precomputed 2D array (skip table) holds the intermediate dot that must be visited when moving between two dots, if any. The DFS starts from a given dot and recursively attempts to extend the pattern by moving to every possible other dot that meets the conditions (either no intervening dot or the intervening dot has been visited). By using symmetry, we compute the count for one corner, one edge, and the center, then aggregate the result appropriately.

Code Solutions

def numberOfPatterns(m: int, n: int) -> int:
    # skip[i][j] holds the intermediate dot between i and j that must be visited first (0 if none)
    skip = [[0] * 10 for _ in range(10)]
    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[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = 5

    def dfs(current: int, remain: int, visited: list) -> int:
        if remain < 0:
            return 0
        if remain == 0:
            return 1
        count = 0
        visited[current] = True
        # Try every next dot from 1 to 9
        for next_dot in range(1, 10):
            # If next dot is not visited and (there is no required skip or the skip dot has already been visited)
            if not visited[next_dot] and (skip[current][next_dot] == 0 or visited[skip[current][next_dot]]):
                count += dfs(next_dot, remain - 1, visited)
        visited[current] = False
        return count

    total_patterns = 0
    visited = [False] * 10
    # Use symmetry: corners (1, 3, 7, 9), edges (2, 4, 6, 8), center (5)
    for length in range(m, n + 1):
        count_corner = dfs(1, length - 1, visited)
        count_edge = dfs(2, length - 1, visited)
        count_center = dfs(5, length - 1, visited)
        total_patterns += 4 * count_corner + 4 * count_edge + count_center
    return total_patterns

# Example usage:
print(numberOfPatterns(1, 1))  # Output: 9
← Back to All Questions