Rearrange an array

Software Development
#1

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

  1. Nav­i­gate the numbers from 0 to n-1.
  2. Now navigate through array.
  3. If (i==a[j]) , then replace the element at i position with a[j] position.
  4. If there is any element in which -1 is used instead of the number then it will be replaced automatically.
  5. 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:

  1. Nav­i­gate 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 cor­rect posi­tion (i=A[i]) . If yes then ignore it.
  4. If a[i] != -1 and ele­ment a[i] is not at its cor­rect posi­tion (i!=A[i]) then place it to its correct posi­tion, 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 cor­rect 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) :

  1. Store all the numbers present in the array into a HashSet
  2. 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) :

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