Is Beautiful Arrangement II easy or hard?

Beautiful Arrangement II is rated Medium on LeetCode. The difficulty comes from recognizing the constructive pattern that controls distinct differences. Once the alternating strategy is understood, the implementation is straightforward.

Beautiful Arrangement II Python/Java solution

Python, Java, C++, and JavaScript implementations typically follow the same greedy pattern. Use two indices representing the current low and high numbers, alternate placement for the first k+1 positions, then append the remaining numbers sequentially. The logic stays O(n) across all languages.

How to solve Beautiful Arrangement II in O(n)?

Create the first k+1 elements using an alternating pattern between low and high values such as 1, k+1, 2, k, 3, k-1. This produces k distinct adjacent differences. After generating that section, append the remaining numbers from k+2 to n in increasing order, which doesn't introduce new difference values.

What is the best approach for Beautiful Arrangement II?

The optimal approach uses a greedy alternating pattern with two pointers. Construct the first k+1 elements by alternating between the smallest and largest numbers to produce differences k, k-1, ..., 1. After that, append the remaining numbers sequentially. This guarantees exactly k distinct differences in O(n) time and O(1) space.

Is Beautiful Arrangement II asked at Google/Amazon/Meta?

Variants of constructive array and greedy pattern problems appear in interviews at large companies like Google, Amazon, and Meta. While this exact problem may not always appear verbatim, the idea of building sequences with controlled differences or constraints is common in algorithm interviews.

What data structure is used in Beautiful Arrangement II?

The solution mainly uses an array with simple pointer variables. Two-pointer techniques help alternate between low and high values during construction. No advanced data structures like heaps or hash maps are required.

What is the time complexity of Beautiful Arrangement II?

The optimal construction runs in O(n) time because each number from 1 to n is placed exactly once in the result array. No sorting, backtracking, or nested loops are required. Space complexity is O(1) aside from the output array since only a few pointers or counters are used.

Description Solution Video 10:11

667. Beautiful Arrangement II

Medium61.1% acceptance2 companies

Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the following requirement:

Suppose this list is answer = [a₁, a₂, a₃, ... , a_n], then the list [|a₁ - a₂|, |a₂ - a₃|, |a₃ - a₄|, ... , |a_n-1 - a_n|] has exactly k distinct integers.

Return the list answer. If there multiple valid answers, return any of them.

Example 1:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

Example 2:

Input: n = 3, k = 2
Output: [1,3,2]
Explanation: The [1,3,2] has three different positive integers ranging from 1 to 3, and the [2,1] has exactly 2 distinct integers: 1 and 2.

Constraints: