SevenDeadlySins's blog

By SevenDeadlySins, history, 4 weeks ago, In English,

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

  1. add 5 at 0th index in list => list = [5]
  2. add 6 at 1st index in list => list = [5, 6]
  3. add 7 at 2nd index in list => list = [5, 6, 7]
  4. add 8 at 1st index in list => list = [5, 8, 6, 7]
  5. 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

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

treap.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    list     = [5, 8, 9, 6, 7]
    position = [0, 1, 2, 1, 2]
    

    By your method, solution would be

    list     = [5, 8, 6, 9, 7]
    position = [0, 1, 1, 2, 2]