How to solve following problem in Linear time ?
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.
Problem Link, look at round 3 question.
A simple offline solution would be to keep 2 sets on all indices, one for insert and one delete. For all updates, put value trim_value to the insertion set of start_index and deletion set of end_index. Now, iterate over the array keeping another multi-set storing all the updates that apply to current index, the value of this element is essentially min value in multi set and that value it self. Insertion and deletion are also done in O(\log N) as there are n updates. Time complexity is O(N \log N).
I have already solved this problem in O(NlongN). But Solution that was asked for Linear time.
Good question,me still waiting for answer as a beginner …
m also waiting.
@gandu007 can you give a link to the problem? I doubt there can be constraints that allow only O(n) solutions to pass…
Updated the link.
Its not correct.
let say array is-1,2,3,4,5,6,7
and queries are -
2 5 1,
1 2 1,
1 2 3,
1 3 4,
1 2 4,
2 3 1,
2 3 2
Then according to your soln answer should be min(1,1)=1.but as you process queries final answer will be 7.
Correct me if i am wrong.