I used a queue based solution with O(n2) worst time complexity and it passed in 0.03s.
could you tell me what is wrong with my solution i just found the max then after removing the smaller side of th hills i found the nex max and so on getting wrong answer.
In this, we are dividing the range into 2 unequal parts, with the best case being both of roughly equal size, giving O(log^2 N) complexity vs the worst case having O(N*logN) time complexity. one logN is due to calls to segment tree, rest due to recursive calls.
Well, I have never faced such scenario since I never initialized array size this way as you did in first.
I do not know.
Glad you liked
I used divide and conquer, worst case complexity O(nlogn).
here is my solution.
That’s the “greedy” algorithm; it will fail to find the best solution sometimes, for example
1 3 2 9 8 6 7 4 5
where the greedy approach will take 3 reservoirs but 2 is best case.
for sequence 4 1 9 5 7 3 2
is there consecutive i and i+1 such that both facing opposite direction for optimal solution
The optimal solution is Right oriented reservoir at the first and third position.