Hello Everyone,
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++
// C++ program for above approach
#include <iostream>
using
namespace
std;
// Function to tranform 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++)
{
// Checf 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);
}
Output
Array after Rearranging -1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n2)
Another Approach:
- Navigate through the array.
- Check if a[i] = -1, if yes then ignore it.
- If a[i] != -1, Check if element a[i] is at its correct position (i=A[i]) . If yes then ignore it.
- 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++
// 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] <<
" "
;
}
Output
-1 1 2 3 4 -1 6 -1 -1 9
Another Approach (Using HashSet) :
- Store all the numbers present in the array into a HashSet
- Iterate through the length of the array, if the corresponding position element is present in the HashSet, then set A[i] = i, else A[i] = -1
Below is the implementation of the above approach.
- C++
#include <iostream>
#include <unordered_map>
using
namespace
std;
//
void
fixArray(
int
arr[],
int
n)
{
// Initialize a hashmap
std::unordered_map<
int
,
int
> hmap;
// Enter each element in hmap
for
(
int
i{0}; i<n; i++)
{
if
(arr[i] != -1)
hmap[arr[i]] = 1;
}
// Navigate through array,
// and put A[i] = i,
// if i is present in hmap
for
(
int
i{0}; i<n; i++)
{
// if i(index) is found in hmap
if
(hmap.find(i) != hmap.end())
{
arr[i] = i;
}
// if i 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++)
std::cout << arr[i] <<
' '
;
return
0;
}
Output
-1 1 2 3 4 -1 6 -1 -1 9
Another Approach (Swap elements in Array) :
- Iterate through elements in an array
- If arr[i] >= 0 && arr[i] != i, put arr[i] at i ( swap arr[i] with arr[arr[i]])
Below is the implementation of above approach.
- C++
// 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]);
// Fucnction Call
fixArray(arr, n);
// Print output
for
(
int
i = 0; i < n; i++)
printf
(
"%d "
, arr[i]);
return
0;
}
Output
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)