Kth Largest Element in an Array

​Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Approach 1: TreeMap

We can use a TreeMap sorted in the descending order of keys to solving the problem. TreeMap class extends AbstractMap and implements the NavigableMap interface.  It creates a map stored in a tree structure.  TreeMap is sorted according to the natural ordering of keys or by using an implementation of the Comparator interface. Read the following articles to learn more about TreeMap. The TreeMap will store the array elements in key position sorted in descending order and the value will indicate the number of occurrences of each digit in the array. So we can compare the occurrence count k to find the kth largest element.

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;


class TreeMapComparator implements Comparator < Integer > {
  // Comparator to sort keys in Descending Order
  public int compare(Integer a, Integer b) {
    return (b - a);
  }
}

class KthLargestSolution {

  public int findKthLargest(int[] nums, int k) {
    TreeMapComparator tc = new TreeMapComparator();
    Map<Integer, Integer> map = new TreeMap<>(tc);
    for (int cur: nums) {
      int count = map.getOrDefault(cur, 0);
      map.put(cur, (count + 1));
    }
    int i = 0;
    int kthLargest = 0;
    Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
    for (Map.Entry<Integer,Integer> entry: entrySet) {
      i = i + entry.getValue();
      if (i == k) {
        kthLargest = entry.getKey();
        break;
      } else if (k < i) {
        kthLargest = entry.getKey();
        break;
      }
    }
    return kthLargest;
  }
}


public class KthLargestElement {

  public static void main(String[] args) {
    int[] arr = {3,2,3,1,2,4,5,5,6};
    KthLargestSolution kthLargestSolution = new KthLargestSolution();
    int k = 4;
    int kthLargest = kthLargestSolution.findKthLargest(arr, k);
    System.out.println("When k = " + k + " || The largest element is :" + kthLargest);
  }
}

The output of the program is:

When k = 4 || The largest element is :4

Approach 2: Heap

The idea is to init a heap “the smallest element first”, and add all elements from the array into this heap one by one keeping the size of the heap always less or equal to k. That would results in a heap containing k largest elements of the array. The head of this heap is the answer, i.e. the kth largest element of the array.

The time complexity of adding an element in a heap of size k is O(logk), and we do it N times that means O(Nlogk) time complexity for the algorithm.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        Queue<Integer> minHeap = new PriorityQueue<Integer>
            (new Comparator<Integer>(){
            public int compare(Integer i1, Integer i2){
                return Integer.compare(i1, i2);
            }    
        });
        
        for(int num : nums){
            minHeap.offer(num);
            if(minHeap.size() > k){
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

Complexity Analysis

  • Time Complexity : O(Nlogk).
  • Space Complexity : O(k) to store the heap elements.

Categories: Heap

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s