Algorithms – Rearrange the Array of Given Range N, such that A[i]=i.

Objective: Given a array of length N, in which elements are in the range of 1 to N. All elements may not present in the array. If 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:

Rearrange the Array of Given Range N, such that A[i]=i

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

Navigate the array.

Check if element is -1, if yes then ignore it.

If element is not -1, Check if its at it correct position (i=A[i]), If yes then ignore it.

If element is not -1, and 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

Either A[i] is vacate, means A[i]=-1, then just put A[i]=i .

OR A[i] is not vacate, 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. .

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________