Taro Logo

Android Unlock Patterns

#259 Most AskedMedium
36 views
Topics:
RecursionDynamic Programming

We need to unlock an Android lock screen with a pattern of specific lengths.

Given an m x n Android lock screen and two integers min and max, how many distinct unlock patterns of length between min and max can be generated from the lock screen?

Each pattern must use distinct keys.

Rules for valid unlock patterns:

  1. Each pattern must connect at least min and at most max 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 appeared in the pattern. If the line connecting the i-th key and the (i+1)-th key passes through the j-th key:
    • If the j-th key has not been selected, then the i-th key cannot be connected to the (i+1)-th key.
    • The j-th key is on the direct line segment connecting the i-th key and the (i+1)-th key.

Constraints:
|minKeys| ≤ |length of pattern| ≤ |maxKeys|.

Example:

Input: min = 1, max = 1


 1 2 3
 4 5 6
 7 8 9


Output: 9

Example 2:

Input: min = 1, max = 2


 1 2 3
 4 5 6
 7 8 9


Output: 65

Constraints:

  • 1 <= min <= max <= 9

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the minimum and maximum length of the unlock pattern (i.e., the values of `m` and `n`)?
  2. Are the numbers from 1-9 the only valid keys, or could other characters/symbols also be included?
  3. If a valid pattern is not possible with the given `m` and `n`, what should the function return? Should I return 0 or throw an exception?
  4. Can a key be visited multiple times in the unlock pattern, or must each key be visited at most once?
  5. Can the pattern skip over intermediate numbers that have not been visited if they're on the path between two keys (e.g., can I go from 1 to 3 without visiting 2)? If skipping is allowed, what are the rules for which intermediate keys must be visited before skipping?

Brute Force Solution

Approach

The brute force approach solves this puzzle by simply trying every possible sequence of numbers from the phone keypad. We generate all valid patterns and count how many meet the length requirements.

Here's how the algorithm would work step-by-step:

  1. Start with an empty pattern.
  2. Pick a number from 1 to 9 as the first number in the pattern.
  3. Then, pick another unused number from 1 to 9 to add to the pattern.
  4. Keep picking unused numbers to extend the pattern until all numbers are used, or the pattern reaches the maximum length.
  5. For each pattern you create, check if it is a valid unlock pattern. A valid pattern only moves from one number to another if the intermediate numbers have already been used.
  6. If the pattern is valid and its length is within the allowed range, increase the count of possible patterns.
  7. Repeat the process of starting with a new initial number and creating all possible patterns that follow the rules.
  8. After trying all possible starting numbers and creating all possible patterns from each, the total count will be the answer.

Code Implementation

def android_unlock_patterns(minimum_length, maximum_length):
    number_of_valid_patterns = 0
    
    # Define a function to check if a move is valid based on the used numbers
    def is_valid_move(current_number, previous_number, used_numbers):
        if previous_number == -1:
            return True

        # Check for moves that require a number in between
        if (current_number + previous_number) in [3, 5, 7, 9, 11, 13, 15, 17]:
            middle_number = (current_number + previous_number) // 2
            return middle_number in used_numbers

        # Check for knight moves that require a number in between
        if abs(current_number - previous_number) in [2, 4, 6, 8]:
            if abs(current_number - previous_number) == 2 and current_number % 3 != previous_number % 3:
                return True
            if abs(current_number - previous_number) == 4 and current_number // 3 != previous_number // 3:
                return True
            if abs(current_number - previous_number) == 6:
                middle_number = min(current_number, previous_number) + 3
                return middle_number in used_numbers
            if abs(current_number - previous_number) == 8:
                middle_number = 5
                return middle_number in used_numbers
        return True

    # Recursive function to generate patterns and count valid ones
    def generate_patterns(current_pattern, used_numbers):
        nonlocal number_of_valid_patterns

        pattern_length = len(current_pattern)

        # Count valid patterns within the specified length range
        if minimum_length <= pattern_length <= maximum_length:
            number_of_valid_patterns += 1

        # Stop recursion when the pattern reaches max length
        if pattern_length == maximum_length:
            return

        for next_number in range(1, 10):
            if next_number not in used_numbers:
                previous_number = current_pattern[-1] if current_pattern else -1

                # Only move to the next number if the move is valid
                if is_valid_move(next_number, previous_number, used_numbers):

                    # Create next pattern only if current move is valid
                    new_used_numbers = used_numbers | {next_number}

                    generate_patterns(current_pattern + [next_number], new_used_numbers)

    # Iterate through each possible starting number
    for start_number in range(1, 10):

        # The starting point is important to the result, so we loop through all
        generate_patterns([start_number], {start_number})

    return number_of_valid_patterns

Big(O) Analysis

Time Complexity
O(9!) – The brute force approach explores all possible permutations of numbers from 1 to 9 to generate unlock patterns. In the worst case, it tries every possible order of these numbers. The number of permutations of 9 numbers is 9! (9 factorial). Since each potential pattern also has to be validated, it adds a minor constant factor. Therefore, the dominant operation is the generation of permutations, leading to a time complexity of O(9!).
Space Complexity
O(N) – The primary space usage comes from the 'pattern' list, which stores the sequence of numbers selected. In the worst-case scenario, the pattern can include all numbers from 1 to 9, making its maximum length 9. A 'visited' set or boolean array is used to keep track of used numbers, its size also correlates to the maximum length of the pattern. Thus, the auxiliary space grows linearly with N, where N is the maximum pattern length (up to 9), or the number of possible digits.

Optimal Solution

Approach

The goal is to find all possible unlock patterns of a certain length on a 3x3 grid, where each number corresponds to a spot on the grid. We avoid re-calculating paths by remembering what we've already counted, focusing on building valid sequences step-by-step.

Here's how the algorithm would work step-by-step:

  1. Imagine the keypad as numbers arranged in a 3x3 grid.
  2. We want to know how many valid unlock patterns of length 'm' to 'n' are possible.
  3. Start by visiting each number on the grid and treat it as the first point in a potential pattern.
  4. From each of these starting points, explore the possible next numbers to visit.
  5. A number can only be visited once within a pattern.
  6. Some jumps are only valid if you pass over a number in between. For example, going from 1 to 3 requires passing over 2.
  7. Keep track of visited numbers and consider the jumping rule to determine if a path is valid.
  8. Keep exploring until the pattern is of the desired length.
  9. When a valid pattern is completed, increase the total count.
  10. Repeat the process for each starting number, and for lengths 'm' through 'n'.
  11. Since certain starting numbers are symmetrical, we can use multiplication to reduce redundant calculations.

Code Implementation

def android_unlock_patterns(minimum_length, maximum_length):
    total_patterns = 0
    visited = [False] * 10

    # Defines the valid jumps between numbers.
    jumps = {
        1: {3: 2, 7: 4, 9: 5}, 2: {8: 5}, 3: {1: 2, 7: 5, 9: 6},
        4: {6: 5}, 6: {4: 5}, 7: {1: 4, 3: 5, 9: 8},
        8: {2: 5}, 9: {1: 5, 3: 6, 7: 8}
    }

    def depth_first_search(current_number, current_length):
        nonlocal total_patterns

        if minimum_length <= current_length <= maximum_length:
            total_patterns += 1

        if current_length > maximum_length:
            return

        visited[current_number] = True

        for next_number in range(1, 10):
            if not visited[next_number]:
                # Check for required jumps over intermediate numbers.
                jump_number = jumps.get(current_number, {}).get(next_number)
                if (jump_number is None) or visited[jump_number]:
                    depth_first_search(next_number, current_length + 1)

        visited[current_number] = False

    # Numbers 1, 3, 7, 9 are symmetric.
    total_patterns += 4 * depth_first_search(1, 1)

    # Numbers 2, 4, 6, 8 are symmetric.
    total_patterns += 4 * depth_first_search(2, 1)

    # Number 5 is unique.
    total_patterns += depth_first_search(5, 1)

    return total_patterns

# This determines valid unlock patterns of a certain length.
# This helps avoid redundant calculations by remembering what has been counted already.
# This explores possible next numbers to visit from starting points

Big(O) Analysis

Time Complexity
O(9 * A(9, n)) – The algorithm explores possible unlock patterns of length m to n, starting from each of the 9 numbers on the grid. The dominant factor is the recursive exploration of paths. For each starting number, the algorithm explores all possible paths of length up to n, where n is the maximum pattern length. The number of arrangements can be approximated by A(9, n) = 9! / (9-n)!, representing the arrangements of n elements from a set of 9. We iterate through 9 starting positions, meaning the complexity will be O(9 * A(9, n)). Although A(9, n) simplifies to permutations, and factorials grow quickly, the value 'n' is bounded (1 <= n <= 9).
Space Complexity
O(1) – The algorithm primarily uses a boolean array of size 9 (visited) to track which numbers have been used in the unlock pattern. This array's size is constant regardless of the input range m to n. The recursion depth is limited by the pattern length n, however, the stack space used by recursive calls is proportional to n. Since the maximum value of n is always less than or equal to 9, the space can be considered O(1), or constant space. Therefore, the overall auxiliary space is constant.

Edge Cases

Invalid input: n < 1 or n > 9 or m < 1 or m > 9 or m > n
How to Handle:
Return 0 immediately since the pattern length is outside the permissible range.
n = 1 and m = 1 (Pattern of length 1)
How to Handle:
Return 9 because any single number from 1 to 9 is a valid pattern of length 1.
Skipping over multiple numbers in one move (e.g., going from 1 to 9 without passing 5, if pattern length allows it)
How to Handle:
The isValidMove function should check if intermediate number(s) exist between the current and next numbers if the distance is greater than 1 and is diagonal or a skip-one-intermediate horizontal/vertical jump.
Integer overflow in count calculation for large n
How to Handle:
While n is limited to 9, the intermediate counts could potentially lead to overflow; Use long or BigInteger if necessary.
A very long valid pattern starting with 5 (maximizes recursion depth)
How to Handle:
Ensure the algorithm doesn't exceed reasonable recursion depth by potentially implementing iterative depth-first search.
Repeatedly visiting the same number in a valid pattern (violates constraint)
How to Handle:
Use a boolean array (visited) to keep track of numbers already visited in the current pattern to prevent re-visiting.
m = n = 9, which forces the algorithm to consider all possible paths of length 9.
How to Handle:
Check for time limit exceeding (TLE) and consider using memoization for potentially faster computation if repetitive paths occur.
Starting with a corner number versus starting with the center number (5).
How to Handle:
The starting number will greatly affect available moves; the solution needs to correctly account for this in its valid move checking.
0/1916 completed