Given an array of `n elements`. `‘k’ operations` need to be performed on the array. ↵
↵
For each operation `start_index, end_index,trim_value` is given. One has to 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`. `for each A[i] for i between start and end , A[i] = min(A[i],h)` .↵
↵
↵
After performing, ‘k’ such operations find the `maximum value of the array`.↵
↵
I have a solution of `O(n + k*log(n))`. I think it can be optimized to O( n*log(n) ) at least, if not better. ↵
↵
Note: Please try `not` to use `Segment tree or BIT`. ↵
↵
Constraints -> `n<=10^6 (sure)` , `A[i] <= 10^6 (Not quite sure of this though)`↵
↵
For Eg. Given array = `7, 2, 8, 5, 1, 6, 4` and `k = 3`↵
↵
Following are the k operation `(start, end, value)` -↵
↵
`1 3 4` => Now the array = `4, 2, 4, 5, 1, 6, 4`↵
↵
`3 5 5` => Now the array = `4, 2, 4, 5, 1, 6, 4`↵
↵
`4 7 4` => Now the array = `4, 2, 4, 4, 1, 4, 4`↵
↵
So the `Maximum value` is `4` in the array.↵
↵
↵
For each operation `start_index, end_index,trim_value` is given. One has to 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`. `for each A[i] for i between start and end , A[i] = min(A[i],h)` .↵
↵
↵
After performing, ‘k’ such operations find the `maximum value of the array`.↵
↵
I have a solution of `O(n + k*log(n))`. I think it can be optimized to O( n*log(n) ) at least, if not better. ↵
↵
Note: Please try `not` to use `Segment tree or BIT`. ↵
↵
Constraints -> `n<=10^6 (sure)` , `A[i] <= 10^6 (Not quite sure of this though)`↵
↵
For Eg. Given array = `7, 2, 8, 5, 1, 6, 4` and `k = 3`↵
↵
Following are the k operation `(start, end, value)` -↵
↵
`1 3 4` => Now the array = `4, 2, 4, 5, 1, 6, 4`↵
↵
`3 5 5` => Now the array = `4, 2, 4, 5, 1, 6, 4`↵
↵
`4 7 4` => Now the array = `4, 2, 4, 4, 1, 4, 4`↵
↵
So the `Maximum value` is `4` in the array.↵
↵
