“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.

Table of Contents

## 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.

**Please click Like if you loved this article?**

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.