215. Kth Largest Element in an Array
mediumAsked at AtlassianKth Largest Element in an Array is an Atlassian heap-vs-quickselect classic. Given an integer array and an integer k, return the kth largest element. The grading is whether you can compare the heap, sort, and quickselect tradeoffs without hand-waving.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Atlassian loops.
- Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite Kth Largest as a recurring heap/quickselect problem, sometimes as the harder follow-up to Top K Frequent.
- Blind (2025-09)— Atlassian threads list it as 'the quickselect question if you can pull it off, otherwise the heap answer is accepted'.
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
nums = [3,2,1,5,6,4], k = 25Example 2
nums = [3,2,3,1,2,4,5,5,6], k = 44Approaches
1. Sort then index
Sort ascending; return nums[n - k].
- Time
- O(n log n)
- Space
- O(log n) for sort
function findKthLargestSort(nums, k) {
nums.sort((a, b) => a - b);
return nums[nums.length - k];
}Tradeoff: One line and clearly correct. The LeetCode prompt explicitly asks 'can you solve it without sorting?' so this is the warm-up; show the heap or quickselect for the real answer.
2. Min-heap of size k (O(n log k))
Maintain a min-heap of size k. For each num: push, then pop if size > k. Result is the heap's root.
- Time
- O(n log k)
- Space
- O(k)
class MinHeap {
constructor() { this.h = []; }
size() { return this.h.length; }
peek() { return this.h[0]; }
push(v) {
this.h.push(v);
let i = this.h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p] <= this.h[i]) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p;
}
}
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length) {
this.h[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1;
const r = 2 * i + 2;
let m = i;
if (l < this.h.length && this.h[l] < this.h[m]) m = l;
if (r < this.h.length && this.h[r] < this.h[m]) m = r;
if (m === i) break;
[this.h[i], this.h[m]] = [this.h[m], this.h[i]];
i = m;
}
}
return top;
}
}
function findKthLargestHeap(nums, k) {
const heap = new MinHeap();
for (const n of nums) {
heap.push(n);
if (heap.size() > k) heap.pop();
}
return heap.peek();
}Tradeoff: Atlassian-accepted at SWE-II. Beats sort for k << n. Hand-written heap (~20 lines) is the standard JS expectation.
3. Quickselect (O(n) average)
Randomized partition around a pivot; recurse only into the side containing the target index (n - k).
- Time
- O(n) average, O(n^2) worst case
- Space
- O(log n) recursion
function findKthLargest(nums, k) {
const target = nums.length - k;
const partition = (lo, hi) => {
const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
const pivot = nums[pivotIdx];
[nums[pivotIdx], nums[hi]] = [nums[hi], nums[pivotIdx]];
let store = lo;
for (let i = lo; i < hi; i++) {
if (nums[i] < pivot) {
[nums[store], nums[i]] = [nums[i], nums[store]];
store++;
}
}
[nums[store], nums[hi]] = [nums[hi], nums[store]];
return store;
};
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const p = partition(lo, hi);
if (p === target) return nums[p];
if (p < target) lo = p + 1;
else hi = p - 1;
}
return -1;
}Tradeoff: Best average performance — O(n). The catch is the O(n^2) worst case (all-equal input or adversarial pivot). Random pivot mitigates but doesn't eliminate; Atlassian Senior interviewers love the median-of-medians digression here.
Atlassian-specific tips
Atlassian explicitly grades the heap-vs-quickselect tradeoff. State both options aloud BEFORE coding: 'heap is O(n log k) and stable; quickselect is O(n) average but O(n^2) worst-case'. Then ask the interviewer which one they'd like to see. Many Atlassian Senior interviewers specifically grade 'asked the interviewer which tradeoff they care about' as a +1. SWE-II tends to accept either; lead with heap if unsure.
Common mistakes
- Confusing kth largest with kth smallest — target index = n - k, not k - 1.
- On quickselect, using a fixed pivot like nums[lo] — adversarial inputs (already-sorted) hit O(n^2) immediately. Use random.
- On heap, mistakenly using a max-heap of size n then popping k - 1 times — that's O(n + k log n) which loses to size-k min-heap when k is large.
Follow-up questions
An interviewer at Atlassian may pivot to one of these next:
- Kth Smallest Element in a Sorted Matrix (LeetCode 378) — heap on row pointers or binary search on value.
- Median of Two Sorted Arrays (LeetCode 4) — k = (n + m) / 2 case; specialized binary search.
- What if the array is streaming? Min-heap of size k still works; quickselect doesn't (needs the whole array).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Heap or quickselect at Atlassian?
Either. Heap is the safer choice — clear big-O, easy to bug-check, no pathological inputs. Quickselect is the showy choice if you can write it cleanly under pressure; if not, don't risk it. Ask the interviewer; the asking itself scores.
Why min-heap and not max-heap?
Because you want to keep the k LARGEST values. A min-heap of size k lets you compare each incoming value to the SMALLEST of your kept set; if the incoming is larger, evict the smallest. Max-heap forces you to keep all n in the heap.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Kth Largest Element in an Array and other Atlassian interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →