Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

0 0 6 minutes read

Given an array arr[] of size n where every element is in the range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]]. This should be done with O(1) extra space

Examples:

Input: arr[] = {3, 2, 0, 1}
Output: arr[] = {1, 0, 3, 2}
Explanation:
In the given array
arr[arr[0]] is 1 so arr[0] in output array is 1
arr[arr[1]] is 0 so arr[1] in output array is 0
arr[arr[2]] is 3 so arr[2] in output array is 3
arr[arr[3]] is 2 so arr[3] in output array is 2

Input: arr[] = {4, 0, 2, 1, 3}
Output: arr[] = {3, 4, 2, 0, 1}
Explanation:
arr[arr[0]] is 3 so arr[0] in output array is 3
arr[arr[1]] is 4 so arr[1] in output array is 4
arr[arr[2]] is 2 so arr[2] in output array is 2
arr[arr[3]] is 0 so arr[3] in output array is 0
arr[arr[4]] is 1 so arr[4] in output array is 1

Input: arr[] = {0, 1, 2, 3}
Output: arr[] = {0, 1, 2, 3}
Explanation:
arr[arr[0]] is 0 so arr[0] in output array is 0
arr[arr[1]] is 1 so arr[1] in output array is 1
arr[arr[2]] is 2 so arr[2] in output array is 2
arr[arr[3]] is 3 so arr[3] in output array is 3

Let’s assume an element is a and another element is b, both the elements are less than n. So if an element a is incremented by b*n. So the element becomes a + b*n so when a + b*n is divided by n then the value is b and a + b*n % n is a.

The array elements of the given array lie from 0 to n-1. Now an array element is needed that can store two different values at the same time. To achieve this, every element at ith index is incremented by (arr[arr[i]] % n)*n. After the increment operation of the first step, every element holds both old values and new values. An old value can be obtained by arr[i]%n and a new value can be obtained by arr[i]/n.

Follow the steps below the solve the given problem:

Traverse the array from start to end.
For every index increment the element by array[array[index] ] % n. To get the ith element find the modulo with n, i.e array[index]%n.
Again Traverse the array from start to end
Print the ith element after dividing the ith element by n, i.e. array[i]/n.

Below is the implementation of the above approach:

C++

#include <iostream>
using namespace std;
 
// The function to rearrange an array
// in-place so that arr[i] becomes arr[arr[i]].
void rearrange(int arr[], int n)
{
    // First step: Increase all values by (arr[arr[i]]%n)*n
    for (int i = 0; i < n; i++)
        arr[i] += (arr[arr[i]] % n) * n;
 
    // Second Step: Divide all values by n
    for (int i = 0; i < n; i++)
        arr[i] /= n;
}
 
// A utility function to print an array of size n
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
/* Driver program to test above functions*/
int main()
{
    int arr[] = { 3, 2, 0, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Given array is \n";
    printArr(arr, n);
 
    rearrange(arr, n);
 
    cout << "Modified array is \n";
    printArr(arr, n);
    return 0;
}

Java

class Rearrange {
    // The function to rearrange an array in-place so that
    // arr[i] becomes arr[arr[i]].
    void rearrange(int arr[], int n)
    {
        // First step: Increase all values by
        // (arr[arr[i]]%n)*n
        for (int i = 0; i < n; i++)
            arr[i] += (arr[arr[i]] % n) * n;
 
        // Second Step: Divide all values by n
        for (int i = 0; i < n; i++)
            arr[i] /= n;
    }
 
    // A utility function to print an array of size n
    void printArr(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println("");
    }
 
    /* Driver program to test above functions */
    public static void main(String[] args)
    {
        Rearrange rearrange = new Rearrange();
        int arr[] = { 3, 2, 0, 1 };
        int n = arr.length;
 
        System.out.println("Given Array is :");
        rearrange.printArr(arr, n);
 
        rearrange.rearrange(arr, n);
 
        System.out.println("Modified Array is :");
        rearrange.printArr(arr, n);
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to Rearrange
# an array so that arr[i] becomes
# arr[arr[i]]
 
# The function to rearrange an
# array in-place so that arr[i]
# becomes arr[arr[i]].
 
 
def rearrange(arr, n):
 
    # First step: Increase all values
    # by (arr[arr[i]] % n) * n
    for i in range(0, n):
        arr[i] += (arr[arr[i]] % n) * n
 
    # Second Step: Divide all values
    # by n
    for i in range(0, n):
        arr[i] = int(arr[i] / n)
 
# A utility function to print
# an array of size n
 
 
def printArr(arr, n):
 
    for i in range(0, n):
        print(arr[i], end=" ")
    print("")
 
 
# Driver program
arr = [3, 2, 0, 1]
n = len(arr)
 
print("Given array is")
printArr(arr, n)
 
rearrange(arr, n)
print("Modified array is")
printArr(arr, n)
 
# This code is contributed by shreyanshi_arun

C#

// C# Program to rearrange an array
// so that arr[i] becomes arr[arr[i]]
// with O(1) extra space
using System;
 
class Rearrange {
 
    // Function to rearrange an
    // array in-place so that arr[i]
    // becomes arr[arr[i]].
    void rearrange(int[] arr, int n)
    {
 
        // First step: Increase all values
        // by (arr[arr[i]] % n) * n
        for (int i = 0; i < n; i++)
            arr[i] += (arr[arr[i]] % n) * n;
 
        // Second Step: Divide all values by n
        for (int i = 0; i < n; i++)
            arr[i] /= n;
    }
 
    // A utility function to
    // print an array of size n
    void printArr(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine("");
    }
 
    //  Driver Code
    public static void Main()
    {
        Rearrange rearrange = new Rearrange();
        int[] arr = { 3, 2, 0, 1 };
        int n = arr.Length;
 
        Console.Write("Given Array is :");
        rearrange.printArr(arr, n);
 
        rearrange.rearrange(arr, n);
 
        Console.Write("Modified Array is :");
        rearrange.printArr(arr, n);
    }
}
 
// This code has been contributed by Nitin Mittal.

PHP

<?php 
// The function to rearrange an array 
// in-place so that arr[i] becomes arr[arr[i]].
function rearrange(&$arr, $n)
{
    // First step: Increase all values
    // by (arr[arr[i]]%n)*n
    for ($i = 0; $i < $n; $i++)
        $arr[$i] += ($arr[$arr[$i]] % $n) * $n;
 
    // Second Step: Divide all values by n
    for ($i = 0; $i < $n; $i++)
        $arr[$i] = intval($arr[$i] / $n);
}
 
// A utility function to print 
// an array of size n
function printArr(&$arr, $n)
{
    for ($i = 0; $i < $n; $i++)
        echo $arr[$i] ." ";
    echo "\n";
}
 
 
// Driver Code
$arr = array(3, 2, 0, 1);
$n = sizeof($arr);
 
echo "Given array is \n";
printArr($arr, $n);
 
rearrange($arr, $n);
 
echo "Modified array is \n";
printArr($arr, $n);
 
// This code is contributed 
// by ChitraNayal
?>

Javascript

<script>
// The function to rearrange an array 
// in-place so that arr[i] becomes arr[arr[i]].
function rearrange(arr, n)
{
 
    // First step: Increase all values by (arr[arr[i]]%n)*n
    for (let i = 0; i < n; i++)
        arr[i] += (arr[arr[i]] % n) * n;
 
    // Second Step: Divide all values by n
    for (let i = 0; i < n; i++)
        arr[i] = Math.floor(arr[i] / n);
}
 
// A utility function to print an array of size n
function printArr(arr, n)
{
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
    document.write("<br>");
}
 
/* Driver program to test above functions*/
    let arr = [3, 2, 0, 1];
    let n = arr.length;
 
    document.write("Given array is <br>");
    printArr(arr, n);
    rearrange(arr, n);
 
    document.write("Modified array is <br>");
    printArr(arr, n);
 
// This code is contributed by Surbhi Tyagi.
</script>

Output

Given array is 
3 2 0 1 
Modified array is 
1 0 3 2

Time Complexity: O(N), Only two traversal of the array is needed. So time complexity is O(N).
Auxiliary Space: O(1), No extra space is required.

Note: The problem with the above solution is, that it may cause an overflow.

The credit for this solution goes to Ganesh Ram Sundaram.

Here is a better solution:
Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!