Java Solution. Everyone else's code is way too convoluted to understand
So we know that if we want to have (say n = 6) :\nk = 1\n {1, 2, 3, 4, 5, 6} OR {6, 5, 4, 3, 2, 1}.\n\nFor k = 2\n{1, 6, 5, 4, 3, 2} OR {6, 1, 2, 3, 4, 5}.\n\nF
So we know that if we want to have (say n = 6) *<there are multiple sets that work for each, I will only show one or two basic ones>*:\nk = 1\n {1, 2, 3, 4, 5, 6} OR {6, 5, 4, 3, 2, 1}.\n\nFor k = 2\n{1, 6, 5, 4, 3, 2} OR {6, 1, 2, 3, 4, 5}.\n\nFor k = 3\n{1, 6, 2, 3, 4, 5} OR {6, 1, 5, 4, 3, 2}.\n\nNotice that each time we want to increase k, we reverse the list again and again from list of size n - 1 to n - 2 to n - 3 to.....\nHence, to have a higher k, we just have to keep reversing the elements on top of each other from index 0 to index k - 1.\n\nSo, a naive approach would be O(kn) = O(n^2) since k at worst = n - 1:\n\n\n```\npublic int[] constructArray(int n, int k) {\n\tint[] res = new int[n];\n\t\n\t// Create initial array of {1, 2, 3, 4, ..., n}\n\tfor(int i = 0; i < n; i++)\n\t\tres[i] = i + 1;\n\t\t\n\t// Keep reversing each sub-array from index 0 to k - 1\n\tfor(int i = 1; i < k; i++)\n\t\treverseList(res, i, n - 1);\n\treturn res;\n}\n\n// Reverse sub-array.\n// You can also use XOR to swap for "coolness" since you don\'t use another variable but it is slower than using the int temp itself\npublic void reverseList(int[] res, int left, int right){\n        while(left < right){\n            int temp = res[left];\n            res[left] = res[right];\n            res[right] = temp;\n            \n            left++;\n            right--;\n        }\n    }\n```\n\n\nNow, since we know the pattern, the next thing you might wonder is:\nCan I do this is O(n)? Can I do this in 1 go since the pattern is simple? After all, I\'m just reversing every other number until k - 1 times and the rest of the numbers being either incremement of 1 from there or decrement of 1 from there. And yes, yes you can.\n\n\tpublic int[] constructArray(int n, int k) {\n\t\tint[] res = new int[n];\n\t\tint left = 1;\n\t\tint right = n;\n\n\t\tfor(int i = 0; i < n; i++){\n\t\t // If k is even, increment by 1, else decrement by 1 (you can swap this order. Just be consistent)\n\t\t if(k % 2 == 0)\n\t\t  res[i] = left++;\n\t\t else \n\t\t  res[i] = right--;\n\t\t\t\n\t\t // Keep swapping the reverses on each index until you do it k - 1 times.\n\t\t // Then rest of numbers should just ONLY incremements or ONLY decrements.\n\t\t if(k > 1)\n\t\t  k--;\n\t\t}\n\t\treturn res;\n\t}\n\t\nI understand that this code is also found in the 2 liner one in the top voted. But seriously, that\'s unreadable and completely unhelpful. So if you guys are struggling and not understanding the logic behind this, I hope this makes more sense. Basically, if you reverse the whole array, you get k = 1. If you reverse that from index 2 then, you get k = 2. If you reverse that from index 3 then, you get k = 3.. and so on.\nThe for loop for O(n) is doing just that. "k--" until all the necessary reverses are done to get the number of k differences then just either going increments of 1 or decrements of 1 only on the rest of the array.
[]