algoadvance

Leetcode 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

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

Clarifying Questions:

  1. Can nums contain negative numbers?
    • Yes, nums can contain negative numbers.
  2. Can nums be empty?
    • No, according to the problem’s constraints, nums will have at least one element.
  3. What are the constraints on k?
    • k is always valid, which means 1 <= k <= nums.length.

Strategy:

  1. Sorting Approach:
    • Sort the array in descending order.
    • Pick the element at index k-1.
  2. Usage of a Min-Heap:
    • Use a Min-Heap (priority queue) to manage the size of the heap to k.
    • Iterate through each element in the array, maintaining a heap of size k.
    • The root of the heap will be the kth largest element.
  3. Quickselect Algorithm:
    • Use a selection algorithm to find the kth largest element without full sorting.
    • This is similar to the quicksort algorithm, but only works on one partition.

Code:

Let’s implement the Min-Heap approach, which provides a good balance between simplicity and efficiency.

import java.util.PriorityQueue;

public class KthLargestElementInArray {
    public int findKthLargest(int[] nums, int k) {
        // Create a Min-Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            minHeap.add(num);
            // If the heap size exceeds k, remove the smallest element
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        // The root of the heap is the k-th largest element
        return minHeap.peek();
    }

    public static void main(String[] args) {
        KthLargestElementInArray solution = new KthLargestElementInArray();
        int[] nums1 = {3,2,1,5,6,4};
        int[] nums2 = {3,2,3,1,2,4,5,5,6};
        
        System.out.println(solution.findKthLargest(nums1, 2)); // Output: 5
        System.out.println(solution.findKthLargest(nums2, 4)); // Output: 4
    }
}

Time Complexity:

This method is efficient and scales well for larger arrays compared to full sorting, which would take O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI