We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Largest Element in an Array

Difficulty: Medium

Problem Description

Given an integer array nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in the sorted order, not the k-th distinct element. Can you solve it without sorting?

Key Insights

  • The k-th largest element can be found without fully sorting the array.
  • A max-heap or a min-heap can be used to efficiently track the largest elements.
  • The Quickselect algorithm can be employed for an average-case O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n) on average with Quickselect, O(n log k) with a min-heap, O(n log n) for sorting. Space Complexity: O(1) for Quickselect, O(k) for a min-heap.

Solution

To find the k-th largest element, we have several approaches. The Quickselect algorithm is a popular choice as it allows us to find the k-th largest element in linear time on average. It works by selecting a pivot and partitioning the array into elements greater than and less than the pivot. The process is recursively applied to find the k-th largest element. Alternatively, a min-heap can be maintained to keep track of the largest k elements, allowing us to retrieve the k-th largest element directly.

Code Solutions

import heapq

def findKthLargest(nums, k):
    # Using a min-heap to store the largest k elements
    min_heap = []
    
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    # The root of the min-heap is the k-th largest element
    return min_heap[0]
← Back to All Questions