Skip to content
Hello Python
Algorithm1 Practice4 Interview

Quickselect

Partition like quicksort while recursing into only the side containing the requested rank. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Quickselect when the prompt's constraints and required operations match this shape: Partition like quicksort while recursing into only the side containing the requested rank.

Pybit demonstrates Quickselect in a professional Python interview workspace.
On this page · Partition Toward One Rank

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Quickselect Code Labs

Partition Toward One Rank

Quickselect uses the same partition operation as quicksort, but only the side containing the target rank remains relevant.

Discard the Side Without the Target

After partition, the pivot has its final rank. If that rank is below target, discard it and the left side; if above, discard it and the right side.

Trace Quickselect Partitions

Reference
def quickselect_trace(values,k):
    values=values.copy();left=0;right=len(values)-1;trace=[]
    while left<=right:
        pivot=values[right];boundary=left
        for index in range(left,right):
            if values[index]<=pivot:values[boundary],values[index]=values[index],values[boundary];boundary+=1
        values[boundary],values[right]=values[right],values[boundary];trace.append([left,right,boundary])
        if boundary==k:break
        if boundary<k:left=boundary+1
        else:right=boundary-1
    return trace
Practice

Implement quickselect_trace(values,k). k is zero-based smallest rank; return [left,right,pivot_index] after each partition until found.

Public tests

  • Discard the side without the rank

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Interpret K and Pivot Rank Carefully

Translate one-based kth-smallest input to zero-based target exactly once. Kth largest can map to n minus k or invert the partition relation; mixing conventions causes off-by-one errors.

Find the Kth Smallest Value

Reference
def kth_smallest(values,k):
    values=values.copy();target=k-1;left=0;right=len(values)-1
    while True:
        pivot=values[right];boundary=left
        for index in range(left,right):
            if values[index]<=pivot:values[boundary],values[index]=values[index],values[boundary];boundary+=1
        values[boundary],values[right]=values[right],values[boundary]
        if boundary==target:return values[boundary]
        if boundary<target:left=boundary+1
        else:right=boundary-1
Practice

Implement kth_smallest(values,k). k is one-based; return the kth smallest value without mutating input.

Public tests

  • Interpret one-based rank correctly

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Control Randomized Worst Cases

Random pivots yield expected O(n) work because only one shrinking side is processed. Adversarial pivots can cause O(n squared); randomization or median selection reduces risk but does not make the simple version stable.

Explain It in an Interview

Say: “Partition fixes one pivot rank. Only one side can contain target rank k, so I discard the other instead of sorting it.” State input mutation, duplicates, expected and worst-case time, and rank convention.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Quickselect complete workflowO(n) average, O(n^2) worstO(n) average, O(n^2) worstThree-way partition candidates and retain only the partition containing the one-based target rank.

Space

O(n) for the focused Select the Kth Smallest Value implementation.

Assumptions

  • 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.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Quickselect invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The resolved region satisfies the target ordering relation.
  3. The unresolved region still contains every item not yet placed.
  4. Partition values into strict and equal groups. Preserve this claim after every transition.
  5. Translate a one-based rank while discarding irrelevant partitions. Preserve this claim after every transition.

When To Use Or Avoid Quickselect

Use It When

  • Use Quickselect when this precondition is stated or can be proved: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Use it when this maintained state removes repeated work: The resolved region satisfies the target ordering relation.

Choose Another Tool When

  • Avoid Quickselect when this precondition is absent: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The comparison, key domain, stability need, and memory constraints match the selected ordering method.

Avoid

def kth_smallest(values, k):
    pass

Use instead

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

Where you will hit this: Select the Kth Smallest Value(opens in a new tab)

Breaking the state transition

Moves into the higher partition without translating k past discarded values.

Prevent it: Preserve this proof obligation: The resolved prefix, suffix, rank, digit pass, or bucket remains in its documented final relation.

Avoid

def kth_smallest(values,k):
    a=list(values)
    while True:
        p=a[0]; lo=[x for x in a if x<p]; eq=[x for x in a if x==p]; hi=[x for x in a if x>p]
        if k<=len(lo):a=lo
        elif k<=len(lo)+len(eq):return p
        else:a=hi

Use instead

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

Where you will hit this: Select the Kth Smallest Value(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n) average, O(n^2) worst.

Avoid

def kth_smallest(values,k):
    a=list(values)
    while True:
        p=a[0]; lo=[x for x in a if x<p]; eq=[x for x in a if x==p]; hi=[x for x in a if x>p]
        if k<=len(lo):a=lo
        elif k<=len(lo)+len(eq):return p
        else:a=hi

Use instead

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

Where you will hit this: Build Tree from Inorder and Postorder(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.