Kth Largest Element in an Array (Quickselect/Heap)

To solve finding the k-th largest element efficiently, I would first clarify that we need the element at the specific rank if the array were sorted in descending order. For an unsorted array, a naive sort takes O(n log n), but Google often looks for more optimized solutions. I propose using the Quickselect algorithm, which is analogous to Quicksort's partitioning. We pick a pivot, rearrange the array so elements larger than the pivot are on the left, and smaller ones on the right. If the pivot lands exactly at index k-1, we found our answer. Otherwise, we recursively search only the relevant half. This gives us an average time complexity of O(n) with O(1) space. Alternatively, if k is significantly smaller than n, a Min-Heap of size k is viable. We iterate through the array, pushing elements onto the heap and popping the smallest whenever the size exceeds k. The root will be the k-th largest after processing all elements. This runs in O(n log k). While slightly slower for large k, it handles streaming data better. Let's assume standard inputs. Using Quickselect, if the array is [3, 2, 1, 5, 6, 4] and k=2, we partition until the second largest element, 5, settles in the correct position. I would also add checks for k being greater than the array length to ensure robustness, as Google values production-ready code quality.