Interview Shuriken 52: Sort the Objects


You are given an array containing ‘n’ objects. On their creation, each object was given a creation number, which is a unique number from 1 to ‘n’. This means that an object with creation number ‘4’ was created just before the object with creation number ‘5’.

You have to sort the objects in-place on their creation number in O(n) and without any extra space. For simplicity, let’s assume you are given an integer array containing only the creation numbers, though each number is actually an object.

Example 1:

Input: [3, 1, 5, 4, 2]

Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]

Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]

Output: [1, 2, 3, 4, 5, 6]

Input Format:
The first line of input contains an integer, that denotes the value of n. The following line contains n space separated integers, that denotes the creation numbers of n objects.
Constraints:
1 <= N <= 100000
1 <= A[i] <= N 
Time Limit: 0.5 seconds.
Output Format:
The first and only line of output contains sorted creation numbers.
Sample Input 1:
6
1 5 6 4 3 2
Sample Output 1:
1 2 3 4 5 6


Comments

Popular posts from this blog

Access and modify all the resources of our Wiki.js using WikiJS API

MySQL Multi Source Master Slave Replication using GTID

How to pass parameters in webhook?