Skip to main content

15. Kth Largest Element in an Array

mediumAsked at LINE

Return the k-th largest element in an unsorted array — LINE uses this to see whether you reach for a min-heap of size k, the same shape as picking the top-k most-active chat rooms.

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

Problem

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 in sorted order, not the k-th distinct element.

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 and index

Sort the array descending and return arr[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 holding the k largest values seen. For each new value, push it and pop the smallest if the heap exceeds k. The root is the answer.

Time
O(n log k)
Space
O(k)
// Using a min-heap MinHeap class with peek/push/pop.
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Tradeoff:

LINE-specific tips

At LINE, frame the heap of size k as the structure you'd keep per region to track the top-k busiest chat rooms for fan-out throttling — chat fan-out framing wins.

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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →