DSA Factory
Free lessonsSorting · Stage 0 · Sort it first · Step 1

Position is rank

Sort with one line, then read the answer off an index. About 7 minutes.

Your language already sorts

Think of a teacher lining up a class by height. You don't need to write that routine yourself, because every language has a fast sort built in. It takes about n times log n steps, so even a million numbers sort in well under a second.

In Python it is a list method, in Java it is Arrays.sort, and in C++ it is sort. One line, and the list runs from smallest to largest.

Sorting is one line: in every language, so use it.
JavaScript: sorts as text unless you give it a compare function, so 10 would come before 9.
In code
nums = [7, 2, 9, 4, 1]
nums.sort()
# [1, 2, 4, 7, 9]
Sort [7, 2, 9, 4, 1], then find the 3rd smallest
7
0
2
1
9
2
4
3
1
4
i

Before sorting, the 3rd smallest could be anywhere.

Move 1 of 4

In a sorted list, position is rank

Once the class is lined up, the shortest child is first, the second shortest is next, and so on. The same is true of a sorted list: the smallest value sits at position 0, the 2nd smallest at position 1.

So the kth smallest sits at position k − 1. Repeats count once each time they appear: in 2, 2, 5 the 2nd smallest is 2.

After sorting: the kth smallest is just a lookup.
k counts from 1, but positions count from 0.
In code
nums.sort()
return nums[k - 1]
Quick check

nums has 10 values. After sorting, which index holds the 4th smallest?

  1. AIndex 3
  2. BIndex 4
  3. CIndex 6
Show the answer

Index 3. Index 0 holds the smallest, so the 4th smallest is at index 4 − 1 = 3.

Your problem

The kth smallest

Return the kth smallest value in nums. k = 1 means the smallest. A value that appears more than once counts once for each time it appears.

Example
nums = [7, 2, 9, 4, 1], k = 3 → 4

1 ≤ k ≤ n ≤ 500,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding