Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Kth Largest Element in an Array
Bookmark
Input
Example 1
Example 2
Example 3
Custom
nums
=
[3, 2, 1, 5, 6, 4]
,
k
=
2
INPUT ARRAY
3
2
1
5
6
4
MIN-HEAP (the k largest so far)
size
0
/ 2
heap empty
keep the 2 largest in a min-heap — its root is the 2nd largest
INPUT ARRAY
3
2
1
5
6
4
MIN-HEAP (the k largest so far)
size
0
/ 2
heap empty
keep the 2 largest in a min-heap — its root is the 2nd largest
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
1
/ 2
3
root = min
push
3
onto the min-heap (size 1)
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
2
/ 2
3
2
root = min
push
2
onto the min-heap (size 2)
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
3
/ 2
3
2
1
root = min
push
1
onto the min-heap (size 3)
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
2
/ 2
3
2
root = min
EVICTED (too small for the top k)
1
look at nums[3] =
5
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
3
/ 2
3
2
root = min
5
EVICTED (too small for the top k)
1
push
5
onto the min-heap (size 3)
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
2
/ 2
3
root = min
5
EVICTED (too small for the top k)
1
2
look at nums[4] =
6
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
2
/ 2
5
root = min
6
EVICTED (too small for the top k)
1
2
3
size > 2 → evict min =
3
(too small for the top 2)
INPUT ARRAY
3
2
1
5
6
4
curr
MIN-HEAP (the k largest so far)
size
3
/ 2
5
6
4
root = min
EVICTED (too small for the top k)
1
2
3
push
4
onto the min-heap (size 3)
INPUT ARRAY
3
2
1
5
6
4
MIN-HEAP (the k largest so far)
size
2
/ 2
5
root = min
6
EVICTED (too small for the top k)
1
2
3
4
2nd largest = 5
algo
master
.
io
Step:
Find the 2nd largest element with a size-2 min-heap
0 / 17
Input
Example 1
Example 2
Example 3
Custom
nums
=
[3, 2, 1, 5, 6, 4]
,
k
=
2
0 / 17
algo
master
.
io
Step:
Find the 2nd largest element with a size-2 min-heap
