Get Min/Max in O(1) time from a Queue?
data-structures, java
Solution
You only have 2 ways to get O(1) for a min/max operation:
- if the structure is sorted and you know where the max / min is located
- if the structure is not sorted and only allows insertion: you can recalculate the min / max every time you insert an item and store the value separately
- if the structure is not sorted and allows insertions and removals: I don't think you can do better than O(n), unless you use more than one collection (but that solution does not support removal of any elements, only head / tail elements, which should be the case with a queue).
Problem
How can I retrieve the max and min element from a queue at any time in 0(1) time complexity? Earlier I was using Collections.max and min to find the elements but that would be 0(n).