Rearrange Array so that arr[i] Becomes arr[arr[i]]

Title: Rearrange Array so that arr[i] Becomes arr[arr[i]]

If you are given an array where every value is itself a valid index into that same array, you can remap every slot to point at the value its index refers to, without allocating a second array. In this guide, we will build a clean, compilable Java program that rearranges an array so arr[i] becomes arr[arr[i]] for every index, using an encoding trick that keeps the whole operation in place.

You will learn why a naive rearrangement needs a second array, how a single multiply-and-mod trick lets you encode two values in one int slot, and how to walk through the algorithm one index at a time so the logic sticks. We will also cover the mistakes candidates make under interview pressure and the follow-up questions you should expect once the base solution is working.

Understanding the Problem

You are given an array arr of size n containing a permutation of the integers 0 to n - 1. You must transform the array so that, for every index i, the new value at arr[i] equals the old value that used to live at arr[arr[i]].

The obvious approach copies the original array, then fills a new array with copy[copy[i]] for each i. That works, but it costs O(n) extra space. The interesting version of this problem asks you to do the remapping in place, using only the original array and a constant number of extra variables.

The in-place trick relies on one property of the input: every value is already a valid index. That lets us temporarily store two numbers inside one int by encoding the old value and the new value together, then separating them again in a second pass.

Approach / Algorithm Steps

The core idea is to encode each original value and its target value into a single slot using n as a base, then decode every slot in a second pass. Follow these steps:

1. Capture n = arr.length once, before any mutation, since every encode and decode step depends on this exact value.
2. Loop over every index i from 0 to n - 1.
3. For each i, read arr[arr[i]] % n. The modulo recovers the original value even if that slot was already encoded earlier in this same pass.
4. Add (arr[arr[i]] % n) * n to arr[i], so the slot now holds original value + n * target value in a single int.
5. After the encoding loop finishes, every slot holds both its old and new value packed together.
6. Loop over every index i a second time and divide arr[i] by n, discarding the remainder that held the old value.
7. Each slot now holds exactly arr[arr[i]] from before the transformation, and the array has been rearranged with no extra array allocated.

Java Program

import java.util.Arrays;

public class RearrangeArray {

    public static void rearrange(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            arr[i] += (arr[arr[i]] % n) * n;
        }
        for (int i = 0; i < n; i++) {
            arr[i] /= n;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 0, 1};
        System.out.println("Original array: " + Arrays.toString(arr));
        rearrange(arr);
        System.out.println("Rearranged array: " + Arrays.toString(arr));
    }
}

Explanation of the Program

• rearrange first stores n once, since both the encode and decode loops need the exact same value to stay consistent.
• The first for loop never writes a plain new value. It always adds (arr[arr[i]] % n) * n to the existing arr[i], which packs the future value into the high part of the number while the low part (anything less than n) still reflects the original value.
• The % n on arr[arr[i]] is doing the real work: if that slot has already been encoded earlier in the same loop, it now holds originalValue + n * something, and taking it modulo n strips that n * something back off, leaving the original value exactly as it was before any encoding touched it.
• The second for loop is purely a cleanup pass. Dividing every arr[i] by n throws away the remainder, which is exactly the part that held the old value, and keeps the quotient, which is exactly the new value that was packed in during the first loop.
• main just prints the array before and after calling rearrange, so you can see the transformation happen on a 4-element permutation.

Step-by-Step Trace

Trace rearrange on arr = [4, 0, 2, 1, 3]. Index 2 maps to itself, which is a useful case to watch, and the expected final array is [3, 4, 2, 0, 1].

Notice row i = 3 reads arr[1], which was already encoded back in row i = 1; the % n recovers the original 0 from the encoded 20 instead of treating 20 as a literal value. After the encoding loop, arr holds [19, 20, 12, 1, 8]. Dividing every slot by 5 in the second loop gives [3, 4, 2, 0, 1], the expected result. At the end of the encoding loop, every arr[i] holds originalValue + n * targetValue, so a single division pass is enough to reveal targetValue everywhere at once.

Examples

Example 1: Identity Permutation

When arr[i] == i for every index, the rearrangement is a no-op, because arr[arr[i]] is just arr[i] again.

int[] arr = {0, 1, 2, 3};
rearrange(arr);
System.out.println(Arrays.toString(arr));
// Output: [0, 1, 2, 3]

Example 2: A Single 3-Cycle

arr = [2, 0, 1] is one cycle of length 3. Every index chases the next one around the cycle before landing back on itself.

int[] arr = {2, 0, 1};
rearrange(arr);
System.out.println(Arrays.toString(arr));
// Output: [1, 2, 0]

Example 3: Two Overlapping 2-Cycles

arr = [1, 3, 0, 2] contains two independent swaps happening at the same time: index 0 and index 2 trade values, and index 1 and index 3 trade values.

int[] arr = {1, 3, 0, 2};
rearrange(arr);
System.out.println(Arrays.toString(arr));
// Output: [3, 2, 1, 0]

Common Mistakes to Avoid

This encoding trick is compact, which also makes it easy to get subtly wrong. Watch for these mistakes:

• Skipping the modulo when reading – reading arr[arr[i]] without % n once that slot has already been encoded in the same pass returns the inflated value instead of the original one, corrupting every index that chains through it. Always read arr[arr[i]] % n, never the raw value.
• Dividing inside the encoding loop – dividing arr[i] by n right after encoding it destroys the original value before a later index can read it through arr[arr[i]], so any index that points at an earlier slot gets a wrong result. Keep the encode and decode steps in two completely separate loops.
• Applying this to non-permutation input – if arr contains duplicates or values outside 0 to n - 1, arr[arr[i]] either collides with another index or throws ArrayIndexOutOfBoundsException. Confirm the input is a true permutation of 0 to n - 1 before relying on this O(1)-space trick.
• Ignoring integer overflow for large n – the encoding step multiplies a value by n, so for a large array this can exceed Integer.MAX_VALUE and silently wrap around, producing a wrong decode. Switch to a long[] for large n, or fall back to the O(n) extra-array approach.

Edge Cases to Test

Walk through these input shapes before calling the implementation done:

• Empty array
• Single-element array (arr = [0])
• Identity permutation (arr[i] == i for every index)
• Array containing a self-mapped index among other cycles
• Values outside the 0 to n - 1 range
• Duplicate values (not a valid permutation)
• Large n where encoding risks int overflow
• Null array reference

Additional Considerations

The algorithm runs in O(n) time, two linear passes over the array, and uses O(1) extra space beyond the input array itself, since the encoding happens in place. This is the main advantage over the naive copy-based approach, which is also O(n) time but needs an O(n) auxiliary array.

The trade-off is fragility. The technique only works because every value doubles as a valid index, which lets you pack two numbers into one int without losing information. It does not generalize to arbitrary integer arrays, and it temporarily produces values up to roughly n * n, so it is only safe when n * n fits comfortably inside the chosen numeric type.

Interview Follow-up Questions

Once the base solution is working, expect the interviewer to push further:

• What if the array is not guaranteed to be a permutation of 0 to n – 1? – fall back to an auxiliary array of size n, fill it with arr[arr[i]] for every i using the original values, then copy it back; this costs O(n) extra space but handles arbitrary integers safely.
• What if n is large enough that the encoding multiplication overflows int? – switch the array to long[], or process the array in blocks small enough that each block’s n * n stays within int range.
• How would you verify, without extra space, that the input really is a permutation of 0 to n – 1? – use the sign bit of each slot as a visited marker: negate arr[v] the first time value v is seen, and if you ever encounter a value whose target slot is already negative, it is a duplicate.
• What if you needed to apply this remapping to an array too large to fit in memory? – this calls for an external, pass-based approach: store (index, value) pairs on disk sorted by index, then produce the remapped output with a single sequential merge pass instead of random access by index.

Conclusion

The arr[i] becomes arr[arr[i]] problem is a good test of whether you can see past the obvious O(n) space solution and find a way to pack two values into one slot safely. Once you understand why the % n read matters and why the encode and decode steps must stay in separate loops, the implementation itself is only a handful of lines.

Try adapting rearrange to validate its input first, or to detect and report cycle lengths as it walks the array, to build more confidence with this encoding style of in-place trick. You can learn more about array manipulation problems like this one in our Arrays category.