Kth Largest Element in an Array

Kth Largest Element in an Array

1. What is this problem about?

The Kth Largest Element in an Array interview question is one of the most popular algorithmic challenges. You are given an unsorted array and need to find the $k^{th}$ largest element. Note that it is the $k^{th}$ largest in sorted order, not the $k^{th}$ distinct element.

2. Why is this asked in interviews?

This question is a favorite at Google, Amazon, and Uber because it allows for multiple solutions with different trade-offs. It evaluations your knowledge of Sorting, Heaps, and most importantly, the Quickselect algorithm. it tests if you can optimize from $O(N \log N)$ to $O(N)$ average time.

3. Algorithmic pattern used

There are three main patterns:

1. Sorting ($O(N \log N)$): Sort the array and return arr[n - k].
2. Min-Heap ($O(N \log K)$): Keep a heap of the $k$ largest elements. The top is the answer.
3. Quickselect ($O(N)$ average): Based on Quicksort partitioning. Pick a pivot, partition the array, and only recurse into the side that contains the $k^{th}$ index.

4. Example explanation

[3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4

• Sorted: [1, 2, 2, 3, 3, 4, 5, 5, 6]
• The $4^{th}$ largest from the end is 4. Quickselect logic:
• Partition around pivot 4. Numbers $> 4$ are {5, 5, 6} (3 elements).
• Since we need the $4^{th}$ largest, and there are only 3 larger than 4, the $4^{th}$ largest is the pivot 4 itself.

5. Common mistakes candidates make

• Worst case Quickselect: Forgetting that Quickselect can be $O(N^2)$ if the pivot selection is poor (e.g., always picking the first element of a sorted array). Recommend using a random pivot.
• Heap size: Using a Max-Heap of size $N$ instead of a Min-Heap of size $k$.
• Duplicates: Not handling duplicate elements correctly in the partitioning logic.

6. Interview preparation tip

Master Quickselect. It is the most "senior" answer to this problem. Be prepared to explain why it is $O(N)$ on average (using the Master Theorem or a geometric series argument). This is a core Quickselect interview pattern.