### nipul1's blog

By nipul1, history, 6 weeks ago,

yesterday I had a coding interview in which I was asked the following problem which I was not able to solve. please help me to figure out an approach for this problem.

Problem: Alex has a permutation of first n natural numbers in an array A for this permutation he has calculated another array B which is done as follows

B[i] will contain the number of elements on left of index i which are bigger then a[i], now somehow Array A is lost then we have to regenerate the array A from array B.

• +4

 » 6 weeks ago, # |   0 This problem is quite similar to https://codeforces.com/contest/1208/problem/DYou can initialise all elements of a Fenwick tree to 1 and binary search for the value while traversing array B from right to left and updating the found value to 0.
•  » » 6 weeks ago, # ^ |   0 Thank you.
 » 6 weeks ago, # | ← Rev. 2 →   0 You can determine the last element as n — b[n]. Now proceed from the back and keep a track of the used up elements and the available elements and check if placing a given value satisifies the constraint. Naively I think it can be done in O(n ^ 2) and then optimise using sets.The assertion I think would be that the permutation is unique as at any stage our invariant is that there is a finite list and only placing a particular element would satisfy the constraint. The invariant holds vacuously at the end(pos = n) and hence it will hold at termination as well
•  » » 6 weeks ago, # ^ |   0 oh i was close to this but I got distracted from this approach.
 » 6 weeks ago, # | ← Rev. 2 →   +3 You can use a segment tree to mark the visited elements as 0(set all indices of segment tree to 1 initially) and then query for sum range in segment tree whose value is b[i] while traversing b from back.Sorry for my English.
•  » » 6 weeks ago, # ^ |   +1 thanks for sharing.
 » 6 weeks ago, # |   +11 You can solve it from the rightmost element using fenwick/segment tree + binary search in O(n log^2(n)).Another alternatives is to use pbds or bbst and then solve them in O(n log(n)).