Beats 100% C++ Easy (Zig Zag Approach)
Intuition\n Describe your first thoughts on how to solve this problem. \nTo construct a list of n different positive integers ranging from 1 to n that ensures e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo construct a list of n different positive integers ranging from 1 to n that ensures exactly k distinct differences, we can leverage a zig-zag pattern approach. This will create maximum unique differences early on.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStart with the first element as 1.\n\nAlternate between adding and subtracting k, decreasing k each time:\nThis ensures that the differences created will be distinct and reduces the number of distinct differences.\n\nOnce k reaches 0, fill the rest of the array in ascending order from the current maximum value.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\nWe iterate through the array a single time, so the complexity is linear.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\nWe use an array of size n to store the result.\n\n![Screenshot 2024-07-05 171858.png](https://assets.leetcode.com/users/images/d2ce3a6d-dbe6-47cc-9b0e-b2a0ba7960ba_1720180153.3936865.png)\n\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> constructArray(int n, int k) {\n        int nm=1;\n        vector<int> v(n,-1);\n        v[0]=1;\n        int mx = 1;\n        int f=0;\n        for(int i=1;i<n;i++){\n            if(f==0)nm+=k;\n            else nm-=k;\n            \n            mx=max(mx,nm);\n            v[i]=nm;\n            k--;\n            f=1-f;\n            if(k==0)break;\n        }\n        for(int i=0;i<n;i++){\n            if(v[i]==-1){\n                while(i<n){\n                    v[i]=mx+1;\n                    mx++;\n                    i++;\n                }\n            }\n        }\n\n        return v;\n    }\n};\n\n\n\nCODE EXPLAINATION:\n\n1) Initialize Variables:\n\nnm (next number) is initialized to 1.\nv (the result array) is initialized with size n and all values set to -1.\nThe first element of v is set to 1.\nmx (current maximum value) is initialized to 1.\nf (a flag for alternating addition and subtraction) is set to 0.\n\n2) Main Loop:\n\nFor each index from 1 to n-1:\nIf f is 0, add k to nm.\nIf f is 1, subtract k from nm.\nUpdate mx to be the maximum of mx and nm.\nSet the current element of v to nm.\nDecrease k by 1.\nToggle f between 0 and 1.\nIf k reaches 0, break out of the loop.\n\n3) Fill Remaining Values:\n\nIf there are any elements in v that are still -1, fill them with consecutive values starting from mx + 1.\n\n\n\n**Example Dry Run\nFor n = 10 and k = 3:**\n\n\nInitialization:\n\nnm = 1\nv = [1, -1, -1, -1, -1, -1, -1, -1, -1, -1]\nmx = 1\nf = 0\nMain Loop:\n\nIteration 1 (i = 1, k = 3, f = 0):\n\nnm = 1 + 3 = 4\nmx = max(1, 4) = 4\nv = [1, 4, -1, -1, -1, -1, -1, -1, -1, -1]\nk = 2\nf = 1\nIteration 2 (i = 2, k = 2, f = 1):\n\nnm = 4 - 2 = 2\nmx = max(4, 2) = 4\nv = [1, 4, 2, -1, -1, -1, -1, -1, -1, -1]\nk = 1\nf = 0\nIteration 3 (i = 3, k = 1, f = 0):\n\nnm = 2 + 1 = 3\nmx = max(4, 3) = 4\nv = [1, 4, 2, 3, -1, -1, -1, -1, -1, -1]\nk = 0\nf = 1\nExit the loop because k = 0.\nFill Remaining Values:\n\nmx = 4\nFill the remaining -1 values in v with mx + 1, mx + 2, ...:\nv[4] = 5\nv[5] = 6\nv[6] = 7\nv[7] = 8\nv[8] = 9\nv[9] = 10\n```
['Array', 'Math', 'C++']