Build Array from Permutation – Solution to LeetCode Problem

Problem Statement

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

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

Examples

Example 1 

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

Example 2 

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

Constraints

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < nums.length
  • The elements in nums are distinct.

Follow Up

Can you solve it without using an extra space (i.e., O(1) memory)?

I highly recommend you to try solving this problem on LeetCode.

Approach 1

One very simple idea is to create a new list. Create a loop with loop control variable i from 0 to len(nums). For each i, append nums[nums[i]] to the new list.

Solution in Python 

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(0, len(nums)):
            res.append(nums[nums[i]])
        return res

While this has a time complexity of O(n), it has a space complexity of O(n) because it needs additional space to store the new list.

Approach 2

This solution makes use of the modulo operator. Using the properties of Modulo, we can store two numbers in one element and extract them at our will. We are given that the range of nums[i] is between 0 to 1000. So we take modulo to be 1001.

As the values in the input array are ranging from 0 to n-1 where n is the length of the array, we can simply store the input array value in modulo by n and modified value in divide by n. This solves the problem of adding extra space to our solution.

We make use of the equation nums[i] = nums[i] + (n*(nums[nums[i]]%n)) to store the new values in the nums array. We then divide by n to get the required value to return.

To understand this better, let’s assume an element is a and another element is b, both the elements are less than n. So if an element a is incremented by b*n, the element becomes a + b*n. So, when a + b*n is divided by n, the value is b and a + b*n % n is a.

Example

Consider the input array as [1, 0]. Now in each iteration (0 to len(nums)-1), we use the equation shown above to make the array as shown below.

nums[i] = nums[i] + (n*(nums[nums[i]]%n))
After running the loop, the array becomes [1, 2].

After dividing by 2 it results in [0, 1] which is the correct answer.

Solution in Python 

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(0, len(nums)):
            nums[i]=nums[i]+(n*(nums[nums[i]]%n))

        for i in range(0, len(nums)):
            nums[i] = int(nums[i]/n)

        return nums

Solution in C++ 

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

The space complexity of this approach is O(1) and the time complexity is O(n). The basic idea to remember here is that we have to make use of the modulo operator to store two values in the same element.

I hope you understood the concepts involved, if not, please do comment below. If you liked my work, you can buy me a pizza here.

This post was originally published on hello ML.

35

Tags:

LeetcodeAlgorithmsDatastructures