Home » Data Structure » Array Data Structure

Rearrange the element such that array[i] = i

C++ implementation to rearrange the element such that array[i] = i using multiple approaches.
Submitted by Vikneshwar GK, on March 04, 2022

Consider an integer array, of size n, that has elements either from the range 0 to n-1 or -1. The task at hand is to arrange the array in such a way that the array[i] = i. If the corresponding element is not present, then fill the position with -1.

Example:

Input:
array[]= {2, 3, -1, 4, -1}

Output:
array[] = {-1, -1, 2, 3, 4}

Input:
array[]= {2, 1, -1, 0, 4, -1}

Output:
array[] = {0, 1, 2, -1, 4, -1}

Solution 1: Using Another Array

This method involves using an additional array and inserting the elements from the original array into the new array following the constraint of the given problem statement.

• Declare a new array of size n
• Iterate through the original array and place the element other than -1 in their corresponding position in the new array
• Now, iterate the new array and check if newarray[i] = i
• If yes, set array[i] = i, else array[i] = -1
• Print the array

C++ Implementation:

#include <iostream>
#include <unordered_set>

using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
    int newarray[length];

    for (int i = 0; i < length; i++) {
        // copy element into new array
        if (array[i] != -1) {
            newarray[array[i]] = array[i];
        }
    }
    for (int i = 0; i < length; i++) {
        // copy back from new array to original array
        if (newarray[i] != i) {
            array[i] = -1;
        }
        else {
            array[i] = i;
        }
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }
    rearrangeArray(array, N);
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 3
Enter element 3: -1
Enter element 4: 4
Enter element 5: -1
-1 -1 2 3 4

Time Complexity: O(n), where n is the length of the array.

Solution 2: Using Set

Set is a C++ STL container that stores unique elements in a sorted manner. We will use these features to facilitate our problem statement. It involves the following steps.

• Iterate the array and store the elements in the set
• Now iterate the array again and check if array[i] = i
• If not, check whether i is present in the set
• If present, set array[i] = i, else set it to -1
• Print the array

C++ Implementation:

#include <iostream>
#include <unordered_set>

using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
    // declare unordered set
    unordered_set<int> s;

    // copy array element to set
    // skip -1
    for (int i = 0; i < length; i++) {
        if (array[i] != -1)
            s.insert(array[i]);
    }

    for (int i = 0; i < length; i++) {
        // if i present if set
        if (s.find(i) != s.end()) {
            array[i] = i;
        }
        // if i not found
        else {
            array[i] = -1;
        }
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }
    rearrangeArray(array, N);
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: -1
Enter element 2: 0
Enter element 3: 4
Enter element 4: 2
Enter element 5: -1
Enter element 6: 1
0 1 2 -1 4 -1

Time Complexity: O(n), where n is the length of the array.

Solution 3: Using Swap

This method involves iterating through the array and swapping the array elements until the given constraint in the problem is satisfied. It involves the following steps.

• Iterate the array
• If array[i] != -1 and array[i] != i, swap the element with array[array[i]] and decrement the loop counter
• Print the array

C++ Implementation:

#include <iostream>
#include <unordered_set>

using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
    int temp;
    for (int i = 0; i < length; i++) {
        if (array[i] != -1 && array[i] != i) {
            temp = array[i];
            array[i] = array[array[i]];
            array[temp] = temp;
            i--;
        }
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }
    
    rearrangeArray(array, N);
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter element 6: 6
Enter element 7: 7
Enter element 8: -1
Enter element 9: 9
Enter element 10: 0
0 1 2 3 4 5 6 7 -1 9 

Time Complexity: O(n), where n is the length of the array.