shubhamcr7's blog

How to solve N queries on array on N elements in linear time O(N).
By shubhamcr7, history, 8 years ago, In English

Given an array of n elements. ‘n’ operations needs to be performed on the array. For each operation start_index, end_index,trim_value is given. One has trim the value starting from the start_index to end_index inclusive. If the value at that index is more than or equal to trim value then make it equal to trim_value else leave it as it is. After performing ‘n’ operations find the maximum value of the array.

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

Comments Comments (24)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one finding the problem statement a bit ambiguous ?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it could be solved using Segment Tree and Lazy Propagation

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That will be O(NlogN).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      that's the best thing i can think about, is there any O(N) Solution??? guess not :\

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

Are you sure you need O(N)? All I can make up is O(NlogN).

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

I think we can use the fact that a[i] will only decrease or at least, never increase.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I had the same thoughts. Default answer is the maximum of all trims, the answer better that this can only be found in a point which is not covered by any segments. If there is a fast way to check whether the point is covered or not then we are done.

    Update: But the fastest way to check whether it's covered is O(N). I give up.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I am thinking in direction of a partial sum solution (where you update l_index and r+1_index)

      I mean, if we just want to know if a point is never updated, we can simply do that, right?

      Actually, we have to keep track of only those trim values that are <= max(a[i]) before each query. So, I guess maybe we can do something in offline mode.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

First sort all the updates in the increasing order of trim value using radix sort or counting sort.

Now, maintain 2 arrays: next[i] and prev[i] denoting the immediate next and previous untrimmed element from i.

Iterate over the updates in the increasing order of trim value and trim all elements in the required range , updating next[] and prev[] as you go.

If we consider the initial sorting of updates to be O(N) , total time complexity is O(N)

Edit: sorry, seems like it might not be possible to keep track of prev and next in amortized O(N)

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Good thinking!

    But, if I understand correctly, it's not O(n). It's like dsu so the complexity is not exactly O(n) but close to it. Isn't it?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Everything apart from sort will be amortized O(N), because each element will be trimmed at max. once. It's not like dsu, you simply have to update prev[] and next[] as follows:

      when you trim ith element, set:

      prev[next[i]] = prev[i];
next[prev[i]] = next[i];

      Edit: this cannot be updated for previously deleted elements, hence seems like solution is not O(N)

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        eg: sorted queries : { [3,6,v] , [2,8,v+1] , [4,10,v+3] , [1,5,v+2] }
        prev[i from 3 to 6]=2
        next[i from 3 to 6]=7

        prev[i from 2 to 2]=1
        next[i from 2 to 2]=next[3]=7
        prev[i from next[2] to 8]=1
        next[i from next[2] to 8]=9

        next[i from ( next[ next[4]==7 ]==9 ) to 10]=11 -> we see a chain forming

        But you're claiming that this chain will always have a size<=2, right? Let me think about it for a moment.

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

          You are right, I was only maintaining prev and next links for non-trimmed elements, but for this we would need the first non-trimmed element in the range of each query, which will bring in an extra log(n) factor. Looks like we are back to square one :D

          → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    This can be done even easier. If the sorting is O(N) then we can just sort the operations by left border and mark all the positions that were changed in O(N). Then we assume the default maximum value to be the maximum of all trims and watch every single position in O(N). If the position is not marked then we compare it with the maximum and check if it's better. Upd: mistake here, sorry.

    But is the sorting really O(N)? OP hasn't clarified it.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I don't think so.
      eg: array : [1 2 3]
      query : [1,3,100000]
      or
      array : [ 10 11 12 ] query : [ 1,3,10 ] => array : [10 10 10] query : [ 1,3,12 ] => array : [10 10 10]

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I got it. Good solution!

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

      By keeping a pointer of next and previous, you are skipping over the previously trimmed region. As the queries are sorted in increasing order, thus, once updated, an index won't get trimmed again.

      eg: sorted queries : { [3,6,v] , [2,8,v+1] , [1,5,v+2] , [4,6,v+3] }
      Once the segment [3,6] has been trimmed to v, it can't be trimmed further. So we skip it for all other queries.
      next[3]=next[6]=7
      prev[3]=prev[7]=2
      So, when we get the second query, we only update linearly from l to min(prev[i],r) and from max(l,next[i]) to r.

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

        Can someone prove the complexity? It doesn't look O(n) to me. The implementation follows a dsu like storage of representative node. The complexity is close to O(n) but not O(n). At least, that's what I think.

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    Improving on @gvaibhav21's approach ,Time Complexity — O(n)

    • sort trim_value using radix sort(tvs)
    • tvs //({ [3,6,v] , [2,8,v+1] , [4,10,v+3] , [1,5,v+2] }), trim_value_store
    • updated[] = {1}
    • for tv in tvs
      • i = tv.left
      • while(i <= tv.right)
        • arr[i] = min(arr[i], tv.val)
        • i += updated[i]
        • updated[i] = tv.right-i+1
    → Reply