Beautiful Arrangement II: Constructing k Distinct Differences

May 21, 20264 min read

leetcodeproblemmediumarrays

LeetCode 667: Beautiful Arrangement II asks you to construct an array of n distinct integers from 1 to n such that the absolute differences between consecutive elements produce exactly k distinct values. You can return any valid arrangement.

At first glance this looks like it requires brute-force search or backtracking. But there is a clean O(n) construction that builds the answer directly, no searching needed.

The first 3 elements are built by interleaving low and high values, producing 3 distinct differences. The remaining elements continue in ascending order.

Approach

The key insight is that you can create exactly k distinct differences by interleaving from both ends of the number range for the first k+1 elements.

Start with two pointers: lo = 1 and hi = k + 1. Alternate placing lo then hi, incrementing lo and decrementing hi each time. This produces consecutive differences of k, k-1, k-2, all the way down to 1. That gives you exactly k distinct difference values.

After placing k+1 elements, you have used numbers 1 through k+1. The remaining numbers from k+2 to n are placed in ascending order. Each consecutive pair in this tail differs by exactly 1, which is a difference you already counted. So no new distinct differences are introduced.

The result: exactly k distinct absolute differences, built in a single pass.

Drill array construction patterns with spaced repetition

The Python solution

def constructArray(n: int, k: int) -> list[int]:
    result = []
    lo, hi = 1, k + 1
    for i in range(k + 1):
        if i % 2 == 0:
            result.append(lo)
            lo += 1
        else:
            result.append(hi)
            hi -= 1
    for val in range(k + 2, n + 1):
        result.append(val)
    return result

The first loop places k+1 elements by alternating between lo (starting at 1) and hi (starting at k+1). On even indices we pick from the bottom, on odd indices from the top.
The differences between these interleaved elements are k, k-1, k-2, ..., 1, giving exactly k distinct values.
The second loop appends the remaining numbers k+2 through n in order. Each consecutive pair adds a difference of 1, which was already counted.

Why does interleaving produce exactly k distinct differences? The first pair differs by (k+1) - 1 = k. The next pair differs by (k+1) - 2 = k-1. Each new pair shrinks the gap by 1 until you reach a difference of 1. That is k distinct values: k, k-1, k-2, ..., 1.

Practice constructive array problems

Visual walkthrough

Step 1: Interleave low and high (k+1 = 4 elements)

Alternate between the smallest and largest unused values. This produces differences k, k-1, k-2, ..., 1 — giving exactly k distinct values.

Step 2: Fill remaining elements in ascending order

After placing k+1 elements, append the rest starting from k+2 in order. Each consecutive pair differs by 1 (already counted), so no new distinct differences are added.

Step 3: What if k = n-1? Full zigzag

When k = n-1, every element is placed by interleaving. The array [1, 5, 2, 4, 3] gives differences {4, 3, 2, 1} — exactly k=4 distinct values.

Complexity analysis

Metric	Value	Why
Time	O(n)	Single pass to build the array
Space	O(n)	The output array

The first loop runs k+1 times and the second runs n - k - 1 times, for a total of n iterations. No sorting, no hash sets, no extra data structures beyond the output array itself.

Building blocks

Constructive two-pointer interleaving

The core technique here is using two pointers moving toward each other to generate a specific sequence of differences. You pick from the low end, then the high end, then the low end again. This pattern shows up whenever you need to maximize or control the variation between consecutive elements.

lo, hi = 1, k + 1
for i in range(k + 1):
    if i % 2 == 0:
        result.append(lo)
        lo += 1
    else:
        result.append(hi)
        hi -= 1

This same interleaving idea appears in wiggle sort problems, where you need elements to alternate between peaks and valleys. Once you recognize the "pick from both ends" pattern, a whole family of construction problems becomes approachable.

Edge cases

k = 1: every consecutive pair must have the same absolute difference. Just return [1, 2, ..., n]. The interleaving step places only two elements (1, 2), then the rest follow in order.
k = n-1: you need every possible difference from 1 to n-1. The entire array is built by interleaving: [1, n, 2, n-1, 3, ...]. No ascending tail is appended.
n = 1: the only valid answer is [1]. There are no consecutive pairs, so k must be 0 (though the problem guarantees 1 <= k < n).

From understanding to recall

This problem rewards you for knowing the constructive interleaving pattern. If you have seen it before, the solution takes a couple of minutes. If you have not, you might spend a long time exploring backtracking or greedy heuristics that are harder to get right.

The fix is deliberate practice. Write the two-pointer interleaving loop from scratch. Trace through it with n=6, k=4 and verify the differences. Do it again tomorrow, and again in three days. After a few repetitions, the pattern becomes second nature. You see "construct an array with specific difference properties" and the lo/hi interleaving loop appears in your mind immediately.

Constructive array building is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning each one individually and reinforcing it with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Beautiful Arrangement - The predecessor problem using backtracking
Next Permutation - Another array construction problem
Wiggle Sort II - Similar interleaving of values

Try CodeBricks free