The problem
The list a holds journey times. Return the value that would be at index k (counting from 0) if the list were sorted. Do not change a. sorted(), .sort() and heapq are switched off.
kth_smallest([29, 10, 14, 37, 13, 5, 33, 18, 21], 4) # 18
kth_smallest([4, 9, 1, 7], 0) # 1
The tests include a list that is already sorted and a list where every value is the same.
Limits
- Up to 500,000 values.
kis at least 0 and less thanlen(a).
Builds on SORT-3 Quick sort and partitioning and SORT-8 Quickselect.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Middle | Not run | |
| 2 | Smallest and largest | Not run | |
| 3 | Repeats | Not run | |
| 4 | One value | Not run | |
| 5 | 300,000 values in order | Not run | |
| 6 | 300,000 equal values | Not run | |
| 7 | 500,000 mixed values | Not run | |
| 8 | Input not changed | Not run |