Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Brute Force Approach
3.
Implementation of Brute Force Method
4.
An Optimized Version of the First Approach
5.
Implementation After Optimization
6.
Rearranging Array Using HashSet
7.
Implementation Using HashSet
8.
Frequently Asked Questions
8.1.
How can I rearrange a given array so that arr[i] becomes arr[arr[i]] with O(1) extra space?
8.2.
How do you rearrange elements in an array?
8.3.
How do you rearrange an array element in Python?
8.4.
What is the time complexity of different operations in unordered_map?
8.5.
How do you return the first value in an array?
9.
Conclusion
Last Updated: Mar 27, 2024
Easy

How to Rearrange an Array such that arr[i]=i?

Author Juhi Sinha
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Let’s say you have an array of n numbers, and this array can contain numbers from 0 to n-1. And for the numbers up to n, which are not present in the array, it has -1. 

Now we have to arrange the elements in the array such that arr[i]=i, or all the elements in the array are at their respective indices, and the index whose respective elements are not present in the array contains -1.

Rearranging An Array

There are numerous ways to achieve this task. We will start with the most straightforward approach of just traversing through the array and putting the numbers to their respective indices. Then we will be using advanced methods to complete this task more efficiently.

Recommended Topic, Array Implementation of Queue and Rabin Karp Algorithm

Brute Force Approach

Let’s begin with a simple example: If you have an array of 5 elements {2,-1,0,3,1}, and you have to rearrange it such that arr[i]=i. The simple approach will be to pick the first index, the 0th index, then searching the array for 0, which we find at index 2, now we swap arr[0] and arr[2]. We do this for the rest of the indexes and get the final array.

In Simple words, this method checks the array for every index up to n-1, whether the corresponding number is present in it or not. If the number is present, we swap it with the element at the index. Suppose we searched the array for number ‘a’ corresponding to index a, which is present at index ‘b’ in the array. Then we will swap array[b] with array[a], so that array[a] stores ‘a’.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation of Brute Force Method

//To rearrange an array such that arr[i]=i,using brute force method.
#include <bits/stdc++.h>
using namespace std;
//Bruteforce approach to rearrange the array.
void rearrange(int arr[], int len)
{
    int var;
    //Iterate over the array.
    for(int i=0;i<len;i++)
    {
        //Swap the element having matching index to its value.
        for(int j=0;j<len;j++)
        {
            if(arr[j]==i)
            {
                var=arr[j];
                arr[j]=arr[i];
                arr[i]=var;
                break;
            }
        }
    }
    //Marking the indices of elements as -1, the elements which are not present in 
    //the array.
    for(int i=0;i<len;i++)
    {
        //If not present 
        if(arr[i]!=i)
        {
            arr[i]=-1;
        }
    }
}
//To print the array.
void printarray(int arr[], int len)
{
    cout<<"Array after rearranging"<<endl;
    for(int i=0;i<len;i++)
    {
        cout<<arr[i]<<" ";
    }
}
//Driver function.
int main()
{
    int len;
    int arr[]={-1,9,-1,7,6,2,5,-1,3,-1};
    len=sizeof(arr)/sizeof(arr[0]);
    rearrange(arr,len);
    printarray(arr,len);
}


Output

Array after Rearranging

-1 -1 2 3 -1 5 6 7 -1 9


The time complexity of this approach is O(N^2), where N is the number of elements in the array as we have a nested loop which is the costliest step.

The space complexity of this approach is O(1).

Check this out: Array in Java

An Optimized Version of the First Approach

This method starts with traversing through the array and finding an index that has an element corresponding to some other index. We then put that element at its correct position, and if its right place has some other element, we put it to its valid index. We continue to repeat the process until all elements move to their corresponding index.

Implementation After Optimization

//To rearrange an array such that arr[i]=i,using optimization of brute force method.
#include <bits/stdc++.h> 
using namespace std;
//Rearranging array using optimisation of first method
void rearrange(int arr[], int len)
{
    //Traversing through the array and finding the elements placed at
    //the wrong indices.
    for(int i=0;i<len;i++)
    {
        if(arr[i]!=i && arr[i]!=-1)
        {
            int a =arr[i];
            while(arr[a]!=-1&&arr[a]!=a)
            {
                //Temporarily hold the value, so that the value can
                //be replaced.
                int b=arr[a];
                arr[a]=a;
                a=b;
            }
            arr[a]=a;
            if(arr[i]!=i)
            {
                //To fill the indices with no corresponding elements
                //to -1.
                arr[i]=-1;
            }
        }
    }
}
//Driver function
int main()
{
    int arr[]={-1,9,-1,7,6,2,5,-1,3,-1};
    int n=sizeof(arr)/sizeof(arr[0]);
    //Function call
    rearrange(arr,n);
    //Print the output
    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
}


Output

-1 -1 2 3 -1 5 6 7 -1 9


The time complexity of this approach is O(N), where N is the number of elements in the array.

The space complexity of this approach is O(1).


Check out this array problem - Merge 2 Sorted Arrays

Rearranging Array Using HashSet

HashSet stores unique elements and discards extra copies of the keys it receives. Its internal implementation uses a hashtable in which keys get hashed into indices of the hash table, which helps in randomizing insertion. Operations of HashSet take O(1) time in the average cases and O(n) in the worst cases.

Since it discards the duplicate keys, It helps us collect all the unique numbers in the array.  This quality of HashSet makes it suitable to be used to solve this problem.

We push all the positive array elements into a HashSet and their set value as one. Then we traverse through the hash set, and whatever elements we get from it, we fill them at their respective places in the array. Then we fill all the remaining indexes of the array with -1.

Implementation Using HashSet

//To rearrange an array such that arr[i]=i,using HashSet.
#include <bits/stdc++.h>
using namespace std;
//Rearranging the array using hashset.
void rearrange(int arr[], int len)
{
    //using unordered map
    unordered_map<int,int> m;
    //if value is not -1 making that key value equal to 1.
    for(int i=0;i<len;i++)
    {
       if(arr[i]!=-1)
           m[arr[i]]=1;
    }
    //Iterating through the array to put arr[i] = i, if i is present
    //in the map else make it -1.
    for(int i=0;i<len;i++)
    {
        //if i(index) is found in map
        if(m.find(i)!=m.end())
        {
            arr[i]=i;
        }
        else
        {
            //if i is not found
            arr[i]=-1;
        }
    }
}
//To print the array.
void printarray(int arr[], int len)
{
    cout<<"array after rearranging"<<endl;
    for(int i=0;i<len;i++)
    {
        cout<<arr[i]<<" ";
    }
}
//Driver function.
int main()
{
    int len;
    int arr[]={-1,9,-1,7,6,2,5,-1,3,-1};
    len=sizeof(arr)/sizeof(arr[0]);
    rearrange(arr,len);
    printarray(arr,len);
}


Output

Array after Rearranging 
-1 -1 2 3 -1 5 6 7 -1 9


The time complexity of this approach is O(N), where N is the number of elements in the array.

The space complexity of this approach is O(N) as we use a hashmap to store the presence of elements as keys.

Also see, Morris Traversal for Inorder.

Frequently Asked Questions

How can I rearrange a given array so that arr[i] becomes arr[arr[i]] with O(1) extra space?

We can do that by traversing the array from start to end. Then for every index increment the element by array[array[index]] % n. Then, get the ith element to find the modulo with n, i.e., array[index]%n. Then again, traverse the array from start to end. Finally, we will print the ith element after dividing the ith element by n.

How do you rearrange elements in an array?

There are numerous ways to do so, and the basic methods do that with the help of swapping the numbers to their desired positions.

How do you rearrange an array element in Python?

The logic behind rearranging an array barely changes with the languages. The only changes that occur are in the functions used in that language. In Python, we will use loops by the range method, which has a different syntax in C++.

What is the time complexity of different operations in unordered_map?

The most common operations on unordered_map are search, insert, and delete. All of these have a time complexity of O(1).

How do you return the first value in an array?

To return the first value in an array, we need to access the 0th element of the array, represented by Arrayname[0].

Conclusion

This article discusses how we can rearrange an array such that arr[i]=i. It only contains elements ranging from -1 to n-1.

  • We started with the Brute force method, which involves traversing through the array and, for each index, searching if the corresponding element is present in the array or not. If present, move them to their correct position.
     
  • The second method was an optimized version of the first method. It traversed the array to find the indices not having their correct corresponding values. We move those values to their valid index, and if these indices contain values corresponding to some other index, we repeat the whole process. We continue to do so until all elements move to their correct position.
     
  • The last method uses HashSet to solve this problem. We traverse the whole array, push all the elements with positive values into an unordered map, and set their value as 1 in the map. We then traverse the array. For the element present in the map, we fill the respective indexes with the value equal to the index and then fill the empty indices with -1.
     

Check out the following problems related to array -

You can read more about HashSet at this link or practice similar problems on Coding Ninjas Studio. If you liked this blog, do share it with your friends!

Previous article
Difference between Array, Queue & Stack
Next article
Find the Number Occurring Odd Number of Times
Live masterclass