LeetCode 351: Android Unlock Patterns Solution in Python – A Step-by-Step Guide

What Is LeetCode 351: Android Unlock Patterns?

LeetCode 351: Android Unlock Patterns is about counting valid swipe patterns on a 3x3 grid, where dots are arranged like this:

Copy code1 2 3
4 5 6
7 8 9

You start at one dot, swipe to another, and continue, following these rules:

• Each dot can only be used once.
• You can swipe in any direction (up, down, left, right, or diagonal).
• If your swipe passes over an unused dot, that dot must already be in your pattern (e.g., 1 to 3 needs 2 first).

You’re given a minimum length m and maximum length n, and you need to count all valid patterns with lengths from m to n. It’s a fun mix of exploration and rule-checking!

Problem Statement

• Input:
• m: minimum number of dots in the pattern (integer).
• n: maximum number of dots in the pattern (integer).
• Output: Total number of valid patterns with lengths between m and n.
• Rules:
• Use each dot (1-9) at most once.
• For jumps over a dot (e.g., 1-9 needs 5), the middle dot must be visited.
• Grid is 3x3, dots numbered 1-9.

Constraints

• 1 <= m <= n <= 9

Examples

• Input: m = 1, n = 1
• Output: 9 (one-dot patterns: [1], [2], ..., [9])
• Input: m = 1, n = 2
• Output: 65 (9 one-dot + 56 two-dot patterns)
• Input: m = 2, n = 2
• Output: 56 (just two-dot patterns)

These examples show how patterns grow—let’s solve it!

Understanding the Problem: Counting Valid Patterns

To solve LeetCode 351 in Python, we need to: 1. Model the 3x3 grid and its jump rules. 2. Count all valid patterns for lengths m to n. 3. Handle jumps (e.g., 1-3 needs 2).

A naive approach might list every sequence, but with 9 dots and rules, that’s inefficient. Instead, we’ll use:

• Best Solution: Backtracking with symmetry—O(9!) time, O(9) space—smart and fast.
• Alternative Solution: Basic DFS—O(9!) time, O(9) space—simpler but less optimized.

Let’s dive into the backtracking solution—it’s the star!

Best Solution: Backtracking with Symmetry

Why This Is the Best Solution

Backtracking with symmetry is the top choice because it’s efficient—O(9!) time (all possible paths, reduced by symmetry) and O(9) space—and leverages the grid’s layout to avoid duplicate work. The grid has symmetry: corners (1, 3, 7, 9) behave similarly, edges (2, 4, 6, 8) do too, and the middle (5) is unique. By calculating one of each type and multiplying, we save effort. It’s like swiping once and copying the results!

How It Works

Backtracking is like trying every swipe and undoing it if it fails:

• Setup:
• List “jumps” where a middle dot is needed (e.g., 1-3 needs 2).
• Use a visited list to track used dots.
• Backtrack:
• Start at a dot.
• Try swiping to each unused dot, checking jump rules.
• Build patterns of length m to n, counting valid ones.
• Symmetry:
• Compute for one corner (1), multiply by 4.
• Compute for one edge (2), multiply by 4.
• Compute for middle (5), use as is.

It’s like exploring a maze with a rewind button!

Step-by-Step Example

For m = 1, n = 2:

• Setup: Jumps = {(1,3):2, (1,9):5, ...}, visited = [False]*10.
• Start at 1:
• Length 1: [1], valid, count = 1.
• Length 2: Try 2 ([1,2]), valid; try 3 ([1,3]), needs 2 (not yet), skip; try 4 ([1,4]), valid; etc.
• Symmetry:
• Corner (1): Count patterns, multiply by 4 (1, 3, 7, 9).
• Edge (2): Count, multiply by 4 (2, 4, 6, 8).
• Middle (5): Count once.
• Total: 9 (len=1) + 56 (len=2) = 65.

Let’s code it with a thorough breakdown!

Code with Explanation

Here’s the Python code, explained step-by-step:

Copy codeclass Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        # Define jumps - pairs where a middle dot must be used
        # Example: swiping from 1 to 3 needs 2 in between
        jumps = {
            (1,3): 2, (3,1): 2,  # 1-3 or 3-1 needs 2
            (1,7): 4, (7,1): 4,  # 1-7 or 7-1 needs 4
            (3,9): 6, (9,3): 6,  # 3-9 or 9-3 needs 6
            (7,9): 8, (9,7): 8,  # 7-9 or 9-7 needs 8
            (1,9): 5, (9,1): 5,  # 1-9 or 9-1 needs 5 (diagonal)
            (3,7): 5, (7,3): 5,  # 3-7 or 7-3 needs 5 (diagonal)
            (2,8): 5, (8,2): 5,  # 2-8 or 8-2 needs 5
            (4,6): 5, (6,4): 5   # 4-6 or 6-4 needs 5
        }

        # Create a list to track used dots (1-9), 0 is unused
        visited = [False] * 10

        # Backtracking function: curr is current dot, length is dots used
        def backtrack(curr, length):
            # If length is in our range (m to n), count this pattern
            if m <= length <= n:
                nonlocal count  # Use the count from outside
                count += 1      # Add 1 to total
            # If we’ve gone past n, stop this path
            if length >= n:
                return

            # Try swiping to every dot (1-9)
            for next_dot in range(1, 10):
                # If this dot isn’t used yet
                if not visited[next_dot]:
                    # Check if this swipe needs a middle dot
                    if (curr, next_dot) in jumps:
                        mid = jumps[(curr, next_dot)]  # Get middle dot
                        # If middle isn’t used, skip this move
                        if not visited[mid]:
                            continue
                    # Valid move! Mark dot as used
                    visited[next_dot] = True
                    # Recurse with next dot, increase length
                    backtrack(next_dot, length + 1)
                    # Undo (backtrack) to try other paths
                    visited[next_dot] = False

        # Count patterns starting from different dots
        count = 0

        # Corner dots (1, 3, 7, 9) - symmetric
        visited[1] = True  # Start at 1
        backtrack(1, 1)    # Begin with length 1
        visited[1] = False # Reset
        corner = count * 4 # Multiply by 4 for all corners

        # Edge dots (2, 4, 6, 8) - symmetric
        count = 0
        visited[2] = True  # Start at 2
        backtrack(2, 1)
        visited[2] = False
        edge = count * 4   # Multiply by 4 for all edges

        # Middle dot (5) - unique
        count = 0
        visited[5] = True  # Start at 5
        backtrack(5, 1)
        visited[5] = False
        middle = count     # No multiplication

        # Add all counts together
        return corner + edge + middle

Explanation

• Lines 3-12: jumps Dictionary
• This is our rulebook. Swiping from 1 to 3 passes over 2, so 2 must be used first. Same for 1 to 9 (needs 5). We list both directions (e.g., 1-3 and 3-1) for simplicity.

• Line 15: visited List
• A list with 10 spots (0-9), all set to False. When visited[3] is True, dot 3 is in our pattern. We use 1-9, leaving 0 unused.

• Lines 19-36: backtrack Function
• Parameters: curr is the current dot, length is how many dots we’ve swiped.
• Lines 21-23: If length is between m and n, add 1 to count. nonlocal count lets us modify the outer count.
• Lines 24-25: If length reaches n, stop—we don’t need longer patterns.
• Lines 28-36: Loop over dots 1-9:
• Line 30: If next_dot is False in visited, it’s free to use.
• Lines 31-34: If this swipe (e.g., 1 to 3) is in jumps, check the middle dot (2). If it’s False, skip this move.
• Lines 35-36: Valid swipe! Set next_dot to True, recurse with length + 1, then set it back to False to explore other paths.

• Lines 39-54: Main Logic
• Corner: Start at dot 1, count patterns, multiply by 4 (1, 3, 7, 9 are symmetric).
• Edge: Start at 2, count, multiply by 4 (2, 4, 6, 8 are symmetric).
• Middle: Start at 5, count once (5 is unique).
• Reset count and visited each time.

• Line 56: Sum all counts.

• Time Complexity: O(9!)—all possible paths, reduced by symmetry.
• Space Complexity: O(9)—visited list and recursion stack.

This solution is like a clever swipe planner—try, adjust, and count!

Alternative Solution: Basic DFS

Why an Alternative Approach?

The basic DFS (Depth-First Search) solution tries every pattern from every starting dot without symmetry. It’s O(9!) time and O(9) space too, but it doesn’t optimize, so it does more work. It’s simpler to follow—great for understanding DFS!

How It Works

• Setup: Same jumps and visited list.
• DFS: Start at each dot (1-9), explore all valid paths for lengths m to n.
• Count: Add up all patterns without shortcuts.

It’s like swiping everywhere without a plan—thorough but clear.

Step-by-Step Example

For m = 1, n = 1:

• Start at 1: [1], count = 1.
• Start at 2: [2], count = 2.
• ...
• Total: 9.

Code with Explanation

Copy codeclass Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        # Define jumps (same as before)
        jumps = {
            (1,3): 2, (3,1): 2,
            (1,7): 4, (7,1): 4,
            (3,9): 6, (9,3): 6,
            (7,9): 8, (9,7): 8,
            (1,9): 5, (9,1): 5,
            (3,7): 5, (7,3): 5,
            (2,8): 5, (8,2): 5,
            (4,6): 5, (6,4): 5
        }
        visited = [False] * 10

        # DFS function
        def dfs(curr, length):
            if m <= length <= n:
                nonlocal count
                count += 1
            if length >= n:
                return
            for next_dot in range(1, 10):
                if not visited[next_dot]:
                    if (curr, next_dot) in jumps and not visited[jumps[(curr, next_dot)]]:
                        continue
                    visited[next_dot] = True
                    dfs(next_dot, length + 1)
                    visited[next_dot] = False

        # Try every starting dot
        count = 0
        for start in range(1, 10):
            visited[start] = True
            dfs(start, 1)
            visited[start] = False
        return count

Explanation

• Lines 3-12: jumps—same rulebook as before.
• Line 15: visited—tracks used dots, all False initially.
• Lines 18-30: dfs—similar to backtrack:
• Count if length is in range.
• Stop at n.
• Try each next dot, skip invalid jumps, recurse, and backtrack.
• Lines 33-38: Loop over all 9 starting dots, count patterns from each.
• Time: O(9!)—no symmetry savings.
• Space: O(9)—recursion and visited.

It’s a full swipe adventure!

Comparing the Two Solutions

• Backtracking with Symmetry (Best):
• Time: O(9!), optimized by symmetry.
• Space: O(9).
• Pros: Faster, less repetition.
• Cons: More setup.
• Basic DFS (Alternative):
• Time: O(9!), no optimization.
• Space: O(9).
• Pros: Easier to code.
• Cons: More work.

Symmetry makes the difference!

Additional Examples and Edge Cases

• m=1, n=1: 9—one dot each.
• m=2, n=3: 56 + 248 = 304—two and three dots.
• m=9, n=9: 1—one way to use all 9.

Both solutions handle these well.

Complexity Breakdown

• Backtracking: Time O(9!), Space O(9).
• DFS: Time O(9!), Space O(9).

Symmetry reduces practical effort.

Key Takeaways

• Backtracking: Smart exploration—use symmetry!
• DFS: Full sweep—great for learning!
• Patterns: Rules add challenge.
• Python Tip: Lists and recursion shine—see [Python Basics](/python/basics).

Final Thoughts: Unlock Those Patterns

LeetCode 351: Android Unlock Patterns in Python is a swipe-tastic problem. Backtracking with symmetry is the efficient champ, while DFS builds a strong foundation. Want more? Check LeetCode 17: Letter Combinations or LeetCode 46: Permutations. Ready to swipe? Visit Solve LeetCode 351 on LeetCode and unlock those patterns today!