Beautiful Arrangement - Solution & Explanation
Problem Statement
Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i]is divisible byi.iis divisible byperm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
Example 1:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 15
Approach Overview
Problem Overview: Given an integer n, count how many permutations of numbers 1..n form a beautiful arrangement. A permutation is valid if for every position i, either perm[i] % i == 0 or i % perm[i] == 0. The goal is to explore permutations efficiently while enforcing this divisibility constraint.
Approach 1: Backtracking with Pruning (Time: O(n!), Space: O(n))
This approach builds the permutation one position at a time using backtracking. Start at position 1 and try placing every unused number from 1..n. Before placing a number x at position i, check the constraint x % i == 0 or i % x == 0. If the condition fails, skip immediately. A boolean array or bit mask tracks which numbers are already used. The recursion proceeds until position n, where a valid arrangement is counted.
The key optimization is pruning invalid placements early. Instead of generating all n! permutations, the algorithm only explores candidates that satisfy the divisibility rule. For small constraints (the problem limits n ≤ 15), this dramatically reduces the search space. This solution is simple to implement and performs well because many permutations are rejected early.
Approach 2: Dynamic Programming with Bitmasking (Time: O(n * 2^n), Space: O(2^n))
This method replaces recursion with dynamic programming and represents chosen numbers using a bitmask. Each DP state stores the number of valid arrangements for a specific mask of used numbers. The number of set bits in the mask determines the current position in the permutation.
For each mask, try placing a number x that has not been used yet. If it satisfies the divisibility rule for the next position, transition to a new mask with the corresponding bit set. Memoization ensures each mask is computed only once. Since there are 2^n masks and up to n transitions per state, the complexity becomes O(n * 2^n).
This approach is more structured than pure recursion and avoids repeated exploration of identical states. Bitmask DP is common for permutation counting problems where n ≤ 20. It also demonstrates strong understanding of state compression techniques used in many advanced interview problems.
Recommended for interviews: Backtracking with pruning is usually the expected solution because it directly models permutation generation and clearly shows constraint-based pruning. It demonstrates control over recursion and search space reduction. The bitmask DP approach is a strong follow-up optimization that highlights knowledge of state compression and dynamic programming, which can impress interviewers when discussing scalability.
Approach 1: Backtracking Approach
The idea is to generate permutations of the numbers from 1 to n and check if each permutation is a beautiful arrangement. This can be efficiently done using backtracking. While generating permutations, we can directly test the divisibility conditions to ensure they form a beautiful arrangement.
This solution uses bitmasking to mark the numbers that have been used. It recursively checks each position with available numbers. If a number can be placed at a position according to the rules, it tries to place the next number. If a full beautiful arrangement is achieved, it counts it.
Complexity
Time Complexity: O(k), where k are the valid permutations (worst-case roughly n!).
Space Complexity: O(n) due to the recursion stack.
Approach 2: Dynamic Programming Approach with Bitmasking
This approach involves using dynamic programming (DP) with bitmasking to efficiently count beautiful arrangements. By representing the set of visited numbers as a bitmask and using memoization, we can avoid redundant calculations.
This Python solution uses a top-down dynamic programming approach with memoization. The function dfs uses a bitmask to denote which integers have been placed, and iteratively places integers satisfying the beautiful arrangement condition.
Complexity
Time Complexity: O(n * 2^n) due to bitmask permutations.
Space Complexity: O(2^n) for the DP cache plus recursion stack.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(k), where k are the valid permutations (worst-case roughly n!). |
| Dynamic Programming Approach with Bitmasking | Time Complexity: O(n * 2^n) due to bitmask permutations. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(n!) | O(n) | Best for interview explanations and small n (≤15). Easy to implement and prunes invalid permutations early. |
| Dynamic Programming with Bitmask | O(n * 2^n) | O(2^n) | When you want a more optimized state-based approach and to avoid recomputing identical permutation states. |
Video Solution
Beautiful Arrangement | LeetCode 526 | C++, Java, Python • Knowledge Center • 15,558 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Beautiful Arrangement easy or hard?
How to solve Beautiful Arrangement in O(n * 2^n)?
What is the best approach for Beautiful Arrangement?
What data structure is used in Beautiful Arrangement?
What is the time complexity of Beautiful Arrangement?
Beautiful Arrangement Python or Java solution approach?
Is Beautiful Arrangement asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Beautiful Arrangement with our built-in code editor and test cases.
Practice on FleetCode