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.
Am I the only one finding the problem statement a bit ambiguous ?
Not really. It's as messy as your hair.
Not really messy, but I don't think there is a solution that works in O(N).
I think it could be solved using Segment Tree and Lazy Propagation
That will be O(NlogN).
that's the best thing i can think about, is there any O(N) Solution??? guess not :\
Are you sure you need O(N)? All I can make up is O(NlogN).
I think we can use the fact that a[i] will only decrease or at least, never increase.
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.
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.
We can do it simply, but it won't be O(N).
Yeah, I realized that.
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)
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?
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:
Edit: this cannot be updated for previously deleted elements, hence seems like solution is not O(N)
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.
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
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.
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]
Yeah, you are right. I made a mistake.
I got it. Good solution!
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.
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.
Improving on @gvaibhav21's approach ,Time Complexity — O(n)