How do you solve Beautiful Arrangement II on LeetCode?

Beautiful Arrangement II (LeetCode #667) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a pattern to fill the array can simplify the problem significantly.

What is the time complexity of Beautiful Arrangement II?

The optimal solution for Beautiful Arrangement II runs in O(n) time and uses O(n) space. The time complexity is O(n) because we are filling the array in a single pass. The space complexity is also O(n) due to the output array.

What is the brute force solution for Beautiful Arrangement II?

The brute force approach for Beautiful Arrangement II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all permutations of the numbers from 1 to n and checking each permutation to see if it meets the requirement of having exactly k distinct differences. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Beautiful Arrangement II?

Beautiful Arrangement II uses the following concepts: Array, Math. The recommended patterns to study are: Array, Greedy.

What are the interview tips for Beautiful Arrangement II?

Always start with a brute-force approach to understand the problem better. Look for patterns in the problem that can lead to a more efficient solution. Be prepared to explain your thought process clearly, especially when transitioning from brute force to optimal solutions.

What are common mistakes when solving Beautiful Arrangement II?

Generating all permutations without realizing a direct construction is possible. Not considering edge cases where k is close to n.

#667

Beautiful Arrangement II

Medium

ArrayMathArrayGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of generating permutations, we can construct the array directly. By placing numbers in a specific pattern, we can control the distinct differences without needing to check all combinations.

⚙️

Algorithm

3 steps

1Step 1: Start with an empty list and fill it with numbers from 1 to n.
2Step 2: For the first k elements, place them in an alternating high-low pattern to create k distinct differences.
3Step 3: Fill the remaining elements in sequential order to maintain the distinct differences.

solution.py14 lines

1def beautifulArrangementII(n, k):
2    answer = [0] * n
3    left, right = 1, n
4    for i in range(k):
5        if i % 2 == 0:
6            answer[i] = left
7            left += 1
8        else:
9            answer[i] = right
10            right -= 1
11    for i in range(k, n):
12        answer[i] = left
13        left += 1
14    return answer

ℹ

Complexity note: The time complexity is O(n) because we are filling the array in a single pass. The space complexity is also O(n) due to the output array.

1Using a pattern to fill the array can simplify the problem significantly.
2Understanding how to control the distinct differences is key to solving this problem efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.