LeetCode #703 Kth Largest Element in a Stream

Easy

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note:
You may assume that nums' length ≥ k-1 and k ≥ 1.

Solution — Binary Search Tree

Use a BST to store all numbers and find k-th largest start from root. Unfortunately, this approach will reach time limit.

Complexity

Build BST takes O(nlogn) time for inserting every number into the tree if n denotes to counts of numbers in nums.

For add operation, it go down from root to a leaf so the time complexity will be O(logn).

It uses O(n) extra space for this BST.

Solution — Min Heap

Maintain a k-size min heap for all numbers. Once there is a new number coming, push it into heap and pop the smallest one out if needed. Then return the most top number in heap.

Complexity

It takes O(n) time for building the heap (by bottom-up approach) if n denotes to length of nums list.

For add operation, both push and pop takes O(logn) time, so it’s time complexity is O(logn + 2logn) = O(logn).

This approach uses O(n) extra space for maintaining this heap.