1920: Build-Array-from-Permutation
Easy

table of contents

My in-place solution was high-key bad, but here it is.

I wanted to iterate through nums and be able to check which numbers that I have permuted already, which is why I convert every number into a negative number before hand.

That way, I know that if the number is negative it has not been permuted, else we can skip past it and work on permuting the next cycle.

Then, if we are in a new cycle, we can just simply iterate through them and swap all the numbers until we return back to the original index.

code

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        for (int& num : nums) {
            num = -(num+1);
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= 0) continue;
            int original_value = -nums[i]-1;
            
            int original_index = i;
            int new_index = original_value;
            while (new_index != i) {
                nums[original_index] = -nums[new_index]-1;
                original_index = new_index;
                new_index = -nums[new_index]-1;
            }
            nums[original_index] = original_value;
        }
        return nums;
    }
};

complexity

learnings

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            nums[i] |= nums[0xFFFF & nums[i]] << 16; 
        }
        for (int& num : nums) {
            num >>= 16;
        }
        return nums;
    }
};