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:

Constraints:

Clarifying Questions

  1. Q: Can the input array contain duplicate elements? A: Yes, the input array can contain duplicate elements.

  2. Q: Are the elements in the array always integers? A: Yes, all elements in the array are integers.

  3. Q: Is k always a valid index within the range of the array? A: Yes, k is always within the valid range as per the constraints given.

Strategy

To solve the problem of finding the kth largest element, we can use one of the following approaches:

  1. Sorting:
    • Sort the array in descending order and then return the element at the (k-1)-th index. This is straightforward but might not be the most efficient way.
  2. Min-Heap:
    • Use a Min-Heap of size k to keep track of the k largest elements.
    • Iterate through the array, and for each element, maintain the heap of size k. At the end, the root of the heap will be the kth largest element.
  3. Quickselect Algorithm:
    • This is a selection algorithm that works similar to QuickSort. It is more efficient on average for this type of problem. We can utilize a partitioning method to find the k-th largest element.

Given the constraints, using a Min-Heap seems to be a balanced approach in terms of implementation complexity and efficiency.

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // Min-heap to store the k largest elements
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        for (int num : nums) {
            minHeap.push(num);
            
            // Keep the heap size to k
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        
        // The root of the heap is the k-th largest element
        return minHeap.top();
    }
};

// Driver code for testing
int main() {
    Solution solution;
    vector<int> nums1 = {3,2,1,5,6,4};
    int k1 = 2;
    cout << "The " << k1 << "-th largest element in the first array is: " << solution.findKthLargest(nums1, k1) << endl;

    vector<int> nums2 = {3,2,3,1,2,4,5,5,6};
    int k2 = 4;
    cout << "The " << k2 << "-th largest element in the second array is: " << solution.findKthLargest(nums2, k2) << endl;

    return 0;
}

Time Complexity

This method efficiently finds the kth largest element while managing the input constraints effectively.

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