✅ Beautiful Arrangement II | Multiple Approaches Explained with Examples !
The problem statement asks us to find a permutation of 1 to n such that there are k Unique Absolute Adjacent Difference (let\'s call it UAAD henceforth). We mus
The problem statement asks us to find a permutation of `1 to n` such that there are `k` Unique Absolute Adjacent Difference (let\'s call it **UAAD** henceforth). We must realize that with `n` elements, we can form any permutation for `k` UAADs such that `1 <= k < n`. \n\nThe solution for this problem is mostly observation based. I will suggest you to try out some examples before moving on to the explanation below.\n\n---\n\n\u2714\uFE0F ***Solution - I***\n\nWe need to find permutation with `k` UAAD. This means we can make a permutation such that the set of UAADs are `k, k-1, k-2, ..., 2, 1`. \n\n* So we can start the permutation with `1`.\n* Choose the next element such that the absolute difference between them is `k`. \n* Now, choose the next element such that the absolute difference between it & previous element is `k - 1`.\n* And continue so on till absolute difference is 1. Thereafter, we just fill the remaining elements of array such that all of them have absolute difference of 1 (Meaning rest all elements are consecutive).\n\n```\nBelow are some examples which will provide better understanding -\n\nFor eg. \n1. let n = 10, k = 4\npermutation                           =>       [1, 5, 2, 4, 3, 6, 7, 8, 9, 10]\nUAADs(abs(arr[i] - arr[i - 1]))       =>       [X, 4, 3, 2, 1, 3, 1, 1, 1, 1]\n\n\n2. n = 10, k = 5\npermutation                           =>       [1, 6, 2, 5, 3, 4, 7, 8, 9, 10]\nUAADs                                 =>       [X, 5, 4, 3, 2, 1, 3, 1, 1, 1]\n\n\n3. n = 9, k = 8\npermutation                           =>       [1, 9, 2, 8, 3, 7, 4, 6, 5]\nUAADs                                 =>       [X, 8, 7, 6, 5, 4, 3, 2, 1]\n\n\n4. n = 15, k = 6\npermutation                           =>       [1, 7, 2, 6, 3, 5, 4, 8, 9, 10, 11, 12, 13, 14, 15]\nUAADs                                 =>       [X, 6, 5, 4, 3, 2, 1, 4, 1,  1,  1,  1,  1,  1,  1]\n\nAs we can see from above examples, the approach is like maintaining two pointers: l = 1, r = k + 1.\n1. We assign 1st index as \'l\' and increment \'l\'. Then assign 2nd index as \'r\' and decrement \'r\'.\n2. Assign 3rd index as \'l\' and increment it. Assign 4th index as \'r\' and decrement it.\nWe continue this process till first k index are assigned in this manner.\n```\n\n---\n\nThe implementation of above idea is given below -\n\n**C++**\n```\nvector<int> constructArray(int n, int k) {\n    vector<int> ans(n);\n    int l = 1, r = k + 1, i = 0;\n    while(i < k)   // first k elements will be such there are k unique UAADs\n        ans[i++] = l++, ans[i++] = r--;\n    if(l == r) ans[i++] = r; // required for case when k is even\n    while(i < n) ans[i++] = i + 1; // rest of last elements will be consecutive having adjacent difference of 1\n\treturn ans;\n}\n```\n\n***Time Complexity :*** **`O(N)`**, we only iterate once from `0 to n-1`.\n***Space Complexity :*** **`O(N)`**, required for storing the answer\n\n---\n---\n\n\u2714\uFE0F ***Solution - II***\n\nIn this, the idea is the same as above, only the way numbers are chosen is different.\n\nHere, we choose the numbers as - `1, n, 2, n - 1, 3, n - 2, ...`. This will be done till first `k` index are filled. \n\nThe rest of the remaining indices are filled with consecutive elements. Thus, the first `k` elements will give `k - 1` UAADs and the rest of the consecutive elements will give `1` as another UAAD, thus making the total count of UAADs to be `k`.\n\n\n```\nBelow are some examples which will provide better understanding -\n\nFor eg. \n1. let n = 10, k = 4\npermutation                           =>       [1, 10, 2, 9, 8, 7, 6, 5, 4, 3]\nUAADs(abs(arr[i] - arr[i - 1]))       =>       [X,  9, 8, 7, 1, 1, 1, 1, 1, 1]\n\n\n2. n = 10, k = 5\npermutation                           =>       [1, 10, 2, 9, 3, 4, 5, 6, 7, 8]\nUAADs                                 =>       [X, 9, 8, 7, 6, 1, 1, 1, 1, 1]\n\n\n3. n = 9, k = 8\npermutation                           =>       [1, 9, 2, 8, 3, 7, 4, 6, 5]\nUAADs                                 =>       [X, 8, 7, 6, 5, 4, 3, 2, 1]\n\n\n4. n = 9, k = 5\npermutation                           =>       [1, 9, 2, 8, 3, 4, 5, 6, 7]\nUAADs                                 =>       [X, 8, 7, 6, 5, 1, 1, 1, 1]\n\n\n5. n = 15, k = 6\npermutation                           =>       [1, 15,  2, 14,  3, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]\nUAADs                                 =>       [X, 14, 13, 12, 11, 10,  1,  1,  1, 1, 1, 1, 1, 1, 1]\n\n\n1. As we can see from above examples, the approach is again like maintaining two pointers: l = 1, r = n ( <- notice the different initialization than above).\nThe same process as 1st solution is followed till first k index are assigned.\n\n2. Rest of the index are assigned in consecutive manner. For this there will be two different cases -\n\ta. k is odd - Assign consecutive elements starting from l & incrementing it \n\t             (Since previous element ends with l+1 and we need rest of remaining elements to have difference of 1).\n\t\t\t\t  \n\tb. k is even - Assign consecutive elements starting from r & decrement it\n\t\t\t\t (Since previous element ends with l+1 and we need rest of remaining elements to have difference of 1).\n\t\t\t\t \nIn simple words, the rest of elements are filled by taking where the sequence ended in step 1 and appending consecutive elements from there.\n```\n\n---\n\nThe implementation of above idea is given below -\n\n**C++**\n```\nvector<int> constructArray(int n, int k) {\n    vector<int> ans(n);\n    int l = 1, r = n, i = 0;\n    while(i < k - 1) // first k indices are filled with sequence [1, n, 2, n-1, 3, ...]\n        ans[i++] = l++, ans[i++] = r--;\n\t// Remaining indices are filled by consecutive elements. \n\t// The sequence is continued from l or r depending on k (explanation provided above)\n    while(i < n) ans[i++] = (k & 1 ? l++ : r--);\n    return ans;\n}\n```\n\n***Time Complexity :*** **`O(N)`**\n***Space Complexity :*** **`O(N)`**\n\n---\n---\n\n\uD83E\uDDD1\u200D\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any questions or mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C']