Python Program to Rearrange Array

In this problem, we are given an array and we have to rearrange the elements of the array such that for each index i, arr[i] = i. We have to rearrange the elements so that each element is in the position corresponding to its value.

Scenario 1

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

Element 3 is the largest, so it is moved to the last index, 0 is the smallest element, so itismoved to the first index, 2 is moved to the third index, and 1 is moved to the second index.

Scenario 2

Input: [5, 2, 8, 1]
Output: [1, 2, 5, 8]

Element 8 is the largest, so it is moved to the last index. 1 is the smallest element, so it is moved to the first index. 2 is placed at the second position, and 5 is placed at the third position.

Brute Force Approach

In this brute force approach, we will create a new array and initialize it with zeros. Now, we iterate through the given input array. For each element of the array, we place it in the array at the index equal to its value. Now, copy the new array back into the original array.

Example

def rearrange(arr):
    n = len(arr)
    new_arr = [0] * n
    for i in range(n):
        new_arr[arr[i]] = arr[i]
    for i in range(n):
        arr[i] = new_arr[i]
    return arr
arr = [3, 0, 2, 1]
print("array after rearranging:", rearrange(arr))

The output of the above program is as follows -

array after rearranging: [0, 1, 2, 3]

Time Complexity: The time complexity of this approach is O(n).

Efficient Approach

In this approach, we try to reduce the space complexity by reducing the extra space we used in the brute force approach. In the efficient approach, we use the given input to rearrange the elements such that arr[i] = i. We use cyclic replacements to place each element in its correct position.

Example

def rearrange(arr):
   n = len(arr)
   for i in range(n):
      while arr[i] != i:
         arr[arr[i]], arr[i] = arr[i], arr[arr[i]]
   return arr
arr = [3, 0, 2, 1]
print("array after rearranging:", rearrange(arr))

The output of the above program is as follows -

array after rearranging: [0, 1, 2, 3]

Time Complexity: The time complexity of this approach is O(n).