Select the Kth Smallest Value

Practice Exercise Intermediate Medium In-place Index Mapping Array Quickselect

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement kth_smallest(values, k). k is one-based and valid. Return the kth smallest value without sorted or list.sort. Duplicates count separately.

Starter code

def kth_smallest(values, k):
    pass

Test cases

duplicates-rank

{
  "args": [
    [
      7,
      2,
      5,
      2,
      9
    ],
    3
  ]
}

Expected: 5

largest

{
  "args": [
    [
      3,
      1,
      4
    ],
    3
  ]
}

Expected: 4

Wizard outline

Step 1: Resolve a singleton rank
Return the only value for k=1. A one-value search space is the selection base case.
Step 2: Locate the rank around one pivot
Resolve a small partition including duplicates. Strict lower, equal, and higher groups define consecutive rank ranges.
Step 3: Discard irrelevant ranks
Continue only in the partition containing k. Every discarded lower or equal value has a known rank before every higher candidate.

Footguns and prerequisites

Ignoring the equal partition mishandles duplicates.
Failing to subtract discarded ranks selects the wrong suffix position.
functions
lists and tuples
control flow

Reviewed references

Python More on Lists

Recommended approach and implementation

Three-way partition candidates and retain only the partition containing the one-based target rank.

Why it works: Partition sizes define exact consecutive rank ranges. Discarding a range and translating k preserves the target rank until it falls in an equal group, whose pivot is the answer.

def kth_smallest(values, k):
    candidates = list(values)
    while True:
        pivot = candidates[len(candidates) // 2]
        lower = [value for value in candidates if value < pivot]
        equal = [value for value in candidates if value == pivot]
        higher = [value for value in candidates if value > pivot]
        if k <= len(lower):
            candidates = lower
        elif k <= len(lower) + len(equal):
            return pivot
        else:
            k -= len(lower) + len(equal)
            candidates = higher