Rearrange an Array Such that arr[i] is equal to i

“Rearrange an array such that arr[i]=i”  problem states that you are given an array of integers ranging from 0 to n-1. Since all the elements may not be present in the array, then in place of them -1 is there. The problem statement asks to rearrange the array in such a way if a number between range is not present in an array then mark it as -1 and rearrange the elements as arr[i] = i.

Example

arr[]={9,4,-1,-1,2,7,8,1,5,-1}

[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

Explanation: Since any element is not present within the range then, it was replaced with -1 and that the array index is replaced with the number itself.

Algorithm for Rearrange an Array Such that arr[i] is equal i

1. Traverse the array from 0 to n-1(length of the array).
2. Check if arr[i] is greater than equal to 0 and not equal to i.
    1. Swap the elements by doing the following steps.
        1. temp = arr[arr[i]]
        2. arr[arr[i]] = arr[i]
        3. arr[i] = temp
3. Else increase the value of i.
4. Print the array.

Explanation

We are given an array of integers of size n. It will be containing the numbers within the range o to n-1. Some of the numbers can be missing from the range. We have asked to replace all the elements where arr[i] become the value as i. If there is no number present within the array we should replace it with the -1. Suppose we are having a range from 0 to 4. In which we have only 2 and 3 present in an array, and the rest is -1 as elements, then we have to place 2 and 3 at the index as arr[2] =2 and arr[3] =3 and the rest of the places will be marked as -1, if any of the numbers are not present within the range from 0 to 4.

We have given an array. Our main idea is to swap the elements of the array for solving “Rearrange an array such that arr[i] = i” problem. We are going to traverse the array from 0 to n-1 and check for each value of “i”. If arr[i] is greater than 0 so that we can avoid the negative numbers. There is also a condition applying there so that the loop will not go infinite, as we are increasing the value of ‘i’ in else part, so we are also checking that arr[i] should also not equal to “i”. So that it can skip and move further and check for further values.

We just need to swap those values which are greater than equal to 0 and are not equal to i. Also, we are swapping within the array with a single loop, within a range, that’s why we have taken an array of arr[i] values to swap. And at last print those values of the array.

Implementation

C++ program to Rearrange an Array Such that arr[i] is equal i

#include<iostream>

using namespace std;

void arrayRearrange(int arr[], int n)
{
    for (int i = 0; i < n;)
    {
        if (arr[i] >= 0 && arr[i] != i)
        {
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
        else
        {
            i++;
        }
    }
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main()
{
    int arr[] = {9,4,-1,-1,2,7,8,1,5,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayRearrange(arr,n);

    return 0;
}

-1 1 2 -1 4 5 -1 7 8 9

Java program to Rearrange an Array Such that arr[i] is equal i

import java.util.Arrays;

class arrayRearrange
{
    public static void main(String[] args)
    {
        int[] arr = {9,4,-1,-1,2,7,8,1,5,-1};
        for (int i = 0; i < arr.length;)
        {
            if (arr[i] >= 0 && arr[i] != i)
            {
                int temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                i++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

Complexity Analysis

Time Complexity

Since we were just traversing the array, we achieved linear time complexity. O(N) where “N” is the number of elements in the array for “Rearrange an array such that arr[i] = i” problem.

Space Complexity

The algorithm itself takes O(1) constant space but since the input is stored in an array. We get O(N) where “N” is the number of elements in the array.