Skip to main content

73. Kth Largest Element in an Array

mediumAsked at Salesforce

Find the kth largest element in an unsorted array. Salesforce uses this as the canonical heap/quickselect problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses min-heap of size k in their top-k leaderboards.
  • Blind (2025-11)— Recurring on Salesforce backend onsites.

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: Overkill — sorts O(n) elements when we only need 1.

2. Min-heap of size k

Maintain a min-heap of the k largest. For each element, push; pop if size > k. Top of heap is kth largest.

Time
O(n log k)
Space
O(k)
// Pseudocode (Node has no built-in PriorityQueue):
// Use a heap class or:
function findKthLargest(nums, k) {
  // Using sort as proxy for heap — in real interviews, implement or use a library.
  const heap = [];
  for (const n of nums) {
    heap.push(n);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap[0];
}

Tradeoff: O(n log k) when using a real min-heap. The version above uses sort as a proxy; in production use a heap class.

Salesforce-specific tips

Salesforce uses min-heap-of-size-k for top-k leaderboards (top deals, top reps). They grade on whether you reach for the heap pattern. Bonus signal: discuss Quickselect (O(n) average) as an alternative — Salesforce engineers prefer it when k is unknown.

Common mistakes

  • Using sort instead of heap — works but wastes time on full ordering.
  • Using a MAX heap of all elements — O(n + k log n) but the size-k MIN heap is O(n log k) which is better for small k.
  • Off-by-one on the heap size check (should be size > k, not >= k).

Follow-up questions

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

  • Top K Frequent Elements (LC 347).
  • Kth Smallest Element in a Sorted Matrix (LC 378).
  • Median from Data Stream (LC 295).

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. The kth largest is the smallest of the top k, which is the heap's root.

When is quickselect better?

When k is unknown or close to n/2. Quickselect is O(n) average, but worst-case O(n^2) without randomization. The heap is O(n log k) guaranteed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →