![Rearrange an array such that arr[i] = i](/media/new_post_images/Rearrange-an-array-such-that-arri-i.webp)
We have been given an integer array of size n, where every element a[i] is such that, 0<=a[i]<=n-1. Some of the elements may be missing. If the element is missing then there will be -1 written at the place of that element. We have to rearrange the array in such a way that each element a[i]=i and if, i is missing then store -1 at that place.
Example
Input - arr[] = {5, 4, -1, 3, 0, 2, -1}
Output - arr[] = {0, -1, 2, 3, 4, 5, -1}
Simple Approach (Brute Force)
In this approach we will check for each i, 0<=i<=n-1 if it exists in the given array. If yes, then we will make a[i]=i. Now let’s look at the algorithm for better understanding.
Algorithm
- Run a for loop from 0 to n-1 to traverse for each number.
- Using a nested for loop, traverse through the array.
- If a number is found in an array then swap elements at a[i] position with a[j].
- If a number is missing and -1 is written instead of it. Then it will be automatically replaced.
- At last, using a for loop, we iterate through the array and if for any element a[i]!=i then we will make a[i]=-1.
Below is the implementation of the above approach
C++ Programming
#include <bits/stdc++.h>
using namespace std;
void makeEveryElementEqualtoIndex(int a[],int n){
// Traverse for each Number
// from 0 to n-1.
for(int i=0;i<n;i++)
{
// Now traverse the array.
for(int j=0;j<n;j++)
{
// If i is present then
// Swap a[i] with a[j].
if(a[j]==i)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
break;
}
}
}
// Traverse the array and check If
// Any element != it's index
// Then make a[i]=-1.
for(int i=0;i<n;i++)
{
if(a[i]!=i)
{
a[i]=-1;
}
}
}
int main() {
int arr[]={5, 4, -1, 3, 0, 2, -1};
int n=sizeof(arr)/sizeof(arr[0]);
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
Output:
0 -1 2 3 4 5 -1
Java Programming
import java.util.*;
public class Main {
public static void makeEveryElementEqualtoIndex(int a[],int n){
// Traverse for each Number
// from 0 to n-1.
for(int i=0;i<n;i++)
{
// Now traverse the array.
for(int j=0;j<n;j++)
{
// If i is present then
// Swap a[i] with a[j].
if(a[j]==i)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
break;
}
}
}
// Traverse the array and check If
// Any element != it's index
// Then make a[i]=-1.
for(int i=0;i<n;i++)
{
if(a[i]!=i)
{
a[i]=-1;
}
}
}
public static void main (String[] args) {
int arr[]={5, 4, -1, 3, 0, 2, -1};
int n=arr.length;
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
Output:
0 -1 2 3 4 5 -1
Python Programming
def makeEveryElementEqualtoIndex(a, n):
# Traverse for each Number
# from 0 to n-1.
for i in range(n):
# Now traverse the array.
for j in range(n):
# If i is present then
# Swap a[i] with a[j].
if (a[j] == i):
a[j], a[i] = a[i], a[j]
# Traverse the array and check If
# Any element != it's index
# Then make a[i]=-1.
for i in range(n):
if (a[i] != i):
a[i] = -1
for i in range(n):
print(a[i], end = " ")
print()
# Driver Code
arr = [ 5, 4, -1, 3, 0, 2, -1 ]
n = len(arr)
makeEveryElementEqualtoIndex(arr, n);
Output
0 -1 2 3 4 5 -1
C# Programming
using System;
public class main{
static void makeEveryElementEqualtoIndex(int[] a,int n){
// Traverse for each Number
// from 0 to n-1.
for(int i=0;i<n;i++)
{
// Now traverse the array.
for(int j=0;j<n;j++)
{
// If i is present then
// Swap a[i] with a[j].
if(a[j]==i)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
break;
}
}
}
// Traverse the array and check If
// Any element != it's index
// Then make a[i]=-1.
for(int i=0;i<n;i++)
{
if(a[i]!=i)
{
a[i]=-1;
}
}
}
static public void Main (){
int[] arr={5, 4, -1, 3, 0, 2, -1};
int n=arr.Length;
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
Console.Write(arr[i]+" ");
Console.WriteLine();
}
}
Output:
0 -1 2 3 4 5 -1
Complexity Analysis
- Time Complexity - O(n^2), Since we have used two nested loops.
- Space Complexity - O(1)
Another Approach (Using Extra Space)
In this approach, we will store elements in a frequency array or in the HashSet. Then, we will again traverse the array to check if the element i exist in the HashSet or not. Let’s have a look at the Algorithm to have a better understanding -
Algorithm
- Traverse the array and store all elements in a HashSet.
- Again traverse from 0 to n-1 using the for loop, where n is the length of the array. And check if i exist in HashSet then make a[i]=i, else make a[i]=-1.
Below is the implementation of the above approach -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
void makeEveryElementEqualtoIndex(int a[],int n){
unordered_set <set> hs;
// Traverse the array and
// Add elements to the set.
for(int i=0;i<n;i++) hs.insert(a[i]); // Again traverse from i=0 -> i=n-1
for(int i=0;i<n;i++)
{
// If Set contains i
// Then make a[i]=i,
// else a[i]=-1
if(hs.find(i)==hs.end())
a[i]=-1;
else
a[i]=i;
}
}
int main() {
int arr[]={5, 4, -1, 3, 0, 2, -1};
int n=sizeof(arr)/sizeof(arr[0]);
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
Output:
0 -1 2 3 4 5 -1
Java Programming
import java.util.*;
public class Main {
public static void makeEveryElementEqualtoIndex(int a[],int n){
HashSet hs=new HashSet<>();
// Traverse the array
// and add each element
// to the HashSet
for(int i=0;i<n;i++) hs.add(a[i]); // Again traverse from i=0 -> i=n-1
for(int i=0;i<n;i++)
{
// If HashSet contains i
// Then make a[i]=i,
// else a[i]=-1
if(hs.contains(i))
a[i]=i;
else
a[i]=-1;
}
}
public static void main (String[] args) {
int arr[]={5, 4, -1, 3, 0, 2, -1};
int n=arr.length;
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
Output:
0 -1 2 3 4 5 -1
Python Programming
def makeEveryElementEqualtoIndex(a, n):
s = set()
# Traverse the array and
# Add elements to the set.
for i in range(len(a)):
s.add(a[i])
# Again traverse from i=0 -> i=n-1
for i in range(len(a)):
# If Set contains i
# Then make a[i]=i,
# else a[i]=-1
if i in s:
a[i] = i
else:
a[i] = -1
for i in range(n):
print(a[i], end = " ")
print()
# Driver Code
arr = [ 5, 4, -1, 3, 0, 2, -1 ]
n = len(arr)
makeEveryElementEqualtoIndex(arr, n);
Output:
0 -1 2 3 4 5 -1
C# Programming
using System;
using System.Collections.Generic;
public class main{
static void makeEveryElementEqualtoIndex(int[] a,int n){
HashSet hs=new HashSet();
// Traverse the array
// and add each element
// to the HashSet
for(int i=0;i<n;i++) hs.Add(a[i]); // Again traverse from i=0 -> i=n-1
for(int i=0;i<n;i++)
{
// If HashSet contains i
// Then make a[i]=i,
// else a[i]=-1
if(hs.Contains(i))
a[i]=i;
else
a[i]=-1;
}
}
static public void Main (){
int[] arr={5, 4, -1, 3, 0, 2, -1};
int n=arr.Length;
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
Console.Write(arr[i]+" ");
Console.WriteLine();
}
}
Output
0 -1 2 3 4 5 -1
Complexity Analysis
- Time Complexity - O(n), We have traversed the array only two times.
- Space Complexity - O(n), Since we have used HashSet.
Optimized Approach
In this approach, we will try to solve the question in linear Time Complexity and in constant extra space.
Algorithm
- Traverse through the array.
- And if a[i] is not equal to -1 and it is not present at its correct position then we will swap it by its correct position i.e. a[a[i]].
Below is the implementation of the above approach -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
void makeEveryElementEqualtoIndex(int a[],int n){
// Traverse the array
for (int i=0;i<n;)
{
// If a[i] is not equal
// to -1 and it is not at
// its correct position.
// Then swap with its correct
// position
if (a[i]!=-1&&a[i]!=i)
{
int temp=a[a[i]];
a[a[i]]=a[i];
a[i]=temp;
}
else
{
i++;
}
}
}
int main() {
int arr[]={5, 4, -1, 3, 0, 2, -1};
int n=sizeof(arr)/sizeof(arr[0]);
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
Output:
0 -1 2 3 4 5 -1
Java Programming
import java.util.*;
public class Main {
public static void makeEveryElementEqualtoIndex(int a[],int n){
// Traverse the array
for (int i=0;i<n;)
{
// If a[i] is not equal
// to -1 and it is not at
// its correct position.
// Then swap with its correct
// position
if (a[i]!=-1&&a[i]!=i)
{
int temp=a[a[i]];
a[a[i]]=a[i];
a[i]=temp;
}
else
{
i++;
}
}
}
public static void main (String[] args) {
int arr[]={5, 4, -1, 3, 0, 2, -1};
int n=arr.length;
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
Output:
0 -1 2 3 4 5 -1
Python Programming
def makeEveryElementEqualtoIndex(a, n):
i = 0
# Traverse the array
while i < n: # If a[i] is not equal # to -1 and it is not at # its correct position. # Then swap with its correct # position if (a[i] >= 0 and a[i] != i):
(a[a[i]],a[i]) = (a[i],a[a[i]])
else:
i += 1
for i in range(n):
print(a[i], end = " ")
print()
# Driver Code
arr = [ 5, 4, -1, 3, 0, 2, -1 ]
n = len(arr)
makeEveryElementEqualtoIndex(arr, n);
Output:
0 -1 2 3 4 5 -1
C# Programming
using System;
public class main{
static void makeEveryElementEqualtoIndex(int[] a,int n){
// Traverse the array
for (int i=0;i<n;)
{
// If a[i] is not equal
// to -1 and it is not at
// its correct position.
// Then swap with its correct
// position
if (a[i]!=-1&&a[i]!=i)
{
int temp=a[a[i]];
a[a[i]]=a[i];
a[i]=temp;
}
else
{
i++;
}
}
}
static public void Main (){
int[] arr={5, 4, -1, 3, 0, 2, -1};
int n=arr.Length;
makeEveryElementEqualtoIndex(arr,n);
for(int i=0;i<n;i++)
Console.Write(arr[i]+" ");
Console.WriteLine();
}
}
Output:
0 -1 2 3 4 5 -1
Complexity Analysis
- Time Complexity - O(n), We only traversed the array once.
- Space Complexity - O(1), No extra space is used.
Wrapping Up!
In this article, we have learned how to rearrange the array such that a[i]=i. We discussed three approaches in which we can solve this problem. This article also contains well-explained codes of both the approaches in the four most popular languages which are c++, Java, Python, and C# along with their respective outputs attached to the article for a better understanding of a wide range of our readers.
We sincerely hope that this article has walked you through some deep and important concepts of Arrays and you have learned how we should approach such kinds of problems. We hope that you will now be able to solve this problem as well as its other variations seamlessly and efficiently.
Happy Coding!
People are also reading:
Leave a Comment on this Post