Solution: Beautiful Arrangement II

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #667 (Medium): Beautiful Arrangement II

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

---

Examples:

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:

• The n and k are in the range 1 <= k < n <= 10^4.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

For this problem, we have to think about the nature of the range of possible values for k and their matching arrays. The smallest value of k possible is obviously 1, which can be achieved by a strictly increasing (or decreasing) array. Thinking about the largest possible value for k, however, is slightly more challenging.

First, we can consider the range of values in our array, which is [1, n]. The largest possible absolute difference of any two numbers in that range would obviously be the difference between the two extremes, 1 and n, which is n - 1. Since the smallest possible absolute difference is obviously 1, then it would appear to perhaps be possible to achieve each difference in the range [1, n - 1], or a k value of n - 1.

But is this actually possible?

Let's take n = 5 and k = 4 for example. The only possible way to get the absolute difference of 4 would be for 1 and 5 to be consecutive. After that there are two possibilities for next smallest absolute difference of 3, which are 1 & 4 or 2 & 5. Since the 1 and 5 are already next to each other, that means we can achieve this second step with either [1,5,2] or [4,1,5] (or their reverses).

Continuing this trend along, we can gradually see that we can indeed achieve the maximum k value of n - 1 by zig-zagging back and forth between the remaining extremes as we add them to our array. In the previous example, one such example would be [1,5,2,4,3].

The question then remains how we go about achieving some medium value of k larger than 1 but smaller than n - 1. The answer to that lies in considering the array to be made of two parts. In the first part, [1, k+1], we can achieve our k number of absolute differences, then we can simply fill in the remaining range, [k+2, n], with the ideal incrementing values without increasing the value of k.

For example, if we have n = 8 and k = 4, we would build the first part the same as the last example, [1,5,2,4,3], then we would add on the remaining values in increasing order, [6,7,8], to make the wole array, [1,5,2,4,3,6,7,8].

Examples of each variation of k when n = 8:

To achieve the zig-zag fill, we can use variables for the top and bottom values of our first part (a, z), then use a modulo operation (i % 2) to alternate between the two options, remembering to increment/decrement the respective variables each time they're used.

A slightly easier to visualize (but harder to code) version of the solution similarly involves using the same zig-zag for the first k elements, but with the full range of n numbers, and then moving in ideal fashion (either increasing or decreasing by 1, depending on whether k is even or odd) to fill the remaining elements of the array.

Examples of each alternate variation of k when n = 8:

---

Implementation:

The are only minor differences between each of the four languages.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var constructArray = function(n, k) {
    let ans = new Array(n)
    for (let i = 0, a = 1, z = k + 1; i <= k; i++)
        ans[i] = i % 2 ? z-- : a++
    for (let i = k + 1; i < n;)
        ans[i] = ++i
    return ans
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans, a, z = [0] * n, 1, k + 1
        for i in range(k+1):
            if i % 2:
                ans[i] = z
                z -= 1
            else:
                ans[i] = a
                a += 1
        for i in range(k+1,n):
            ans[i] = i + 1
        return ans

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        for (int i = 0, a = 1, z = k + 1; i <= k; i++)
            ans[i] = i % 2 == 1 ? z-- : a++;
        for (int i = k+1; i < n;)
            ans[i] = ++i;
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        for (int i = 0, a = 1, z = k + 1; i <= k; i++)
            ans[i] = i % 2 ? z-- : a++;
        for (int i = k+1; i < n; i++)
            ans[i] = i + 1;
        return ans;
    }
};