Build Array From Permutation Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Uber
Array SimulationViews 4922

Problem Statement

The Build Array From Permutation LeetCode Solution – “Build Array From Permutation” states that given zero-based permutation nums, we have to build an array of the same length where ans[i] = nums[nums[i]] for each i in range [0,nums.length-1].

A zero-based permutation nums is an array of distinct integers from 0 to nums.length-1 (inclusive).

Example:

Input:  nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]

Explanation:

  • answer array will be : {nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]}.
  • answer = {nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]} = [0, 1, 2, 4, 5, 3]
Input:  nums = [5,0,1,2,3,4]
Output: nums = [5,0,1,2,3,4]

Explanation:

  • Resulting answer array is :-  [5, 0, 1, 2, 3, 4].

Approach

Idea:

  1. The main idea to solve this problem is to use basic maths.
  2. We’ll modify every nums[i] to nums[i] = (old value)*n + new value.
  3. If we want to get the old value, old value = nums[i]/n.
  4. If we want to get the new value, new value = nums[i]%n.
  5. Iterate in the original input array and multiply every number by n.
  6. Again, iterate in the array and transform nums[i] according to the formulae mentioned in step 2.
  7. And, to store new values in the same array, use the formulae mentioned in step3 to get the new values at each index.

Build Array From Permutation Leetcode Solution

Code

C++ Solution:

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();
        for(auto& x:nums){
            x *= n;
        }
        for(int i=0;i<n;i++){
            nums[i] += nums[nums[i]/n]/n;
        }
        for(auto& x:nums){
            x %= n;
        }
        return nums;
    }
};

Java Solution:

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            nums[i] *= n;
        }
        for(int i=0;i<n;i++){
            nums[i] += nums[nums[i]/n]/n;
        }
        for(int i=0;i<n;i++){
            nums[i] %= n;
        }
        return nums;
    }
}

Complexity Analysis for Build Array From Permutation Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we traverse the entire input array exactly once.

Space Complexity

The space complexity of the above code is O(1) since we’re not using any extra space.

Reference: https://en.wikipedia.org/wiki/Permutation

Translate »