LeetCode 667 - Beautiful Arrangement II

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to construct a permutation of the integers from 1 to n such that the sequence of absolute differences between adjacent elements contains exactly k distinct values.

If the constructed array is:

$$[a_1, a_2, a_3, \dots, a_n]$$

then we look at the adjacent absolute differences:

$$[|a_1-a_2|, |a_2-a_3|, |a_3-a_4|, \dots, |a_{n-1}-a_n|]$$

The requirement is that this difference array must contain exactly k distinct integers.

The input consists of two integers:

n, the size of the permutation
k, the required number of distinct adjacent differences

The output must be a valid permutation of integers from 1 through n.

The constraints are:

1 <= k < n <= 10^4

These constraints are important because they immediately rule out any brute-force permutation generation approach. The number of permutations grows factorially, which becomes impossible even for moderate values of n.

The problem guarantees:

A valid answer always exists
We only need to return any valid construction

Several edge cases are important:

When k = 1, we need exactly one distinct difference. A simple increasing sequence works because all adjacent differences are 1.
When k = n - 1, we need the maximum possible number of distinct differences. This requires carefully alternating values to generate differences 1, 2, 3, ..., n-1.
Small inputs such as n = 2, k = 1 can expose off-by-one errors.
Incorrect alternating logic can accidentally create repeated differences too early, reducing the distinct count below k.

Approaches

Brute Force Approach

A brute-force solution would generate all possible permutations of numbers from 1 to n. For each permutation, we would compute the adjacent absolute differences and count how many distinct values appear.

This approach is correct because it exhaustively checks every possible arrangement and returns one that satisfies the condition.

However, the time complexity is catastrophic. There are n! permutations, and for each one we must compute up to n-1 differences. Even for n = 10, this becomes impractical.

Since n can be as large as 10^4, brute force is completely infeasible.

Optimal Insight

The key observation is that we do not need to search for a valid arrangement. We can directly construct one.

To create exactly k distinct adjacent differences, we can deliberately generate the differences:

$$k, k-1, k-2, \dots, 1$$

One elegant way to do this is to alternate between the smallest and largest remaining numbers.

For example, suppose we use numbers from 1 to k+1:

$$1, k+1, 2, k, 3, k-1, \dots$$

The adjacent differences become:

$$k, k-1, k-2, \dots$$

which produces exactly k distinct values.

After constructing this special alternating section, we append the remaining numbers in increasing order. Appending in sorted order only introduces difference 1, which already exists, so no new distinct differences are created.

This gives a direct linear-time construction.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n)	O(n)	Generates every permutation and checks differences
Optimal	O(n)	O(n)	Direct mathematical construction using alternating endpoints

Algorithm Walkthrough

Initialize two pointers:

left = 1
right = k + 1

We only need the first k + 1 numbers to generate exactly k distinct differences. 2. Alternate between taking numbers from the left and right ends.

Append:

left
right
left + 1
right - 1
and so on

This alternating pattern generates decreasing differences:

k
k - 1
k - 2
...
1

Continue until all numbers from 1 through k + 1 are used.
Append the remaining numbers from k + 2 through n in increasing order.

This step is important because sorted consecutive values only create adjacent difference 1, which is already part of the distinct set. 5. Return the constructed array.

Why it works

The alternating construction on numbers 1 through k+1 produces adjacent differences exactly equal to:

$$k, k-1, k-2, \dots, 1$$

These are all distinct, so we obtain exactly k distinct differences.

Appending the remaining numbers in sorted order does not introduce any new differences beyond 1, so the total number of distinct differences remains exactly k.

Python Solution

from typing import List

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        result = []

        left = 1
        right = k + 1

        while left <= right:
            result.append(left)
            left += 1

            if left <= right:
                result.append(right)
                right -= 1

        for num in range(k + 2, n + 1):
            result.append(num)

        return result

The implementation follows the construction strategy directly.

We first build the alternating portion using two pointers. The left pointer starts at 1, while the right pointer starts at k + 1.

At each iteration:

We append the current smallest unused value.
Then we append the current largest unused value.

This alternating structure creates the desired sequence of distinct differences.

Once the first k + 1 numbers are exhausted, we append the remaining values sequentially. Since consecutive integers differ by 1, this does not introduce additional distinct differences.

The algorithm runs in linear time because each number is appended exactly once.

Go Solution

func constructArray(n int, k int) []int {
    result := make([]int, 0, n)

    left := 1
    right := k + 1

    for left <= right {
        result = append(result, left)
        left++

        if left <= right {
            result = append(result, right)
            right--
        }
    }

    for num := k + 2; num <= n; num++ {
        result = append(result, num)
    }

    return result
}

The Go implementation mirrors the Python logic closely.

Slices are used instead of Python lists. We preallocate capacity with make([]int, 0, n) to avoid unnecessary reallocations during appends.

Go integers are fully sufficient for this problem because the maximum value is only 10^4, so integer overflow is not a concern.

Worked Examples

Example 1

Input:

n = 3, k = 1

We initialize:

left = 1
right = 2

Step	Action	Result
1	Append `1`	`[1]`
2	Append `2`	`[1,2]`

Now append remaining numbers:

Step	Action	Result
3	Append `3`	`[1,2,3]`

Differences:

$$|1-2| = 1$$

$$|2-3| = 1$$

Distinct differences:

$${1}$$

Exactly one distinct value exists.

Example 2

Input:

n = 3, k = 2

We initialize:

left = 1
right = 3

Step	Action	Result
1	Append `1`	`[1]`
2	Append `3`	`[1,3]`
3	Append `2`	`[1,3,2]`

Differences:

$$|1-3| = 2$$

$$|3-2| = 1$$

Distinct differences:

$${1,2}$$

Exactly two distinct values exist.

Additional Example

Input:

n = 7, k = 4

Initial range used for alternating:

$$1 \text{ through } 5$$

Construction:

Step	Action	Result
1	Append `1`	`[1]`
2	Append `5`	`[1,5]`
3	Append `2`	`[1,5,2]`
4	Append `4`	`[1,5,2,4]`
5	Append `3`	`[1,5,2,4,3]`

Append remaining values:

Step	Action	Result
6	Append `6`	`[1,5,2,4,3,6]`
7	Append `7`	`[1,5,2,4,3,6,7]`

Differences:

$$4, 3, 2, 1, 3, 1$$

Distinct values:

$${1,2,3,4}$$

Exactly four distinct differences exist.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each integer from `1` to `n` is processed exactly once
Space	O(n)	The output array stores `n` integers

The algorithm is highly efficient because it constructs the answer directly without searching or backtracking. Every element is appended once, giving linear time complexity. The only extra memory used is the output array itself.

Test Cases

from typing import List

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        result = []

        left = 1
        right = k + 1

        while left <= right:
            result.append(left)
            left += 1

            if left <= right:
                result.append(right)
                right -= 1

        for num in range(k + 2, n + 1):
            result.append(num)

        return result

def distinct_differences(arr):
    return len(set(abs(arr[i] - arr[i + 1]) for i in range(len(arr) - 1)))

sol = Solution()

# Example 1
arr = sol.constructArray(3, 1)
assert distinct_differences(arr) == 1  # minimal distinct differences

# Example 2
arr = sol.constructArray(3, 2)
assert distinct_differences(arr) == 2  # maximum differences for n=3

# Smallest valid input
arr = sol.constructArray(2, 1)
assert distinct_differences(arr) == 1  # smallest boundary case

# Maximum possible k
arr = sol.constructArray(10, 9)
assert distinct_differences(arr) == 9  # all possible differences

# Middle-range k
arr = sol.constructArray(7, 4)
assert distinct_differences(arr) == 4  # alternating construction

# Larger n with small k
arr = sol.constructArray(20, 2)
assert distinct_differences(arr) == 2  # mostly sequential numbers

# Larger n with moderate k
arr = sol.constructArray(100, 25)
assert distinct_differences(arr) == 25  # stress test

# Ensure permutation validity
arr = sol.constructArray(50, 10)
assert sorted(arr) == list(range(1, 51))  # all numbers used exactly once

Test Summary

Test	Why
`n=3, k=1`	Validates minimal distinct difference case
`n=3, k=2`	Validates maximum distinct differences for small input
`n=2, k=1`	Tests smallest valid constraints
`n=10, k=9`	Tests maximum possible `k`
`n=7, k=4`	Verifies alternating construction logic
`n=20, k=2`	Ensures extra sequential numbers do not add differences
`n=100, k=25`	Stress test for larger input
Permutation validity check	Ensures no duplicates or missing numbers

Edge Cases

Case 1: `k = 1`

When k equals 1, we need exactly one distinct adjacent difference. A naive alternating strategy could accidentally create multiple differences.

For example:

[1,3,2]

produces differences {2,1}, which is invalid.

Our implementation handles this correctly because the alternating range only includes 1 and 2. The remaining numbers are appended sequentially, resulting in:

[1,2,3,4,...]

All adjacent differences are 1.

Case 2: `k = n - 1`

This is the maximum possible number of distinct differences.

A buggy implementation may fail to generate every difference from 1 through n-1.

Our alternating construction guarantees:

1, n, 2, n-1, 3, n-2, ...

which produces:

n-1, n-2, n-3, ...

ensuring every possible difference appears exactly once.

Case 3: Odd Number of Elements in Alternating Section

When k + 1 is odd, the left and right pointers eventually meet.

Incorrect pointer handling can duplicate the middle element or skip it entirely.

For example:

n = 7, k = 4

uses numbers 1..5.

The implementation carefully checks:

if left <= right:

before appending from the right side, preventing duplicates and ensuring all numbers are used exactly once.

LeetCode 667 - Beautiful Arrangement II

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Insight

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Additional Example

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Case 1: k = 1

Case 2: k = n - 1

Case 3: Odd Number of Elements in Alternating Section

Case 1: `k = 1`

Case 2: `k = n - 1`