LeetCode 667 - Beautiful Arrangement II

https://leetcode.com/problems/beautiful-arrangement-ii/description/

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.

Note:

1. The n and k are in the range 1 <= k < n <= 104.

https://leetcode.com/problems/beautiful-arrangement-ii/discuss/106948/C++-Java-Clean-Code-4-liner

if you have n number, the maximum k can be n - 1;
if n is 9, max k is 8.
This can be done by picking numbers interleavingly from head and tail,

// start from i = 1, j = n;
// i++, j--, i++, j--, i++, j--

i: 1   2   3   4   5
j:   9   8   7   6
out: 1 9 2 8 3 7 4 6 5
dif:  8 7 6 5 4 3 2 1

Above is a case where k is exactly n - 1
When k is less than that, simply lay out the rest (i, j) in incremental
order(all diff is 1). Say if k is 5:

     i++ j-- i++ j--  i++ i++ i++ ...
out: 1   9   2   8    3   4   5   6   7
dif:   8   7   6   5    1   1   1   1 

    public int[] constructArray(int n, int k) {
        int[] res = new int[n];
        for (int i = 0, l = 1, r = n; l <= r; i++)
            res[i] = k > 1 ? (k-- % 2 != 0 ? l++ : r--) : l++;
        return res;
    }

https://leetcode.com/problems/beautiful-arrangement-ii/discuss/106965/Python-Straightforward-with-Explanation

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 1and n adjacent; then, we need a difference of n-2, etc.

This leads to the following idea: we will put [1, 2, ...., n-k-1] first, and then we have N = k+1 adjacent numbers left, of which we want k different differences. This is just the answer above translated by n-k-1: we'll put [n-k, n, n-k+1, n-1, ....] after.

https://leetcode.com/problems/beautiful-arrangement-ii/discuss/106971/Java-easy-to-understand-with-explanation
1,n,2,n-1,3,n-2,4... ==> Diff: n-1, n-2, n-3, n-4, n-5...
By following this pattern, k numbers will have k-1 distinct difference values;
and all the rest numbers should have |ai - a_i-1| = 1;
In total, we will have k-1+1 = k distinct values.

https://leetcode.com/problems/beautiful-arrangement-ii/discuss/106963/Java-simple-solution

public int[] constructArray(int n, int k) {
    //number 1-n. if ascending order, always has diff = 1. 
    //reorder to be 1, k+1, 2, k, 3 ... so have diff = k,k-1,k-2....1
    int[] res = new int[n];
    int inc = 1, dec = k+1;
    for(int i=0;i<=k;i++){
        if(i%2==0)
            res[i] = inc++;
        else
            res[i] = dec--;
    }
   
    for(int i=k+1;i<n;i++){
        res[i] = i+1;
    }
    
    return res;
}

X.

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

Also, when $\text{k = 1}$, a valid construction is $\text{[1, 2, 3, ..., n]}$. So we have a construction when $\text{n-k}$ is tiny, and when it is large. This leads to the idea that we can stitch together these two constructions: we can put $\text{[1, 2, ..., n-k-1]}$ first so that $\text{n}$ is effectively $\text{k+1}$, and then finish the construction with the first $\text{"k = n-1"}$method.

For example, when $\text{n = 6}$ and $\text{k = 3}$, we will construct the array as $\text{[1, 2, 3, 6, 4, 5]}$. This consists of two parts: a construction of $\text{[1, 2]}$ and a construction of $\text{[1, 4, 2, 3]}$ where every element had $\text{2}$ added to it (i.e. $\text{[3, 6, 4, 5]}$).

Algorithm

As before, write $\text{[1, 2, ..., n-k-1]}$ first. The remaining $\text{k+1}$ elements to be written are $\text{[n-k, n-k+1, ..., n]}$, and we'll write them in alternating head and tail order.

When we are writing the $i^{th}$ element from the remaining $\text{k+1}$, every even $i$ is going to be chosen from the head, and will have value $\text{n-k + i//2}$. Every odd $i$ is going to be chosen from the tail, and will have value $\text{n - i//2}$.

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

X. Brute Force

• Time Complexity: $O(n!)$ to generate every permutation in the outer loop, then $O(n)$ work to check differences. In total taking $O(n* n!)$ time.
• Space Complexity: $O(n)$. We use $\text{seen}$ to store whether we've seen the differences, and each generated permutation has a length equal to $\text{n}$.

    private ArrayList<ArrayList<Integer>> permutations(int[] nums) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        permute(ans, nums, 0);
        return ans;
    }

    private void permute(ArrayList<ArrayList<Integer>> ans, int[] nums, int start) {
        if (start >= nums.length) {
            ArrayList<Integer> cur = new ArrayList<Integer>();
            for (int x : nums) cur.add(x);
            ans.add(cur);
        } else {
            for (int i = start; i < nums.length; i++) {
                swap(nums, start, i);
                permute(ans, nums, start+1);
                swap(nums, start, i);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private int numUniqueDiffs(ArrayList<Integer> arr) {
        boolean[] seen = new boolean[arr.size()];
        int ans = 0;

        for (int i = 0; i < arr.size() - 1; i++) {
            int delta = Math.abs(arr.get(i) - arr.get(i+1));
            if (!seen[delta]) {
                ans++;
                seen[delta] = true;
            }
        }
        return ans;
    }

    public int[] constructArray(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i+1;
        }
        for (ArrayList<Integer> cand : permutations(nums)) {
            if (numUniqueDiffs(cand) == k) {
                int[] ans = new int[n];
                int i = 0;
                for (int x : cand) ans[i++] = x;
                return ans;
            }
        }
        return null;
    }