easy

Kth Smallest Element (Partial Selection Sort)

Find the kth smallest value by running selection sort for only k passes.

1. Define the problem

Kth Smallest Element (Partial Selection Sort)

Given an integer array nums and an integer k, return the kth smallest value in the array (1-indexed, so k = 1 returns the smallest value). You don't need to sort the whole array — only run selection sort for the first k passes , each one finding the next-smallest remaining value. Stop as soon as the front k slots are correct.

Constraints

  • 1 ≤ k ≤ nums.length ≤ 1000
  • -104 ≤ numsi ≤ 104

Example

Inputnums = [7, 2, 9, 4, 1], k = 3
Output4

Explanation Sorted ascending the array is [1, 2, 4, 7, 9] — the 3rd smallest value is 4.

2. Know the words first

In plain terms

kth smallest
The value that would land at index k - 1 if the array were fully sorted in ascending order.
Partial sort
Only sorting as much of the array as you actually need, instead of sorting everything.
3. Visualize the solution

Run selection sort for only the first k passes

Run selection sort for only the first k passes
Statuspass 1

sortedEnd=0. Scanning all 5 values, the minimum is 1 at index 4.

What happens in this step

arr = [7, 2, 9, 4, 1], sortedEnd = 0, min so far = 7 (index 0)

  idx 1: 2 < 7  →  new min = 2 at index 1
  idx 2: 9 < 2  →  no
  idx 3: 4 < 2  →  no
  idx 4: 1 < 2  →  new min = 1 at index 4

The scan tracks the smallest value across indices 1 through 4; 1 at index 4 wins.
Step 1 of 5

Steps to visualize

  1. Set sortedEnd to 0.
  2. Scan the unsorted region for its minimum and swap it into index sortedEnd.
  3. Advance sortedEnd and repeat — but stop after k passes instead of continuing to the end.
  4. The value now sitting at index k - 1 is the kth smallest.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Run selection sort for only the first k passes
Statuspass 1

sortedEnd=0. Scanning all 5 values, the minimum is 1 at index 4.

What happens in this step

arr = [7, 2, 9, 4, 1], sortedEnd = 0, min so far = 7 (index 0)

  idx 1: 2 < 7  →  new min = 2 at index 1
  idx 2: 9 < 2  →  no
  idx 3: 4 < 2  →  no
  idx 4: 1 < 2  →  new min = 1 at index 4

The scan tracks the smallest value across indices 1 through 4; 1 at index 4 wins.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function kthSmallest(nums, k) {
  const arr = nums.slice();

  for (let sortedEnd = 0; sortedEnd < k; sortedEnd++) {
    let minIndex = sortedEnd;

    for (let scan = sortedEnd + 1; scan < arr.length; scan++) {
      if (arr[scan] < arr[minIndex]) {
        minIndex = scan;
      }
    }

    if (minIndex !== sortedEnd) {
      const temp = arr[sortedEnd];
      arr[sortedEnd] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  return arr[k - 1];
}
Time
O(n * k)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [7, 2, 9, 4, 1], k = 34example from the docstring
nums = [7, 2, 9, 4, 1], k = 11k=1 returns the overall minimum after a single pass
nums = [7, 2, 9, 4, 1], k = 59k equals the array length, returns the overall maximum
nums = [3, 3, 1, 2, 3], k = 43duplicate values among the k smallest
nums = [5], k = 15smallest valid input, a single element
nums = [1, 2, 3, 4, 5], k = 22already sorted input
nums = [-5, -1, -10, 0, 2], k = 2-5negative values mixed with positive ones

Keep reading