Skip to main content

77. Kth Largest Element in an Array

mediumAsked at Datadog

Find the kth largest element in an unsorted array. Datadog asks this for the min-heap-of-size-k trick — same streaming aggregate they use to maintain top-K leaderboards over high-cardinality metric streams.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct top-K analog.
  • Blind (2025-11)— Recurring at Datadog.

Problem

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting?

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 pick

Sort descending; return nums[k-1].

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

Tradeoff: Simple but slow for large n. Datadog asks for sub-sort time.

2. Min-heap of size k (optimal for streaming)

Maintain a min-heap of size k. When new element > heap.peek, replace. Top of heap = kth largest.

Time
O(n log k)
Space
O(k)
// Use a min-heap implementation; for n in array, push if size < k, else if val > top, pop + push.
// Return heap.peek() at end. (Heap implementation omitted; assume MinHeap class.)

Tradeoff: O(n log k) — better than O(n log n) when k is small. Streaming-friendly: works on an unbounded stream.

Datadog-specific tips

Datadog grades on whether you reach for the min-heap (not max-heap). They'll follow up with: 'Now do this over a streaming source.' The min-heap-of-size-k IS the streaming algorithm — no modifications needed. Mention quickselect as the O(n) average-case alternative when the data is fully available.

Common mistakes

  • Using a max-heap of size n — works but O(n + k log n), worse for large n.
  • Forgetting that quickselect is O(n^2) worst case — need randomized pivot.
  • Confusing 'kth largest' (1-indexed from top) with 'kth distinct'.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Quickselect — O(n) average, O(n^2) worst.
  • Top K Frequent Elements (LC 347) — heap of (count, val).
  • Datadog-style: streaming top-K over high-cardinality metric IDs.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Min-heap or max-heap?

Min-heap of size k. We discard small values, keeping the top k. The min of the heap IS the kth largest.

Quickselect or heap?

Quickselect is O(n) average — beats heap when data fits in memory. Heap is required for streaming or when k << n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →