Use heap for O(n) solution if the O(nlogn) is deemed too slow!


#1

Because the ‘heapify’ operation is O(n) and we are selecting a constant number of integers (3), we can use two different heaps (a min and a max heap) to keep an O(n) running time.

  1. Max-heapify the list
  2. Pop the top 3 elements, storing the first one popped as our max int
  3. Min-heapify the list (after adding elements back, or operate on a copy of the list)
  4. Pop the top 2 elements
  5. Return max(min1min2max1, max1max2max3)

Note that we have 2O(n) + 5O(logn) = O(n) operations.


#2

The worst case time complexity is O(nlogn), while maintaining a heap. But it can be solve in O(n). Please correct me is i am wrong.


#3

Ankish you are wrong. Build heap takes order of n time to build a heap whereas max heapify that is to rebuild the heap takes order logn time .


#4

ankish. you maintain a heap of size 3. So maintaining each element takes O(log 3) and the overall time complexity for n elements is O(n log 3) which is still O(n) because log 3 is a constant.