Kth Largest Element in an Array

Frequently Asked at Salesforce OA — Reported repeatedly in Salesforce HackerRank OAs (2024-2026).

Problem Statement

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.

Example 1:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: Sorted descending: [6, 5, 4, 3, 2, 1]. 2nd largest is 5.

Example 2:

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Sorted descending: [6, 5, 5, 4, 3, 3, 2, 2, 1]. 4th largest is 4.

Constraints:

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

Difficulty: Medium LC: 215 Round: OA / Technical R1

---

Pattern Recognition

• What is the input structure? An unsorted integer array.
• What are we optimizing? Find the k-th largest in minimum time, ideally better than O(n log n) full sort.
• What pattern does this fit? Min-heap of size k, or Quickselect (partition-based selection).
• Why does this pattern fit? A min-heap of size k keeps the top-k elements in it at all times; the root is the smallest of the top-k, which is the k-th largest. Quickselect uses the partition step of quicksort to land a pivot at index n - k.

Sorting works (O(n log n)) but is suboptimal. For large n and small k, the min-heap is O(n log k). For arbitrary k, Quickselect gives O(n) average.

---

Approach

Brute Force — Sort and Index

Sort the array and return nums[n - k].

Time: O(n log n). Space: O(1) if sorting in place. Why insufficient: Correct, but wastes work sorting the bottom n - k elements.

Optimal 1 — Min-Heap of Size k

Key Insight: Keep only the k largest elements seen so far. Use a min-heap: push each element, and if the heap exceeds size k, pop the smallest. The root at the end is the k-th largest overall.

Step-by-step:

1. Create an empty min-heap.
2. For each v in nums:
   • Push v.
   • If heap.size() > k, pop the root.
3. Return the root.

Time: O(n log k). Space: O(k).

Optimal 2 — Quickselect (Average O(n))

Key Insight: After the partition step of quicksort, the pivot lands at its final sorted position. If that position is n - k, you are done; otherwise recurse into the side that contains position n - k.

Time: O(n) average, O(n^2) worst (mitigated by random pivots). Space: O(1) (iterative) or O(log n) (recursive).

For interview purposes, the heap solution is usually preferred because its complexity is deterministic and implementation is straightforward.

---

Walkthrough (Min-Heap)

Trace on nums = [3, 2, 1, 5, 6, 4], k = 2:

step	element	heap before	action	heap after
1	3	[]	push	[3]
2	2	[3]	push	[2, 3]
3	1	[2, 3]	push, pop smallest (1)	[2, 3]
4	5	[2, 3]	push, pop smallest (2)	[3, 5]
5	6	[3, 5]	push, pop smallest (3)	[5, 6]
6	4	[5, 6]	push, pop smallest (4)	[5, 6]

Root of final heap is 5. Answer: 5.

---

Implementation

TypeScript

// Min-heap of size k using a simple array-backed heap.
class MinHeap {
    data: number[] = [];
    size(): number { return this.data.length; }
    peek(): number { return this.data[0]; }

    push(v: number) {
        this.data.push(v);
        let i = this.data.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p] <= this.data[i]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
            i = p;
        }
    }

    pop(): number {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            const n = this.data.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let smallest = i;
                if (l < n && this.data[l] < this.data[smallest]) smallest = l;
                if (r < n && this.data[r] < this.data[smallest]) smallest = r;
                if (smallest === i) break;
                [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
                i = smallest;
            }
        }
        return top;
    }
}

function findKthLargest(nums: number[], k: number): number {
    const heap = new MinHeap();
    for (const v of nums) {
        heap.push(v);
        // Keep heap size bounded to k.
        if (heap.size() > k) heap.pop();
    }
    return heap.peek();
}

C++

#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& nums, int k) {
    // Min-heap: top is smallest of the top-k seen so far.
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int v : nums) {
        pq.push(v);
        if ((int)pq.size() > k) pq.pop();
    }
    return pq.top();
}

Watch out:

1. Using a max-heap of size n and popping k times. Correct but O(n + k log n) and wastes memory. Min-heap of size k is strictly better.
2. Off-by-one on k. k is 1-indexed. For the 1st largest, k = 1, not 0.
3. Quickselect worst case. Without random pivot selection, adversarial inputs can degrade to O(n^2). Randomize.

---

Complexity Analysis

	Time	Space
Sort	O(n log n)	O(1)
Min-Heap of Size k	O(n log k)	O(k)
Quickselect	O(n) avg, O(n^2) worst	O(1)

Bottleneck: For heap: each push/pop is O(log k), done n times. For Quickselect: the expected number of partitions halves the active range each time, giving linear total work.

---

Edge Cases

1. k == 1 — return the maximum. Heap of size 1 contains only the largest.
2. k == n — return the minimum. Heap of size n contains everything; root is the smallest.
3. All identical values — return that value.
4. Duplicate values — k-th largest counts duplicates; no distinctness filter.
5. Empty array — undefined by problem constraints, but handle gracefully if asked.

---

Related Problems

• LC 703 — Kth Largest Element in a Stream — Online version; min-heap of size k is the textbook solution.
• LC 347 — Top K Frequent Elements — Same heap pattern on (frequency, value) pairs.
• LC 973 — K Closest Points to Origin — Same heap pattern on (distance, point).
• LC 378 — Kth Smallest Element in a Sorted Matrix — Heap traversal of a 2D sorted grid.

---

OA Strategy Notes

Common, expected-pattern problem. If Salesforce asks this, aim for 10-15 minutes. In OA, use the language's built-in heap/priority queue if available (Python's heapq, C++'s priority_queue). TypeScript has no built-in, so writing a small min-heap class adds a few minutes — practice this ahead of time.

---

What is Expected at Each Level

Junior: Sorts and indexes. Given a nudge, arrives at the heap solution.

Mid-level: Goes to min-heap of size k directly. Explains why O(n log k) beats sort for large n, small k.

Senior: Implements Quickselect, discusses the O(n) average vs O(n^2) worst tradeoff, mentions randomized pivot selection, and notes the Introselect hybrid used in production (std::nth_element).