Skip to content

Volume ITechnology

4.17.4 — Kth Largest Element in an Array ​

LeetCode 215 · Medium

The problem ​

Return the k-th largest element. This is the k-th largest in sorted order, not the k-th distinct value.

[3,2,1,5,6,4], k = 2        →  5
[3,2,3,1,2,4,5,5,6], k = 4  →  4

Up to 100,000 elements. The follow-up asks you to do it without sorting.

The pattern ​

This is the pure selection problem: find the element that would sit at a given position if the array were sorted, without sorting it.

Three answers, and knowing all three plus the condition that picks each is the point of this problem.

Solution 1 — sort ​

python
return sorted(nums)[-k]

O(n \log n). Correct, one line, and the right thing to say first.

The waste: sorting establishes the position of every element, and you asked about one.

Solution 2 — a size-k min-heap ​

Keep the k largest seen so far; the root is the k-th largest.

python
import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []  # (1)
        for n in nums:  # (2)
            heapq.heappush(heap, n)  # (3)
            if len(heap) > k:  # (4)
                heapq.heappop(heap)
        return heap[0]  # (5)

O(n \log k) time, O(k) space. The only version that works on a stream.

Python has this in one line — heapq.nlargest(k, nums)[-1] — which uses a size-k heap internally. Know both.

Line by line. (1) An empty heap, which keeps its smallest item at the front. (2) Visit every number once. (3) Push it. (4) If the heap holds more than k numbers, remove the smallest, because it cannot be among the k largest. (5) The heap now holds exactly the k largest numbers, and the smallest of them, at the front, is the k-th largest. This is the same idea as 4.17.1, run over a fixed list. It costs O(n \log k) time and O(k) memory.

Solution 3 — quickselect, O(n) average ​

Partition the array around a pivot, exactly as quicksort does: everything smaller goes left, everything larger goes right, and the pivot lands in its final sorted position.

Then — and this is the whole idea — look at where the pivot landed. If that is the position you wanted, you are done. If not, the answer is on one side only, so recurse into that side and ignore the other completely.

Quicksort recurses into both halves. Quickselect recurses into one. That difference is what turns O(n \log n) into O(n).

Think of Quickselect like looking for a name in a phone book. If you open it to the middle and realize the name you want is alphabetically earlier, you completely tear off the second half of the book and throw it away. You don't bother sorting or organizing the thrown-away half because you know your target isn't there.

python
import random

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k                # (6) k-th largest = this index when sorted

        def partition(lo: int, hi: int) -> int:  # (7)
            p = random.randint(lo, hi)                     # (8) random pivot
            nums[p], nums[hi] = nums[hi], nums[p]
            pivot = nums[hi]  # (9)

            store = lo  # (10)
            for i in range(lo, hi):
                if nums[i] < pivot:  # (11)
                    nums[store], nums[i] = nums[i], nums[store]
                    store += 1
            nums[store], nums[hi] = nums[hi], nums[store]  # (12)
            return store                                   # final home of the pivot

        lo, hi = 0, len(nums) - 1  # (13)
        while True:
            p = partition(lo, hi)  # (14)
            if p == target:  # (15)
                return nums[p]
            if p < target:  # (16)
                lo = p + 1
            else:
                hi = p - 1  # (17)
ts
function findKthLargest(nums: number[], k: number): number {
  const target = nums.length - k;  // (6)

  function partition(lo: number, hi: number): number {  // (7)
    const p = lo + Math.floor(Math.random() * (hi - lo + 1));  // (8)
    [nums[p], nums[hi]] = [nums[hi], nums[p]];
    const pivot = nums[hi];  // (9)

    let store = lo;  // (10)
    for (let i = lo; i < hi; i++) {
      if (nums[i] < pivot) {  // (11)
        [nums[store], nums[i]] = [nums[i], nums[store]];
        store++;
      }
    }
    [nums[store], nums[hi]] = [nums[hi], nums[store]];  // (12)
    return store;
  }

  let lo = 0, hi = nums.length - 1;  // (13)
  while (true) {
    const p = partition(lo, hi);  // (14)
    if (p === target) return nums[p];  // (15)
    if (p < target) lo = p + 1;  // (16)
    else hi = p - 1;  // (17)
  }
}

Line by line (quickselect) ​

(6) The position the answer would have in sorted order. In a list sorted from small to large, the largest number sits at position n - 1, the second largest at n - 2, and so the k-th largest at n - k.

(7) partition arranges the stretch from lo to hi around one chosen number, the pivot. Afterwards, everything smaller than the pivot is to its left, everything else is to its right, and the pivot itself sits exactly where it would be in a fully sorted list. The function returns that position.

(8) Choose the pivot at random, and swap it to the end of the stretch so it is out of the way. A random choice is what keeps quickselect fast on average. See the note after this list.

(9) Remember the pivot's value.

(10) store marks where the next small number should go. Everything before store is known to be smaller than the pivot.

(11) Walk the stretch. Each number smaller than the pivot is swapped into position store, and store moves one step right.

(12) Put the pivot right after all the smaller numbers. That is its final sorted position, and we return it.

(13) Start with the whole list.

(14) Partition the current stretch. The pivot lands at position p.

(15) If the pivot landed exactly at target, it is the answer. Every number to its left is smaller and every number to its right is not, so it is exactly the k-th largest.

(16) If the pivot landed left of target, the answer is to its right. Continue with only the right part.

(17) Otherwise the answer is to its left. Continue with only the left part. The other part is never touched again. That is the difference from quicksort, which sorts both parts.

target = len(nums) - k. The largest element sits at index n−1 when sorted, the second largest at n−2, so the k-th largest is at n−k. Work this out on paper once rather than guessing.

The random pivot is not decoration. With a fixed pivot such as the last element, a sorted input produces partitions of size n−1 every time, giving O(n^2). Randomising makes that case vanishingly unlikely. Say this out loud — it is the difference between knowing the algorithm and knowing why it works in practice.

Iterative rather than recursive, because there is only ever one side to continue with, so no call stack is needed. O(1) space.

Trace ​

Let's trace Quickselect for nums = [3,2,1,5,6,4] and k = 2. The sorted index target = 6 - 2 = 4.

  1. lo = 0, hi = 5: Pick a pivot, say nums[hi] = 4. Partitioning moves <4 to the left. [3,2,1] are smaller, [5,6] are larger. After swapping, nums becomes [3,2,1,4,6,5]. The pivot 4 lands at index 3 (p = 3).
  2. p (3) < target (4), so our target is to the right. We update lo = 4, hi = 5.
  3. lo = 4, hi = 5: nums[4:6] is [6,5]. Pick pivot 5. Partitioning puts 5 at index 4. nums becomes [3,2,1,4,5,6]. p = 4.
  4. p (4) == target (4). We return nums[4], which is 5. Correct!

Why the average is O(n) ​

A good pivot splits the array roughly in half. So the work is:

n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \cdots < 2n

Each level only processes one side, and the sizes halve. The whole sum is bounded by 2n, which is O(n).

Quicksort processes both sides at each level, so each level costs O(n) in total across \log n levels, giving O(n \log n).

The worst case is O(n^2), when every pivot is the smallest or largest remaining element. Randomisation makes it improbable. There is an algorithm called median of medians that guarantees O(n) worst case, but its constant factor is bad enough that nobody uses it in practice. Naming it is enough.

Edge cases ​

  • k = 1. The answer is the largest number. target is the last position.
  • k equals the length. The answer is the smallest number. target is 0.
  • Repeated numbers, like [3, 3, 3]. Numbers equal to the pivot go to its right, and the loop still ends, because the pivot's own position is settled every round.
  • Quickselect changes the order of nums. If the caller needs their list unchanged, work on a copy.

Choosing between them ​

timespacemutates inputworks on a stream
sortO(n \log n)O(n)maybeno
size-k heapO(n \log k)O(k)noyes
quickselectO(n) averageO(1)yesno

Sort if it is fast enough. Heap if the data streams or memory is tight. Quickselect if you need the best time and may reorder the input.

Where this goes next ​

  • K Closest Points to Origin — the same three solutions on distances. 4.17.3.
  • Median of a large array — quickselect with k = n/2.
  • Wiggle Sort II — quickselect to find the median, then place elements around it.
  • std::nth_element in C++ is quickselect. numpy.partition in Python is too. Knowing that the standard library exposes this operation is worth a sentence.

What the interviewer will push on ​

"Can you avoid sorting?" Heap for O(n \log k), quickselect for O(n) average.

"Why is quickselect O(n) when quicksort is O(n \log n)?" One side instead of two; the sizes halve and sum to 2n.

"What is quickselect's worst case, and what do you do about it?" O(n^2), fixed in practice by a random pivot. Median of medians guarantees linear but is slow in practice.

"Which index is the k-th largest?" n − k. Derive it rather than guessing.

"What if the data does not fit in memory?" The size-k heap, since it holds only k items at a time.

One thing to volunteer: give all three solutions with their trade-offs in about twenty seconds before writing anything. That comparison is the answer to this problem; the code for any single one of them is routine.

Next: 4.17.5 Task Scheduler — a heap simulation with a cooldown, and a formula that removes the heap entirely.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet