Rearrange an array such that arr[i] = i
Given an array of elements of length N, ranging from 0 to N – 1. All elements may not be present in the array. If the element is not present then there will be -1 present in the array. Rearrange the array such that A[i] = i and if i is not present, display -1 at that place.
Examples:
Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8,
11, 10, 9, 5, 13, 16, 2, 14, 17, 4}
Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19]
Approach(Naive Approach):
- Navigate the numbers from 0 to n-1.
- Now navigate through array.
- If (i==a[j]) , then replace the element at i position with a[j] position.
- If there is any element in which -1 is used instead of the number then it will be replaced automatically.
- Now, iterate through the array and check if (a[i]!=i) , if it s true then replace a[i] with -1.
Below is the implementation for the above approach:
// C++ program for above approach
#include <iostream>
using namespace std;
// Function to transform the array
void fixArray(int ar[], int n)
{
int i, j, temp;
// Iterate over the array
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
// Check is any ar[j]
// exists such that
// ar[j] is equal to i
if (ar[j] == i) {
temp = ar[j];
ar[j] = ar[i];
ar[i] = temp;
break;
}
}
}
// Iterate over array
for (i = 0; i < n; i++)
{
// If not present
if (ar[i] != i)
{
ar[i] = -1;
}
}
// Print the output
cout << "Array after Rearranging" << endl;
for (i = 0; i < n; i++) {
cout << ar[i] << " ";
}
}
// Driver Code
int main()
{
int n, ar[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
n = sizeof(ar) / sizeof(ar[0]);
// Function Call
fixArray(ar, n);
}
// Code BY Tanmay Anand
// C program for above approach
#include <stdio.h>
// Function to transform the array
void fixArray(int ar[], int n)
{
int i, j, temp;
// Iterate over the array
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
// Check is any ar[j]
// exists such that
// ar[j] is equal to i
if (ar[j] == i) {
temp = ar[j];
ar[j] = ar[i];
ar[i] = temp;
break;
}
}
}
// Iterate over array
for (i = 0; i < n; i++)
{
// If not present
if (ar[i] != i)
{
ar[i] = -1;
}
}
// Print the output
printf("Array after Rearranging\n");
for (i = 0; i < n; i++) {
printf("%d ",ar[i]);
}
}
// Driver Code
int main()
{
int n, ar[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
n = sizeof(ar) / sizeof(ar[0]);
// Function Call
fixArray(ar, n);
}
// This code is contributed by kothvvsaakash.
// Java program for above approach
public class GFG{
// Function to transform the array
public static void fixArray(int ar[], int n)
{
int i, j, temp;
// Iterate over the array
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
// Check is any ar[j]
// exists such that
// ar[j] is equal to i
if (ar[j] == i)
{
temp = ar[j];
ar[j] = ar[i];
ar[i] = temp;
break;
}
}
}
// Iterate over array
for(i = 0; i < n; i++)
{
// If not present
if (ar[i] != i)
{
ar[i] = -1;
}
}
// Print the output
System.out.println("Array after Rearranging");
for(i = 0; i < n; i++)
{
System.out.print(ar[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int n, ar[] = { -1, -1, 6, 1, 9,
3, 2, -1, 4, -1 };
n = ar.length;
// Function Call
fixArray(ar, n);
}
}
// This code is contributed by divyesh072019
# Python3 program for above approach
# Function to transform the array
def fixArray(ar, n):
# Iterate over the array
for i in range(n):
for j in range(n):
# Check is any ar[j]
# exists such that
# ar[j] is equal to i
if (ar[j] == i):
ar[j], ar[i] = ar[i], ar[j]
# Iterate over array
for i in range(n):
# If not present
if (ar[i] != i):
ar[i] = -1
# Print the output
print("Array after Rearranging")
for i in range(n):
print(ar[i], end = " ")
# Driver Code
ar = [ -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 ]
n = len(ar)
# Function Call
fixArray(ar, n);
# This code is contributed by rag2127
// C# program for above approach
using System;
class GFG {
// Function to transform the array
static void fixArray(int[] ar, int n)
{
int i, j, temp;
// Iterate over the array
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
// Check is any ar[j]
// exists such that
// ar[j] is equal to i
if (ar[j] == i)
{
temp = ar[j];
ar[j] = ar[i];
ar[i] = temp;
break;
}
}
}
// Iterate over array
for(i = 0; i < n; i++)
{
// If not present
if (ar[i] != i)
{
ar[i] = -1;
}
}
// Print the output
Console.WriteLine("Array after Rearranging");
for(i = 0; i < n; i++)
{
Console.Write(ar[i] + " ");
}
}
static void Main() {
int[] ar = { -1, -1, 6, 1, 9,
3, 2, -1, 4, -1 };
int n = ar.Length;
// Function Call
fixArray(ar, n);
}
}
// This code is contributed by divyeshrabadiya07
<script>
// JavaScript program for above approach
// Function to transform the array
function fixArray(ar, n) {
var i, j, temp;
// Iterate over the array
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
// Check is any ar[j]
// exists such that
// ar[j] is equal to i
if (ar[j] == i) {
temp = ar[j];
ar[j] = ar[i];
ar[i] = temp;
break;
}
}
}
// Iterate over array
for (i = 0; i < n; i++)
{
// If not present
if (ar[i] != i) {
ar[i] = -1;
}
}
// Print the output
document.write("Array after Rearranging");
document.write("<br>");
for (i = 0; i < n; i++) {
document.write(ar[i] + " ");
}
}
// Driver Code
var n,
ar = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1];
n = ar.length;
// Function Call
fixArray(ar, n);
// This code is contributed BY Rahul Tank
</script>
Output
Array after Rearranging -1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n2)
Auxiliary Space: O(1), since no extra space has been taken.
Another Approach:
1. Navigate through the array.
2. Check if a[i] = -1, if yes then ignore it.
3. If a[i] != -1, Check if element a[i] is at its correct position (i=A[i]). If yes then ignore it.
4. If a[i] != -1 and element a[i] is not at its correct position (i!=A[i]) then place it to its correct position, but there are two conditions:
- Either A[i] is vacate, means A[i] = -1, then just put A[i] = i .
- OR A[i] is not vacate, means A[i] = x, then int y=x put A[i] = i. Now, we need to place y to its correct place, so repeat from step 3.
Below is the implementation for the above approach:
// C++ program for rearrange an
// array such that arr[i] = i.
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange an array
// such that arr[i] = i.
void fixArray(int A[], int len)
{
for (int i = 0; i < len; i++)
{
if (A[i] != -1 && A[i] != i)
{
int x = A[i];
// check if desired place
// is not vacate
while (A[x] != -1 && A[x] != x)
{
// store the value from
// desired place
int y = A[x];
// place the x to its correct
// position
A[x] = x;
// now y will become x, now
// search the place for x
x = y;
}
// place the x to its correct
// position
A[x] = x;
// check if while loop hasn't
// set the correct value at A[i]
if (A[i] != i)
{
// if not then put -1 at
// the vacated place
A[i] = -1;
}
}
}
}
// Driver code
int main()
{
int A[] = { -1, -1, 6, 1, 9,
3, 2, -1, 4, -1 };
int len = sizeof(A) / sizeof(A[0]);
// Function Call
fixArray(A, len);
// Print the output
for (int i = 0; i < len; i++)
cout << A[i] << " ";
}
// This code is contributed by Smitha Dinesh Semwal
// C program for rearrange an
// array such that arr[i] = i.
#include <stdio.h>
// Function to rearrange an array
// such that arr[i] = i.
void fixArray(int A[], int len)
{
for (int i = 0; i < len; i++)
{
if (A[i] != -1 && A[i] != i)
{
int x = A[i];
// check if desired place
// is not vacate
while (A[x] != -1 && A[x] != x)
{
// store the value from
// desired place
int y = A[x];
// place the x to its correct
// position
A[x] = x;
// now y will become x, now
// search the place for x
x = y;
}
// place the x to its correct
// position
A[x] = x;
// check if while loop hasn't
// set the correct value at A[i]
if (A[i] != i)
{
// if not then put -1 at
// the vacated place
A[i] = -1;
}
}
}
}
// Driver code
int main()
{
int A[] = { -1, -1, 6, 1, 9,
3, 2, -1, 4, -1 };
int len = sizeof(A) / sizeof(A[0]);
// Function Call
fixArray(A, len);
// Print the output
for (int i = 0; i < len; i++)
printf("%d ",A[i]);
}
// This code is contributed by kothavvsaakash
// Java program for rearrange an
// array such that arr[i] = i.
import java.util.*;
import java.lang.*;
public class GfG {
// Function to rearrange an array
// such that arr[i] = i.
public static int[] fix(int[] A)
{
for (int i = 0; i < A.length; i++)
{
if (A[i] != -1 && A[i] != i)
{
int x = A[i];
// check if desired place
// is not vacate
while (A[x] != -1 && A[x] != x)
{
// store the value from
// desired place
int y = A[x];
// place the x to its correct
// position
A[x] = x;
// now y will become x, now
// search the place for x
x = y;
}
// place the x to its correct
// position
A[x] = x;
// check if while loop hasn't
// set the correct value at A[i]
if (A[i] != i)
{
// if not then put -1 at
// the vacated place
A[i] = -1;
}
}
}
return A;
}
// Driver code
public static void main(String[] args)
{
int A[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
System.out.println(Arrays.toString(fix(A)));
}
}
# Python3 program for rearrange an
# array such that arr[i] = i.
# Function to rearrange an array
# such that arr[i] = i.
def fix(A, len):
for i in range(0, len):
if (A[i] != -1 and A[i] != i):
x = A[i]
# check if desired place
# is not vacate
while (A[x] != -1 and A[x] != x):
# store the value from
# desired place
y = A[x]
# place the x to its correct
# position
A[x] = x
# now y will become x, now
# search the place for x
x = y
# place the x to its correct
# position
A[x] = x
# check if while loop hasn't
# set the correct value at A[i]
if (A[i] != i):
# if not then put -1 at
# the vacated place
A[i] = -1
# Driver code
A = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
fix(A, len(A))
for i in range(0, len(A)):
print(A[i], end=' ')
# This code is contributed by Saloni1297
// C# program for rearrange
// an array such that
// arr[i] = i.
using System;
class GfG {
// Function to rearrange an
// array such that arr[i] = i.
public static int[] fix(int[] A)
{
for (int i = 0; i < A.Length; i++)
{
if (A[i] != -1 && A[i] != i)
{
int x = A[i];
// check if desired
// place is not vacate
while (A[x] != -1 && A[x] != x)
{
// store the value
// from desired place
int y = A[x];
// place the x to its
// correct position
A[x] = x;
// now y will become x,
// now search the place
// for x
x = y;
}
// place the x to its
// correct position
A[x] = x;
// check if while loop
// hasn't set the correct
// value at A[i]
if (A[i] != i)
{
// if not then put -1
// at the vacated place
A[i] = -1;
}
}
}
return A;
}
// Driver Code
static void Main()
{
int[] A = new int[] { -1, -1, 6, 1, 9,
3, 2, -1, 4, -1 };
Console.WriteLine(string.Join(",", fix(A)));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
<script>
// Javascript program for rearrange an
// array such that arr[i] = i.
// Function to rearrange an
// array such that arr[i] = i.
function fix(A, len)
{
for (let i = 0; i < len; i++)
{
if (A[i] != -1 &&
A[i] != i)
{
let x = A[i];
// check if desired
// place is not vacate
while (A[x] != -1 &&
A[x] != x)
{
// store the value
// from desired place
let y = A[x];
// place the x to its
// correct position
A[x] = x;
// now y will become x,
// now search the place
// for x
x = y;
}
// place the x to its
// correct position
A[x] = x;
// check if while loop hasn't
// set the correct value at A[i]
if (A[i] != i)
{
// if not then put -1
// at the vacated place
A[i] = -1;
}
}
}
}
// Driver Code
let A = new Array(-1, -1, 6, 1, 9,
3, 2, -1, 4, -1);
let len = A.length;
fix(A, len);
for (let i = 0; i < len; i++)
document.write(A[i] + " ");
// This code is contributed by gfgking
</script>
<?php
// PHP program for rearrange an
// array such that arr[i] = i.
// Function to rearrange an
// array such that arr[i] = i.
function fix(&$A, $len)
{
for ($i = 0; $i < $len; $i++)
{
if ($A[$i] != -1 &&
$A[$i] != $i)
{
$x = $A[$i];
// check if desired
// place is not vacate
while ($A[$x] != -1 &&
$A[$x] != $x)
{
// store the value
// from desired place
$y = $A[$x];
// place the x to its
// correct position
$A[$x] = $x;
// now y will become x,
// now search the place
// for x
$x = $y;
}
// place the x to its
// correct position
$A[$x] = $x;
// check if while loop hasn't
// set the correct value at A[i]
if ($A[$i] != $i)
{
// if not then put -1
// at the vacated place
$A[$i] = -1;
}
}
}
}
// Driver Code
$A = array(-1, -1, 6, 1, 9,
3, 2, -1, 4, -1);
$len = count($A);
fix($A, $len);
for ($i = 0; $i < $len; $i++)
echo ($A[$i]." ");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Output
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)
Auxiliary Space: O(1)
Another Approach (Using Set) :
1) Store all the numbers present in the array into a Set
2) Iterate through the length of the array, if the corresponding position element is present in the Set, then set A[i] = i, else A[i] = -1
Below is the implementation of the above approach.
#include <iostream>
#include <unordered_set>
using namespace std;
void fixArray(int arr[], int n)
{
// a set
unordered_set<int> s;
// Enter each element which is not -1 in set
for(int i=0; i<n; i++)
{
if(arr[i] != -1)
s.insert(arr[i]);
}
// Navigate through array,
// and put A[i] = i,
// if i is present in set
for(int i=0; i<n; i++)
{
// if i(index) is found in hmap
if(s.find(i) != s.end())
{
arr[i] = i;
}
// if i is not found
else
{
arr[i] = -1;
}
}
}
// Driver Code
int main() {
// Array initialization
int arr[] {-1, -1, 6, 1, 9,
3, 2, -1, 4,-1};
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
fixArray(arr, n);
// Print output
for(int i=0; i<n; i++)
cout << arr[i] << ' ';
return 0;
}
// this code is contributed by dev chaudhary
// Java program for rearrange an
// array such that arr[i] = i.
import java.util.*;
import java.lang.*;
class GfG {
// Function to rearrange an array
// such that arr[i] = i.
public static int[] fix(int[] A)
{
Set<Integer> s = new HashSet<Integer>();
// Storing all the values in the HashSet
for(int i = 0; i < A.length; i++)
{
s.add(A[i]);
}
for(int i = 0; i < A.length; i++)
{
if(s.contains(i))
A[i] = i;
else
A[i] = -1;
}
return A;
}
// Driver code
public static void main(String[] args)
{
int A[] = {-1, -1, 6, 1, 9,
3, 2, -1, 4,-1};
// Function calling
System.out.println(Arrays.toString(fix(A)));
}
}
# Python3 program for rearrange an
# array such that arr[i] = i.
# Function to rearrange an array
# such that arr[i] = i.
def fix(A):
s = set()
# Storing all the values in the Set
for i in range(len(A)):
s.add(A[i])
for i in range(len(A)):
# check for item if present in set
if i in s:
A[i] = i
else:
A[i] = -1
return A
# Driver code
if __name__ == "__main__":
A = [-1, -1, 6, 1, 9,
3, 2, -1, 4,-1]
print(fix(A))
# This code is contributed by Chitranayal
using System;
using System.Collections.Generic;
public class main{
static void fix(int[] a,int n){
HashSet<int> hs=new HashSet<int>();
// 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={-1, -1, 6, 1, 9,
3, 2, -1, 4,-1};
int n=arr.Length;
fix(arr,n);
for(int i=0;i<n;i++)
Console.Write(arr[i]+" ");
Console.WriteLine();
}
}
<script>
// JavaScript program for rearrange an
// array such that arr[i] = i.
// Function to rearrange an array
// such that arr[i] = i.
function fix(A)
{
let s = new Set();
// Storing all the values in the HashSet
for(let i = 0; i < A.length; i++)
{
s.add(A[i]);
}
for(let i = 0; i < A.length; i++)
{
if(s.has(i))
A[i] = i;
else
A[i] = -1;
}
return A;
}
let A = [-1, -1, 6, 1, 9, 3, 2, -1, 4,-1];
// Function calling
let ans = fix(A);
for(let i = 0; i < ans.length; i++)
{
document.write(ans[i] + " ");
}
</script>
Output
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)
Auxiliary Space: O(n)
Another Approach (Swap elements in Array) : Using cyclic sort
1) Iterate through elements in an array
2) If arr[i] >= 0 && arr[i] != i, put arr[i] at i ( swap arr[i] with arr[arr[i]])
Below is the implementation of the above approach.
// C++ program for rearrange an
// array such that arr[i] = i.
#include <iostream>
using namespace std;
void fixArray(int arr[], int n)
{
int i = 0;
while (i < n) {
int correct = arr[i];
if (arr[i] != -1 && arr[i] != arr[correct]) {
// if array element should be lesser than
// size and array element should not be at
// its correct position then only swap with
// its correct position or index value
swap(arr[i], arr[correct]);
}
else {
// if element is at its correct position
// just increment i and check for remaining
// array elements
i++;
}
}
return arr;
}
// Driver Code
int main()
{
int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
fixArray(arr, n);
// Print output
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
// This Code is Contributed by kothavvsaakash
// C program for rearrange an
// array such that arr[i] = i.
#include <stdio.h>
void fixArray(int arr[], int n)
{
for (int i = 0; i < n;)
{
if (arr[i] >= 0 && arr[i] != i)
arr[arr[i]] = (arr[arr[i]] + arr[i])
- (arr[i] = arr[arr[i]]);
else
i++;
}
}
// Driver Code
int main()
{
int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
fixArray(arr, n);
// Print output
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
// This Code is Contributed by Adarsh_Verma
// Java program for rearrange an
// array such that arr[i] = i.
import java.util.Arrays;
class Program
{
public static void main(String[] args)
{
int[] arr = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
for (int i = 0; i < arr.length;)
{
if (arr[i] >= 0 && arr[i] != i)
{
int ele = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = ele;
}
else
{
i++;
}
}
System.out.println(Arrays.toString(arr));
}
}
/* This Java code is contributed by PrinciRaj1992*/
# Python3 program for rearrange an
# array such that arr[i] = i.
if __name__ == "__main__":
arr = [-1, -1, 6, 1, 9,
3, 2, -1, 4, -1]
n = len(arr)
i = 0
while i < n:
if (arr[i] >= 0 and arr[i] != i):
(arr[arr[i]],
arr[i]) = (arr[i],
arr[arr[i]])
else:
i += 1
for i in range(n):
print(arr[i], end=" ")
# This code is contributed by Chitranayal
// C# program for rearrange an
// array such that arr[i] = i.
using System;
namespace GFG {
class Program {
static void Main(string[] args)
{
int[] arr = { -1, -1, 6, 1, 9,
3, 2, -1, 4, -1 };
for (int i = 0; i < arr.Length;)
{
if (arr[i] >= 0 && arr[i] != i)
{
int ele = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = ele;
}
else
{
i++;
}
}
Console.WriteLine(String.Join(",", arr));
}
}
}
// This code is contributed by
// Venkata VardhiReddy(venkata)
<script>
// Javascript program for rearrange an
// array such that arr[i] = i.
function fixArray(arr, n)
{
for (let i = 0; i < n;)
{
if (arr[i] >= 0 && arr[i] != i)
arr[arr[i]] = (arr[arr[i]] + arr[i])
- (arr[i] = arr[arr[i]]);
else
i++;
}
}
// Driver Code
let arr = [ -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 ];
let n = arr.length;
// Function Call
fixArray(arr, n);
// Print output
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This Code is Contributed by _saurabh_jaiswal
</script>
Output
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)
Auxiliary Space: O(1)
Another Approach (Using Vector) :
Follow these steps to rearrange an array
- Make a vector of size n and fill its every element by -1.
- Now traverse the input array and if any element is not equal to -1 then
- Fill that index of the vector which is equal to the element of the input array by that element’s value
- In last copy all elements of the vector into the input array and then return or print that input array
Code-
// C++ program for rearrange an
// array such that arr[i] = i.
#include <bits/stdc++.h>
using namespace std;
int* fixArray(int arr[], int n)
{
vector<int> vec(n, -1);
for (int i = 0; i < n; i++) {
if (arr[i] != -1) {
vec[arr[i]] = arr[i];
}
}
for (int i = 0; i < n; i++) {
arr[i] = vec[i];
}
return arr;
}
// Driver Code
int main()
{
int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
fixArray(arr, n);
// Print output
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
import java.util.*;
public class Main {
static int[] fixArray(int arr[], int n)
{
ArrayList<Integer> vec
= new ArrayList<>(Collections.nCopies(n, -1));
for (int i = 0; i < n; i++) {
if (arr[i] != -1) {
vec.set(arr[i], arr[i]);
}
}
for (int i = 0; i < n; i++) {
arr[i] = vec.get(i);
}
return arr;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
int n = arr.length;
// Function Call
fixArray(arr, n);
// Print output
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
# Python program for rearranging
# an array such that arr[i] = i.
def fixArray(arr, n):
vec = [-1]*n
# Traverse the array
for i in range(0, n):
# If arr[i] is not -1 then arr[i]
# is at its correct position.
if (arr[i] != -1):
vec[arr[i]] = arr[i]
# Copy vec[] to arr[]
for i in range(0, n):
arr[i] = vec[i]
return arr
# Driver code
arr = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
n = len(arr)
# Function call
fixArray(arr, n)
# Print output
for i in range(0, n):
print(arr[i], end=" ")
// C# code addition
using System;
class GFG
{
// Function to rearrange an
// array such that arr[i] = i.
static int[] FixArray(int[] arr, int n)
{
var vec = new int[n];
for (int i = 0; i < n; i++) {
vec[i] = -1;
}
for (int i = 0; i < n; i++) {
if (arr[i] != -1) {
vec[arr[i]] = arr[i];
}
}
for (int i = 0; i < n; i++) {
arr[i] = vec[i];
}
return arr;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
int n = arr.Length;
// Function Call
FixArray(arr, n);
// Print output
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// The code is contributed by Arushi Goel.
// JavaScript program for rearrange an
// array such that arr[i] = i.
function fixArray(arr) {
let n = arr.length;
let vec = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
if (arr[i] !== -1) {
vec[arr[i]] = arr[i];
}
}
for (let i = 0; i < n; i++) {
arr[i] = vec[i];
}
return arr;
}
// Driver Code
let arr = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1];
// Function Call
fixArray(arr);
// Print output
console.log(arr.join(" "));
Output-
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)
Auxiliary Space: O(n),for vector
Contact Us