Skip to content

← leetcode

Build Array from Permutation

· Easy

LeetCode problem 1920

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.

  • 0 => -1
  • 1 => -2
  • 2 => -3
  • etc.

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

  • Time: O(n)
  • Space: O(1)

learnings

  • you can just or the respective values 16 bits to the left after a shift, and then consequently right shift everything by 16 bits
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;
    }
};