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

Rearranging An Array
Rearranging An Array

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.

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.


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’.

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).

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).

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 of 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

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].

Key Takeaways

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.

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

Exit mobile version