Problem

Given an array arr of size n where every element is in the range [0, n-1], rearrange the array so that arr[i] becomes arr[arr[i]] for every index i, using only O(1) extra space.

Constraints

  • All elements in the array are in the range [0, n-1].
  • n * n does not overflow for a signed integer.

Examples

Example 1

1
2
3

Input: [1, 0]
Output: [0, 1]
Explanation: arr[0] becomes arr[arr[0]] = arr[1] = 0, arr[1] becomes arr[arr[1]] = arr[0] = 1.

Example 2

1
2
3

Input: [3, 2, 0, 1]
Output: [1, 0, 3, 2]
Explanation: arr[0] becomes arr[arr[0]] = arr[3] = 1, arr[1] becomes arr[arr[1]] = arr[2] = 0, etc.

Example 3

1
2

Input: [4, 0, 2, 1, 3]
Output: [3, 4, 2, 0, 1]

Solution

Method 1 – In-Place Encoding with Modular Arithmetic

Intuition

We need to update each element to its new value, but if we overwrite elements directly, we lose information needed for future updates. The trick is to encode both the old and new values at each index using modular arithmetic, since all values are in [0, n-1].

Approach

  1. For each index i, encode the new value at arr[i] by adding (arr[arr[i]] % n) * n to arr[i]. Now, arr[i] contains both the old and new value.
  2. After the first pass, extract the new value for each index by dividing arr[i] by n.
  3. This works because:
    • The old value is arr[i] % n.
    • The new value is arr[i] / n (integer division).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
	void rearrange(vector<int>& arr) {
		int n = arr.size();
		for (int i = 0; i < n; ++i) {
			arr[i] += (arr[arr[i]] % n) * n;
		}
		for (int i = 0; i < n; ++i) {
			arr[i] /= n;
		}
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
	public void rearrange(ArrayList<Integer> arr) {
		int n = arr.size();
		for (int i = 0; i < n; i++) {
			arr.set(i, arr.get(i) + (arr.get(arr.get(i)) % n) * n);
		}
		for (int i = 0; i < n; i++) {
			arr.set(i, arr.get(i) / n);
		}
	}
}
1
2
3
4
5
6
7

class Solution:
	def rearrange(self, arr: list[int]) -> None:
		n = len(arr)
		for i in range(n):
			arr[i] += (arr[arr[i]] % n) * n
		for i in range(n):
			arr[i] //= n

Complexity

  • ⏰ Time complexity: O(n) — Each element is visited twice (once for encoding, once for decoding).
  • 🧺 Space complexity: O(1) — No extra space is used except for variables.