I recently had to solve this problem for a test, but was not able to find an efficient solution for the same.

Is it possible to make 'n' insertions to a linked list efficiently when we are given the positions of all insertion, and the element which has to be inserted.

`Eg: position = [0,1,2,1,2] , elements = [5,6,7,8,9], list = []`

So basically the operations we would be doing are

- add 5 at 0th index in list =>
`list = [5]`

- add 6 at 1st index in list =>
`list = [5, 6]`

- add 7 at 2nd index in list =>
`list = [5, 6, 7]`

- add 8 at 1st index in list =>
`list = [5, 8, 6, 7]`

- add 9 at 2nd index in list =>
`list = [5, 8, 9, 6, 7]`

So the final list would be `[5, 8, 9, 6, 7]`

Does anyone know an efficient solution for the same? (better than O(n^2)) In the original problem the elements to be inserted are between 0 to n-1

Auto comment: topic has been updated by SevenDeadlySins (previous revision, new revision, compare).treap.

Can you plz elaborate on the solution? I was thinking on these lines but couldn't reach a concrete solution.

Segment tree is enough, try to add elements from the last to the first one.

Can you plz elaborate on the solution? How are using segment tree? and for what?

Huh, I messed something up, but I’ve come up with another solution. Let’s find the rightmost 0, we know it’d be the 0-th element. Also all elements before him, should move „one position to the right” so we add 1 to the elements, which were before this one. We can see that we can go on with this algorithm, so in every step: we pick rightmost minimum, add 1 to all elements before this one (on prefix) and then change this element to inf. We can handle this operations with seg tree.

That's working. Thanks for your help.

let's turn these two arrays into a list of queries.

the i-th query will be represented as [position, element, index] where index is i

this holds true for any two queries:

- the one with the smaller position value comes first in output list

- but when two positions are equal, a query processed later will come first

Solution:

sort this list of queries by position in ascending order or by index in descending order if positions are equal

append to linked list in order of sorted query list.

This method doesn't work. Please observe the position of element at which it was inserted.

By your method, solution would be