Problem Link - Find the Permutation
Problem Statement
A permutation of the numbers 1,...,N is a rearrangment of these numbers. For example
2~~4~~5~~1~~7~~6~~3~~8
is a permutation of 1,2,...,8. Of course,
1~~2~~3~~4~~5~~6~~7~~8
is also a permutation of 1,2,...,8.
Associated with each permutation of N is a special sequence of positive integers of length N called its inversion sequence. The i-th element of this sequence is the number of numbers j that are strictly less than i and appear to the right of i in this permutation. For the permutation
2~~4~~5~~1~~7~~6~~3~~8
the inversion sequence is
0~~1~~0~~2~~2~~1~~2~~0
The 2nd element is 1 because 1 is strictly less than 2 and it appears to the right of 2 in this permutation. Similarly, the 5th element is 2 since 1 and 3 are strictly less than 5 but appear to the right of 5 in this permutation and so on.
As another example, the inversion sequence of the permutation
8~~7~~6~~5~~4~~3~~2~~1
is
0~~1~~2~~3~~4~~5~~6~~7
In this problem, you will be given the inversion sequence of some permutation. Your task is to reconstruct the permutation from this sequence.
Approach
To reconstruct the permutation from the given inversion sequence, we can use the concept of the inversion sequence to build the result step by step. We start by iterating over each value in the inversion sequence. For each value, it represents the number of elements smaller than the current number that have already been placed to the right of it. Based on this information, we can insert the current number at the correct position in the result list. The insert operation is used to place the current number at the correct position in the result list, and the inversion sequence guides where to insert the numbers. The logic relies on progressively inserting each number, from 1 to N, based on its corresponding inversion count.
Time Complexity
The time complexity of the algorithm is O(N^2) because for each insertion operation, it can take up to O(N) time to find the correct position, and we perform N insertions.
Space Complexity
The space complexity is O(N) since we need an array to store the permutation of size N.