SevenDeadlySins's blog

N insertion in a list
By SevenDeadlySins, history, 5 years 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

»
5 years 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).

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

treap.

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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?

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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]
    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I found a better approach for this,

Method:: Make an ordered_set_pair<long double, int> named set. insert {0,-1} and {1,-1} in it. traverse elements and insert {val,ind} in it. where ind is index of that element i.e. 0,1,2,3,..,n-1 val is (set.find_by_order(position[i])->first + set.find_by_order(position[i]+1)->first)/2

after inserting all the elements in set. traverse set and make answer array. answer[i] = elements[set.find_by_order(i+1)->second]

Logic:: Here, we have set two boundries 0 and 1. If we want to insert elements at some position, we will find it's future neighbours and assign average of them to it. In this case for the first element we will assign 0.5. Similary when we assign values in between, at the end we have our array handy in the set by order.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If n is around 1e5, this immediately fails since in the worse case, we might have to compute 1/2^n and long double's precision won't cut it.

    → Reply