140. Rearrange Array Elements (A[i] = i) | In-place Approach

Objective: Given an array of length N, in which elements are in the range of 1 to N. All elements may not present in the array. If the element is not present, there will be -1 present in the array. Rearrange the array such that A[i]=i and if i is not present, display -1 at that place. See example

Example:

Approach: - Time Complexity -O(N), Space Complexity - O(1)

1. Navigate the array.
2. Check if the element is -1, if yes then ignore it.
3. If the element is not -1, Check if at its correct position (i=A[i]), If yes then ignore it.
4. If the element is not -1, and the element is not at its correct position (i!=A[i]) then We need to place it to its correct position but there are two conditions
   1. Either A[i] is vacate, which means A[i]=-1, then just put A[i]=i .
   2. OR A[i] is not vacated, which means A[i]=x, then int y=x put A[i]=i. Now we need to place y to its correct place, so repeat from step 3.

Output:

Fixed Indexed Array [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Fixed Indexed Array [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Related Problems:

- Stable Marriage Problem - Gale–Shapley Algorithm Hard
- Find the last repeating character in a given string Beginner
- Replace array elements with maximum element on the right. Medium
- Given an array, count the number of pairs with a given sum. Beginner
- Determine If a String is Palindrome Beginner