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:
min and at most max keys.
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 <= 9When 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:
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:
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_patternsThe 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:
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| Case | How to Handle |
|---|---|
| Invalid input: n < 1 or n > 9 or m < 1 or m > 9 or m > n | Return 0 immediately since the pattern length is outside the permissible range. |
| n = 1 and m = 1 (Pattern of length 1) | 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) | 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 | 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) | 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) | 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. | 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). | The starting number will greatly affect available moves; the solution needs to correctly account for this in its valid move checking. |