A monitoring service stores response times in times, and most of them repeat (many requests take exactly 20 ms). A percentile widget needs the k-th smallest value, counting repeats (k = 1 is the smallest).
Write kthSmallest(times, k) that returns that value without fully sorting the list. Plain quickselect slows down badly when values repeat a lot; split around the pivot into three groups (less than, equal to, greater than) so repeats are handled in one step. You may reorder times.
Input: times = [20,35,20,12,20,50,20], k = 4 Output: 20
Sorted, the times are 12, 20, 20, 20, 20, 35, 50; the 4th is 20.
Input: times = [7,3,9], k = 3 Output: 9
The 3rd smallest of three values is the largest.
1 <= k <= times.length <= 1000000 <= times[i] <= 10^4Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #123 Kth Smallest With Many Repeats. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.