šŸ”— LeetCode

Kth Largest Element in an Array

MediumheapAmazonMetaGoogleAppleMicrosoft

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.

Examples

Input:nums = [3,2,1,5,6,4], k = 2
Output:5
Explanation:The 2nd largest element in sorted order [1,2,3,4,5,6] is 5.
Input:nums = [3,2,3,1,2,4,5,5,6], k = 4
Output:4

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

šŸ’” Hints

Hint 1

Maintain a min-heap of size k as you iterate through the array.

Hint 2

If the heap size exceeds k, pop the minimum element.

Hint 3

After iterating through all elements, the top of the min-heap is the kth largest element.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linearithmic
Algorithmic Approach

Use a Min-Heap of capacity k. Insert each element into the heap. When the heap size exceeds k, remove the smallest element. The remaining top element is the kth largest.

Time ComplexityO(N log K)
Why:

Maintaining a min-heap of size K requires O(log K) insertion/extraction for each of the N elements.

Space ComplexityO(K)
Why:

The min-heap stores at most K elements at any point.

Big-O Growth CurveLinearithmic (O(N log N))
Scales efficiently for sorting and divide-and-conquer algorithms.

šŸŒ Real-World Use Cases

TwitterTrending Topics Leaderboard

Streaming billions of tweets and maintaining top K hashtags using a bounded min-heap.

šŸ” Dry Run

Solutionā± O(N log K) | šŸ’¾ O(K)
Heap / Priority Queue
ā–¼ Min-Heap
1D Array Representation
[0]
2
[1]
3
Binary Tree Hierarchy (Parent i ā†’ Children 2i+1, 2i+2)
2
[0]
3
[1]
Line36
num=2number
heap=[2, 3]Array
k=2number

Iterate num = 3 and num = 2. Push into min-heap. Size = 2 (matches k = 2).