Katkat
Back

Find kth largest element in array

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

A classic Meta software engineer onsite coding question: return the k-th largest element from an unsorted integer array, handling duplicates correctly. It tests order statistics and selection algorithms — sort, size-k min-heap (O(n log k)), and quickselect (O(n) average) — and the candidate's ability to beat a full sort.

Question

Given an unsorted array of integers nums and an integer k, return the k-th largest element in the array.

The 1st largest element is the maximum element, the 2nd largest is the second highest, and so on. Equivalently, the k-th largest element is the value that would appear at index k - 1 if the array were sorted in descending order.

Requirements:

  1. Handle duplicates correctly. Duplicates count as separate positions, e.g. nums = [5, 5, 4], k = 2 returns 5 (not 4).
  2. Describe your approach and analyze its time and space complexity. Try to design an algorithm that is more efficient than fully sorting the array. (You do not need to provide working code unless asked.)

Input:

  • nums: an array of integers
  • k: an integer where 1 <= k <= len(nums)

Output:

  • The k-th largest element (an integer).

Constraints (typical interview scale):

  • 1 <= n <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9

Example:

  • nums = [3, 2, 1, 5, 6, 4], k = 2 -> 5
  • nums = [5, 5, 4], k = 2 -> 5