LeetCode 526: Beautiful Arrangement Solution in Python – A Step-by-Step Guide

What Is LeetCode 526: Beautiful Arrangement?

In LeetCode 526: Beautiful Arrangement, you’re given an integer n, and your task is to count the number of beautiful arrangements of numbers 1 to n. An arrangement is beautiful if, for every position i (1-based), the number at position i either divides i or is divisible by i. For example, with n = 2, there are 2 arrangements: [1, 2] and [2, 1]. This problem tests permutation generation with constraints, related to LeetCode 46: Permutations.

Problem Statement

• Input: Integer n.
• Output: Integer—number of beautiful arrangements.
• Rules: Use numbers 1 to n exactly once; each position i must satisfy divisibility condition.

Constraints

• 1 <= n <= 15

Examples

• Input: n = 2
• Output: 2
• Arrangements: [1, 2] (1%1=0, 2%2=0), [2, 1] (2%1=0, 1%2=1 but 2%1=0).
• Input: n = 1
• Output: 1
• Arrangement: [1] (1%1=0).
• Input: n = 3
• Output: 3
• Arrangements: [1, 2, 3], [2, 1, 3], [3, 2, 1].

Understanding the Problem: Crafting Beautiful Arrangements

To solve LeetCode 526: Beautiful Arrangement in Python, we need to count all permutations of numbers 1 to n where each position i (1-based) satisfies either num[i-1] % i == 0 or i % num[i-1] == 0. A naive approach might generate all n! permutations and check each, but with n up to 15 (15! ≈ 1.3 trillion), that’s impractical. We’ll explore:

• Best Solution (Backtracking with Visited Tracking): O(k) time (k = number of valid arrangements), O(n) space—efficient and intuitive.
• Alternative Solution (DP with Bitmask): O(n * 2ⁿ) time, O(2ⁿ) space—systematic but complex.

Let’s dive into the backtracking solution with a friendly breakdown!

Best Solution: Backtracking with Visited Tracking

Why Backtracking Wins

The backtracking with visited tracking is the best for LeetCode 526 because it builds arrangements incrementally, pruning invalid paths early, and runs in O(k) time (where k is the number of valid arrangements, much less than n!), using O(n) space. It’s like exploring a maze of numbers, backtracking when we hit a dead end!

How It Works

Think of this as an arrangement-building game:

• Step 1: Track Used Numbers:
• Use a visited set or array to mark numbers 1 to n.
• Step 2: Recursive Backtracking:
• For each position pos, try each unused number.
• Check divisibility: num % (pos+1) == 0 or (pos+1) % num == 0.
• If valid, mark used, recurse to next position, then unmark.
• Step 3: Count Arrangements:
• Increment count when pos reaches n.
• Why It Works:
• Explores only valid permutations.
• Backtracking ensures all possibilities.

It’s like a number-arranging explorer!

Step-by-Step Example

Example: n = 2

• Init: visited = set(), count = 0.
• Step 1: pos = 0:
• Try 1: 1%1=0, add 1, pos = 1:
• Try 2: 2%2=0, add 2, pos = 2, count += 1 ([1, 2]).
• Remove 2.
• Remove 1.
• Try 2: 2%1=0, add 2, pos = 1:
• Try 1: 1%2=1 but 2%1=0, add 1, pos = 2, count += 1 ([2, 1]).
• Remove 1.
• Remove 2.
• Result: count = 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def countArrangement(self, n: int) -> int:
        # Step 1: Initialize count and visited
        self.count = 0
        visited = set()

        # Step 2: Backtracking helper
        def backtrack(pos):
            if pos == n:  # Full arrangement found
                self.count += 1
                return

            # Try each number from 1 to n
            for num in range(1, n + 1):
                if num not in visited:
                    # Check divisibility condition
                    if num % (pos + 1) == 0 or (pos + 1) % num == 0:
                        visited.add(num)
                        backtrack(pos + 1)
                        visited.remove(num)

        # Step 3: Start backtracking
        backtrack(0)
        return self.count

• Line 4: Count as instance variable for recursion.
• Line 5: Set to track used numbers.
• Lines 8-10: Base case: increment count when all positions filled.
• Lines 13-18: For each position:
• Try unused numbers, check condition, recurse, backtrack.
• Line 21: Start from position 0.
• Time Complexity: O(k)—k valid arrangements, typically much less than n!.
• Space Complexity: O(n)—visited set and recursion stack.

It’s like a beautiful arrangement counter!

Alternative Solution: Dynamic Programming with Bitmask

Why an Alternative Approach?

The DP with bitmask solution uses a state-based approach, tracking used numbers with a bitmask and building arrangements systematically. It’s O(n * 2ⁿ) time and O(2ⁿ) space—more predictable but complex and slower for small n. Great for DP enthusiasts!

How It Works

Picture this as a state-building puzzle:

• Step 1: Define dp[mask]: Count of arrangements using numbers in mask.
• Step 2: Base case—dp[0] = 1 (empty set).
• Step 3: Iterate masks, add numbers, check condition.
• Step 4: Return dp[(1<<n)-1]< mark="">—all numbers used.</n)-1]<>

It’s like a bitmask arrangement builder!

Step-by-Step Example

Example: n = 2

• Init: dp = [1, 0, 0, 0] (mask 0 to 3).
• Mask 0: Try 0 (1), 1%1=0, dp[1] += dp[0] = 1.
• Try 1 (2), 2%1=0, dp[2] += dp[0] = 1.
• Mask 1 (0 used): Try 1 (2), 2%2=0, dp[3] += dp[1] = 1.
• Mask 2 (1 used): Try 0 (1), 1%2=1 but 2%1=0, dp[3] += dp[2] = 2.
• Result: dp[3] = 2.

Code for DP Approach

class Solution:
    def countArrangement(self, n: int) -> int:
        # Step 1: Initialize DP array
        dp = [0] * (1 << n)
        dp[0] = 1

        # Step 2: Iterate all masks
        for mask in range(1 << n):
            count = bin(mask).count('1')  # Number of 1s (position)
            for i in range(n):
                if not (mask & (1 << i)):  # If i-th bit not set
                    num = i + 1
                    pos = count + 1
                    if num % pos == 0 or pos % num == 0:
                        dp[mask | (1 << i)] += dp[mask]

        # Step 3: Return count for full mask
        return dp[(1 << n) - 1]

• Line 4: DP array for all subsets.
• Line 5: Base case: empty set = 1.
• Lines 8-13: For each mask, try adding unused numbers, check condition.
• Line 16: Full mask result.
• Time Complexity: O(n * 2ⁿ)—all masks and numbers.
• Space Complexity: O(2ⁿ)—DP array.

It’s a bitmask arrangement master!

Comparing the Two Solutions

• Backtracking (Best):
• Pros: O(k), O(n), fast for small k.
• Cons: Recursive logic.
• DP with Bitmask (Alternative):
• Pros: O(n * 2ⁿ), systematic.
• Cons: Slower, more space.

Backtracking wins for efficiency!

Additional Examples and Edge Cases

• n = 1: 1.
• n = 4: 8.
• n = 15: 24679.

Backtracking handles them all!

Complexity Recap

• Backtracking: Time O(k), Space O(n).
• DP: Time O(n * 2ⁿ), Space O(2ⁿ).

Backtracking’s the speed champ!

Key Takeaways

• Backtracking: Prune and conquer—learn at Python Basics!
• DP: Bitmask power.
• Permutations: Conditions add fun.
• Python: Sets or bits, your pick!

Final Thoughts: Arrange Beautifully!

LeetCode 526: Beautiful Arrangement in Python is a delightful backtracking challenge. Backtracking with visited tracking is your fast track, while DP with bitmask offers a systematic twist. Want more? Try LeetCode 46: Permutations or LeetCode 47: Permutations II. Ready to arrange? Head to Solve LeetCode 526 on LeetCode and count those beauties today!