Forem

ashutosh049
ashutosh049

Posted on • Edited on

2 2

Kth Largest Element in an Array

You can refer to the Leetcode problem 215. Kth Largest Element in an Array


Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Enter fullscreen mode Exit fullscreen mode

Approach 1: Using Sorting

We can use sorting to first sort the nums array in natural order and then return kth element from end i.e n-k th element from start.

K index from end is equal to length-k index from start

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

TC: O(N log N), where N is the size of the input array
SC: O(1)


Approach 2: Using Heap

Actually there are multiple sub-approaches if we choose to use Heap.

Approach Number of elements number of poll
Min Heap of size N Min heap to store all N elements(at most N-K minimum elements at any given time) poll for N-K times to get kthlargest
Min Heap of size K Min heap to store at most K elements. Adding new elements after first K elements are added, we check if new element is greater than heap root(peek) and if so we delete it first and then add the new greater element, otherwise not poll for 1 time and return the polled element
Max Heap of size N Max heap to store all N elements(at most K maximum elements at any given time) poll for K times to get kthlargest
Min Heap of size N
class Solution {

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue();

        for(int num: nums){
            minHeap.offer(num);
        }

        int i = 0;
        int kThLargest = minHeap.poll();

        while (i++ < (n - k)) {
            kThLargest = minHeap.poll();
        }

        return kThLargest;
    }
}
Enter fullscreen mode Exit fullscreen mode
Min Heap of size K
import java.util.Arrays;
import java.util.Collections;

//Min Heap of size K
class Solution {

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue(k);

        for(int i=0; i<k; i++){
            minHeap.offer(nums[i]);
        }

        for(int i=k; i<n; i++){
            if(minHeap.peek() < nums[i]){
                minHeap.poll();
                minHeap.offer(nums[i]);    
            }
        }

        return minHeap.poll();
    }
}
Enter fullscreen mode Exit fullscreen mode
Max Heap of size N
class Solution {
    public int findKthLargest(int[] nums, int k) {

        int len = nums.length;

        if(len == 1){
            return nums[0];
        }

        // Since we are using Max-Heap, we need to sort accordingly
        Comparator<Integer> comp = (a,b) -> b.compareTo(a);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(comp);

        // Add all the elements
        for(int num: nums){
            maxHeap.offer(num);
        }

        // we need to poll for k-1 times and
        // return the next polled element
        int i = 1;

        while(i++ < k){
            maxHeap.poll();
        }

        return  maxHeap.poll();

    }
}
Enter fullscreen mode Exit fullscreen mode

Problem Credit : leetcode.com

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay