LeetCode 667: Beautiful Arrangement II

Problem Restatement

We are given two integers:

We need to construct an array containing every integer from 1 to n exactly once such that the set of absolute differences between neighboring elements contains exactly k distinct values.

For an array:

arr

the adjacent differences are:

|arr[i] - arr[i + 1]|

for all valid indices i.

Return any valid array.

Input and Output

Example function shape:

def constructArray(n: int, k: int) -> list[int]:
    ...

Examples

Consider:

n = 3
k = 1

One valid answer is:

[1, 2, 3]

The adjacent differences are:

|1 - 2| = 1
|2 - 3| = 1

The distinct difference set is:

{1}

So there is exactly one distinct difference.

Now consider:

n = 3
k = 2

One valid answer is:

[1, 3, 2]

The adjacent differences are:

|1 - 3| = 2
|3 - 2| = 1

The distinct difference set is:

{1, 2}

So there are exactly two distinct differences.

Another example:

n = 7
k = 3

One valid construction is:

[1, 4, 2, 3, 5, 6, 7]

The adjacent differences are:

3, 2, 1, 2, 1, 1

The distinct set is:

{1, 2, 3}

First Thought: Try All Permutations

A direct solution is to generate every permutation of:

1, 2, ..., n

and count the distinct adjacent differences.

This works for very small n, but the number of permutations is:

n!

which becomes impossible quickly.

We need a direct construction.

Key Insight

We want exactly:

k distinct differences

The important observation is:

Using alternating low and high numbers creates many distinct differences.

For example:

1, 5, 2, 4, 3

produces differences:

4, 3, 2, 1

This creates a decreasing sequence of distinct differences.

More generally, if we alternate between the smallest and largest remaining values, we create new differences step by step.

Constructing Exactly k Differences

Suppose we want:

k distinct differences

We can build the first k + 1 elements carefully so their differences are:

k, k - 1, k - 2, ..., 1

That gives exactly k distinct values.

After that, we append the remaining numbers in increasing order.

Those later differences are only:

1

which already exists in the set, so no new distinct difference is created.

Alternating Pattern

Use two pointers:

Build the first k + 1 numbers by alternating:

smallest, largest, next smallest, next largest, ...

This generates distinct differences:

k, k - 1, k - 2, ...

Then append the remaining values in increasing order.

Example Walkthrough

Suppose:

n = 7
k = 3

We use numbers:

1 to 4

for the alternating section.

Start:

left = 1
right = 4

Build:

1, 4, 2, 3

Differences:

3, 2, 1

Exactly three distinct values.

Now append the remaining numbers:

5, 6, 7

Final array:

[1, 4, 2, 3, 5, 6, 7]

The later differences are only 1 or 2, which are already present.

Algorithm

1. Create an empty result list.
2. Set:
   • left = 1
   • right = k + 1
3. Alternate between left and right:
   • Append left, increase left
   • Append right, decrease right
4. Continue until all values from 1 to k + 1 are used.
5. Append remaining values:
   • k + 2 to n
6. Return the result.

Correctness

The alternating construction uses exactly the numbers from 1 to k + 1.

At every step, the difference between consecutive elements decreases by 1.

For example:

1, k+1, 2, k, 3, ...

creates differences:

k, k-1, k-2, ...

Therefore, the first k adjacent differences are all distinct and equal to:

1, 2, ..., k

So the array already contains exactly k distinct differences.

The remaining values are appended in increasing order. Their adjacent differences are all 1, which is already included in the existing difference set. Therefore, no new distinct differences are introduced.

Every number from 1 to n appears exactly once, so the result is a valid permutation.

Thus, the algorithm constructs a permutation whose adjacent differences contain exactly k distinct values.

Complexity

Implementation

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 value in range(k + 2, n + 1):
            result.append(value)

        return result

Code Explanation

We begin with:

left = 1
right = k + 1

The alternating section uses numbers from:

1 to k + 1

Then we alternate between the smallest and largest remaining values:

result.append(left)
left += 1

and:

result.append(right)
right -= 1

This creates decreasing distinct differences.

For example:

1, 5, 2, 4, 3

produces:

4, 3, 2, 1

After all numbers in the alternating block are used, we append the remaining numbers normally:

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

These only create differences already present.

Finally:

return result

returns the constructed permutation.

Testing

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

def run_tests():
    s = Solution()

    arr = s.constructArray(3, 1)
    assert sorted(arr) == [1, 2, 3]
    assert distinct_differences(arr) == 1

    arr = s.constructArray(3, 2)
    assert sorted(arr) == [1, 2, 3]
    assert distinct_differences(arr) == 2

    arr = s.constructArray(7, 3)
    assert sorted(arr) == [1, 2, 3, 4, 5, 6, 7]
    assert distinct_differences(arr) == 3

    arr = s.constructArray(10, 4)
    assert sorted(arr) == list(range(1, 11))
    assert distinct_differences(arr) == 4

    arr = s.constructArray(2, 1)
    assert sorted(arr) == [1, 2]
    assert distinct_differences(arr) == 1

    print("all tests passed")

run_tests()

Test meaning: