[C++] Single-Pass Solution Explained, 100% Time, ~98% Space
This problem is made of 2 challenges: spotting what kind of pattern might work for each kind of input and finding out how. to generate it efficiently.\n\nFor th
This problem is made of 2 challenges: spotting what kind of pattern might work for each kind of input and finding out how. to generate it efficiently.\n\nFor the first part, let\'s start with 2 edge cases for `n == 10`; first with `k == 1`, so every number is at the same distance and then we will have:\n\n```cpp\n1, 2, 3, 4, 5, 6, 7, 8, 9, 10\n```\n\nSecond case with the opposite - `k == 9`, so we have to create `9` pairs of numbers with different distances like this:\n\n```cpp\n1, 10, 2, 9, 3, 8, 4, 7, 5, 6\n```\n\nSeen a pattern here? If not yet, let\'s try with `k == 5`:\n\n```cpp\n1, 6, 2, 5, 3, 4, 7, 8, 9, 10\n```\n\nIt looks like if all we need is the same homogeneous distance, we then can just leave the numbers in their increasing order (of course, since they are all equal to the previous `+ 1`, by definition); if we need more groups, then we need to swap a few more and so that usually the first one is always `1`, the second is equal to `1 + k`, the third (if we swapped) is equal to `2`, followed by `2 + k - 2` and so on - as long as we can go, always decreasing `k` by `2` at each step and then summing it to the previous number; once we have consumed `k`, all we can do is just progress and put the remaining numbers in, in their natural order.\n\nNow, the harder part is going to code it all efficiently and possibly elegantly as well.\n\nTo do so, we will first of all start declaring the support variable `res`, already properly sized to avoid reallocations.\n\nNext, we are going to populate it running across it with the pointer `i`, initialised to `0`, while also using `v`, initialised to `1`; at each step we will:\n* if `k-- <= 0`, which means we have "consumed" `k`, we will just set the current cell to be `i + 1` (its "normal", non shuffled value) - note that also makes it so we keep decreasing `k` by `2` at each usage, as discussed above;\n* if otherwise we are on an odd value of `i` (ie: `i & 1`), we will assign it the value of `v` and still increase it;\n* in all the other cases we will give it value of `k + v + 1`\n\nOnce done, we can `return res` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> constructArray(int n, int k) {\n        vector<int> res(n);\n        for (int i = 0, v = 1; i < n; i++) {\n            res[i] = k-- <= -1 ? i + 1 : !(i & 1) ? v++ : k + v + 1;\n        }\n        return res;\n    }\n};\n```
['Math', 'C', 'C++']