667. Beautiful Arrangement II

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.

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.

Solution: Divide and Conquer

When k = n-1, a valid construction is {1, n, 2, n-1, 3, n-2...}. One way to see this is, we need to have a difference of n-1, which means we need 1 and n adjacent, etc.

If k < n-1, we can consider construct the first k elements, then add the rest in sorted order.

Note: Need to check the rest should be in ascending order or descending order.

vector<int> constructArray(int n, int k) {
    vector<int> ans;
    int left = 1, right = n;

    int i = 0;
    while(i < k) {
        if (i%2 == 0) {
            ans.push_back(left++);
        } else {
            ans.push_back(right--);
        }
        i += 1;
    }

    if (i%2 == 1) {
        for (int j=left; j <= right; j++) ans.push_back(j);
    } else {
        for (int j=right; j >= left; j--) ans.push_back(j);
    }

    return ans;
}