coderz.py

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:

Solutions:

Disclaimer: Don’t directly jump into the solution, first try it yourself.

Approach 1: Brute Force Approach

This approach is simple, Just create a new array ans of similar length and iterate over given array nums in such a way that you get the value of each index (like nums[i]) and then use that value as an index to get the value of array nums again (like nums[nums[i]]) and store it one by one in new array ans (like ans[i] = nums[nums[i]]).

For example:

for the given array nums = [0,2,1,5,3,4]

we find ans = [0,1,2,4,5,3]

Code:

class Coderzpy {

    int[] buildArray(int[] nums) {

        int len = nums.length;
        int[] ans = new int[len];

        for(int i = 0; i < len; i++){
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
    public static void main(String args[]) {

        int[] nums = {5,0,1,2,3,4};
                   
        System.out.println("The new array is: "+
        buildArray(nums));
   }
}

output: The new array is: [0,1,2,4,5,3]

Time Complexity: O(n) for iterating each element in array nums.

Space Complexity: O(n) for storing all elements in new arrays ans.

Approach 2: Optimized Approach

In this approach, we are going to use the constant space to process the original array :

1. In-place
2. In a way that allows us to move the value (nums[nums[i]]) in the correct place (i).
3. While also keeping the original value (nums[i]), in-place, in some way so that we can use it later when needed.

We have to keep the value nums[i] preserved, for example, if we need the value at the later position of the array say j, nums[j] = i, but we have overridden the value of i (nums[i]) by (nums[nums[i]]), then we will not be able to use the Original value.

To achieve this task we are going to use Euclid’s Division Algorithm in which a number can be represented in the form a = qb + r, where b and r are not multiples of q, and r < q then we can extract b and r with the following.

• b = a / q (where / is integer division) – we know that qb when divided by q will give us b, however, we still would need to get rid of the r / q. From our requirements though, r < q, so r / q will always be 0, thus b = (qb/q) + (r/q) = b + 0 = b
• r = a % q – we know that qb is a multiple of q, thus is divided by it cleanly and we know that r < q, so r is not a multiple of q, therefore the remainder when dividing a = qb + r by q is just r

Euclid’s Division Algorithm Explained (if you don’t understand the above points, then read this first and try to understand the above points again) otherwise skip this part:

Let’s say you have two numbers, 'a' and 'q', and you want to divide 'a' by 'q' using integer division (where you only get the whole number part of the division).

1. b = a / q (integer division):
   • Imagine you have a bag with 'a' apples, and you want to share them into 'q' equal-sized groups.
   • 'b' represents the number of complete groups you can make out of those 'a' apples.
   • Now, you might worry about any leftover apples that don’t make a complete group. But, because we’re using integer division, we’re only interested in the complete groups, not the leftovers.
   • So, 'b' is the answer you get by counting how many complete groups of 'q' apples each you can make out of 'a' apples.
2. r = a % q (remainder of the division):
   • Imagine again that you have 'a' apples and you want to share them into 'q' equal-sized groups.
   • 'r' represents the remaining apples that don’t fit perfectly into those groups.
   • For example, if 'a' is 10 and 'q' is 3, you can make 3 groups of 3 apples each (totaling 9 apples), and there will be 1 apple left over (the remainder).
   • 'r' is the number of apples that are left after you’ve distributed as many complete groups of 'q' apples as possible.

Now, putting it together:

• When you divide 'a' by 'q' and get 'b', you’re counting the full groups of 'q' apples that fit into 'a', ignoring any leftover apples.
• When you calculate the remainder 'r', you’re finding the number of apples that are left over after filling complete groups of 'q' apples.

So, when you add up the full groups of 'q' apples ('b') and the leftover apples ('r'), you get back to the original number of apples 'a'. The remainder 'r' is the part that couldn’t be evenly divided into complete groups, but it’s still part of the original total 'a'.

Now come back to the solution of our problem:

We need to find a way to transform every element of nums into the form a = qb + r.

At every i, nums[nums[i]] is going to be our b and the original value, nums[i] is our r. Now we just need a q that satisfies the r < q, for all the possible r values (all nums[i]). Luckily, we have such a q already, as our array values are indices in the same array. q = nums.length is always guaranteed to be greater than all nums[i] because each index is always within the bounds of the array, from 0 to nums.length.

Code:

class Coderzpy {

    public int[] buildArray(int[] nums) {
        
        int q = nums.length;

        for(int i = 0; i < q; i++) {

            int r = nums[i];

            int b = nums[nums[i]]%q ;
            
            nums[i] = q*b + r;
        }

        for(int i = 0; i < q; i++) {

            nums[i] = nums[i]/q;
        }

        return nums;
    }

    public static void main(String args[]) {

        int[] nums = {5,0,1,2,3,4};
                   
        System.out.println("The new array is: "+
        buildArray(nums));
   }
}

output: The new array is: [0,1,2,4,5,3]

Time Complexity: O(n) for iterating each element in array nums.

Space Complexity: O(1) because no new array is created to keep new values.

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py