Skip to main content

11. Kth Largest Element in an Array

mediumAsked at Rappi

Find the kth-largest element of an unsorted array — Rappi frames this as picking the kth-fastest courier from a city-wide ETA leaderboard for batched dispatch.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and an integer k, return the kth largest element in the array. Do not sort the entire array if you can avoid it.

Constraints

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

Examples

Example 1

Input
nums = [3,2,1,5,6,4], k = 2
Output
5

Example 2

Input
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output
4

Approaches

1. Sort descending

Sort the whole array and index into position k-1.

Time
O(n log n)
Space
O(1)
return nums.sort((a,b)=>b-a)[k-1];

Tradeoff:

2. Min-heap of size k

Maintain a min-heap of the top-k seen so far; root after one pass is the kth largest.

Time
O(n log k)
Space
O(k)
function findKthLargest(nums, k) {
  const heap = []; // min-heap, see standard PQ impl
  for (const n of nums) {
    heap.push(n); heap.sort((a,b)=>a-b);
    if (heap.length > k) heap.shift();
  }
  return heap[0];
}

Tradeoff:

Rappi-specific tips

Rappi expects you to call out the O(n log k) heap explicitly — their leaderboard is sharded by city and rebuilding a full sort per dispatch tick is unacceptable.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Kth Largest Element in an Array and other Rappi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →