algoadvance

LeetCode Problem 215: Kth Largest Element in an Array

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.

Clarifying Questions

  1. Q: Can the array contain negative numbers? A: Yes, the array can contain negative as well as positive integers.
  2. Q: Can k be larger than the length of the array? A: No, k will always be a valid integer such that 1 <= k <= len(nums).
  3. Q: Is modifying the input array allowed? A: Yes, modifying the input array is allowed.
  4. Q: What are the constraints on the size of the array? A: The array size can be large, so the algorithm should handle arrays efficiently even for large sizes.

Strategy

To find the kth largest element in an array, there are several possible approaches:

  1. Sorting: Sort the array and access the kth largest element directly.
  2. Heap: Use a min-heap of size k to keep track of the k largest elements encountered so far.
  3. Quickselect: Use a partition-based selection algorithm similar to quicksort’s partitioning.

Approach

Here, we’ll use the Heap approach for its balanced performance and ease of implementation:

  1. Min-Heap: We’ll maintain a min-heap of size k to keep track of the largest elements.
    • If the heap size is less than k, we simply add the current element.
    • If the heap size is k, we compare the current element with the smallest element in the heap (heap root). If the current element is larger, we replace the smallest element with the current element.
    • The root of the min-heap will eventually contain the kth largest element in the end.

Algorithm

  1. Initialize an empty min-heap.
  2. Iterate through every element in the array:
    • If the size of the heap is less than k, push the element onto the heap.
    • Else, if the current element is larger than the smallest element in the heap (heap root), pop the smallest element and push the current element.
  3. After processing all elements, the root of the heap will be the kth largest element.
  4. Return the root of the heap.

Code

import heapq

def findKthLargest(nums, k):
    min_heap = []
    
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        else:
            if num > min_heap[0]:
                heapq.heapreplace(min_heap, num)
    
    return min_heap[0]

# Example usage
nums = [3,2,1,5,6,4]
k = 2
print(findKthLargest(nums, k))  # Output: 5

Time Complexity

Overall time complexity: O(n log k). This is efficient for large arrays combined with reasonably-sized k.

Try our interview co-pilot at AlgoAdvance.com