Google Coding Interview Question | Leetcode 1509 | Min Diff Between Max and Min Value in Three Moves

[@yitingg7942]

Thanks I feel this question is easy to code but hard to think of.

[@jkim5118]

Why is the optimal solution O(N)? Storing 4 mins/maxes into the PQ would take O(NlogN). Wouldn't it?

[@EshwarNorthEast]

At a time you would have only 4 values in the heap. I supposes its N log 4 which is N since log 4 is a constant.
Hope it is clear.

[@aw6507]

this doesn't seem to work if there are duplicate?

[@jay-rathod-01]

It was fun