DSA Tracker

Visualize

Kth Largest Element in an Array

Quickselect with Lomuto partition

time O(n) averagespace O(1)

Sorting costs O(n log n) just to learn one order statistic. Quickselect partitions around a pivot like quicksort — but then recurses into ONLY the side that contains the answer. The kth largest is simply the element that ends up at ascending index n−k once partitions place pivots on their true sorted positions.

Details

Animated on: Find the 3rd largest element of [7,2,9,4,5,1,8] without fully sorting it.

Problem:Kth Largest Element in an ArrayMedium

Pattern:Heap and Top K

Quickselect with Lomuto partition

step 1 / 15

7
[0]
2
[1]
9
[2]
4
[3]
5
[4]
1
[5]
8
[6]

k = 3 means the answer occupies ascending index n − k = 7 − 3 = 4. Goal: keep partitioning until some pivot lands EXACTLY on index 4.

  • lo=0· arr[0] = 7
  • hi=6· arr[6] = 8
Pseudocode
1FUNCTION quickselect(arr, lo, hi, k):
2  pivot = arr[hi]; set boundary i to lo - 1
3  FOR j from lo to hi-1:
4    IF arr[j] <= pivot:
5      move i one step right, then swap arr[i] with arr[j]
6  swap arr[i+1] with arr[hi]   (pivot to its final spot)
7  p = i + 1
8  IF p equals k: RETURN arr[p]
9  IF p < k: quickselect on the right side (p+1, hi, k)
10  ELSE: quickselect on the left side (lo, p-1, k)

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. k = 3 means the answer occupies ascending index n − k = 7 − 3 = 4. Goal: keep partitioning until some pivot lands EXACTLY on index 4.
  2. Partition pass 1: Lomuto picks the last cell as pivot — 8 — and sweeps j left to right growing a '≤ 8' prefix; i marks the prefix's right edge (starts before the array).
  3. j=0: 7 ≤ 8 → advance i to 0 and swap(0,0) — a free self-swap since 7 already sits in the ≤8 zone.
  4. j=1: 2 ≤ 8 → i climbs to 1, another trivial self-swap. The green prefix now holds {7, 2}.
  5. j=2: 9 > 8 → skip. Boundary i freezes at 1, so 9 waits on the big side — the NEXT small value will swap it rightward.
  6. j=3: 4 ≤ 8 → swap(i+1=2, j=3): 4 trades places with 9, exiling 9 rightward. Green prefix grows to {7, 2, 4}.
  7. j=4: 5 ≤ 8 → swap(3, 4) pushes the wandering 9 one slot further right. Prefix = {7, 2, 4, 5}.
  8. j=5: 1 ≤ 8 → swap(4, 5); the 9 lands at index 5, directly beside its pivot. Sweep done — everything left of index 5 is ≤ 8.
  9. Final move: swap(i+1=5, hi=6) drops the pivot 8 between its two camps — five values ≤ 8 on the left, only 9 on the right. Index 5 is now 8's FINAL sorted position.
  10. But we want index 4, and the pivot landed at p = 5 > 4 → recurse LEFT into indices 0..4. Bonus knowledge for free: index 5 holding 8 proves 8 IS the 2nd largest.
  11. Partition pass 2 over [7,2,4,5,1]: new pivot is the window's last cell, value 1 — the smallest here, so expect it to land at the window's far LEFT.
  12. All four comparisons fail (7, 2, 4, 5 all exceed 1), so i never advances past -1. Final swap(0, 4) trades 1 with 7 → pivot 1 lands at p = 0. Since 0 < 4, recurse RIGHT into indices 1..4.
  13. Partition pass 3 over window [2,4,5,7]: pivot = arr[4] = 7 — the largest of this slice, so it should land at the window's RIGHT end… which happens to be exactly our target index 4.
  14. Every element (2, 4, 5) is ≤ 7, so the sweep just walks through and the closing swap seats 7 at p = 4. p == k == 4 → return arr[4] = 7. Jackpot on the first try of this window.
  15. Answer: the 3rd largest is 7. Three pivots (8, 1, 7) each locked onto their true sorted position while whole regions were discarded untouched — average O(n) work total.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Kth Largest Element in an Array in the editorAll Arrays problemsBack to roadmap