Find Kth Largest Number in an Array : Python, C#, Java

Continuing on the journey to understand the strength and weakness of languages when solving algorithm problems, let us look at the leetcode problem of finding kth largest number in an array.

In essence, the most common way to address any algorithm problem that talks about kth largest or kth smallest element in an stream or an array, is to utilize a priority queue that keeps the internal set of elements in sorted order (insert would take log(k) where k is the size of priority queue) and lets you remove the min or max element as O(1) operation. There are different implementations of priority queues available in different languages - most typical one is using a heap (min or max). Here is a quite useful thread that talks about heaps and priority queue.

Back to our problem. Below are possible solutions in C#, Python and Java. I did not attempt JavaScript as it does not have a built in type of priority queue; you could implement it though (reference).

Python (heapq makes it easy)

def findKthLargest(self, nums: List[int], k: int) -> int:

        pq = []

        for i in range(len(nums)):

            heapq.heappush(pq, nums[i])

            if(len(pq) > k):

                heapq.heappop(pq)

        return pq[0]

C# (No in-built data type. Can use SortedList which is close to a minHeap but you need to manage duplicate elements on your own)

public int FindKthLargest(int[] nums, int k) {

        SortedList<int,int> sortedList =new SortedList<int,int>();

        int itemCount=0;

        foreach(int num in nums)

        {

            if(sortedList.ContainsKey(num))

                sortedList[num] += 1;

            else

                sortedList[num] = 1;

            itemCount++;

            if(itemCount > k)

            {

                if(sortedList[sortedList.Keys.First()]==1)

                    sortedList.Remove(sortedList.Keys.First());

                else

                    sortedList[sortedList.Keys.First()]--;

                itemCount--;

            }

        }

        return sortedList.Keys.First();

    }

Java (use in-built PriorityQueue type)

public int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for(int num: nums){

            heap.offer(num);

            if(heap.size() > k){

                heap.poll();

            }

        }

        return heap.peek();

    }

Observations

1. Since Java and Python have in-built support for priority queue, you can simply focus on logic. Since we are trying to utilize a makeshift type in C#, we have to deal with more than just logic to write the correct code.

2. Test results from leetcode submission. Java consumed highest amount of memory but took the least amount of time. Python produced a balanced result though.