Asked at
Kth Largest Element
MediumVerifiedQuickselectHeapArray~20 min
Given an integer array nums and an integer k, return the kth largest value (1-indexed).
The kth largest sits at sorted index n - k. Quickselect finds it in average O(n) without a full sort.
The input arrives as a single object { nums, k }.
Examples
in{ nums: [3, 2, 1, 5, 6, 4], k: 2 }
out5
Sorted descending: 6, 5, 4, 3, 2, 1 — the 2nd largest is 5.
in{ nums: [3, 2, 3, 1, 2, 4, 5, 5, 6], k: 4 }
out4
The 4th largest value is 4.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.