find the kth smallest element in linear time using divide and conquer recall we can do this trivially in onlogn time sort the list and access kth element in constant time this is a divide and conquer algorithm that can find a solution in on time for more information of this algorithm https web stanford educlassarchivecscs161cs161 1138lectures08small08 pdf choose a random pivot for the list we can use a more sophisticated algorithm here such as the medianofmedians algorithm return the kth smallest number in lst kthnumber2 1 3 4 5 3 3 kthnumber2 1 3 4 5 1 1 kthnumber2 1 3 4 5 5 5 kthnumber3 2 5 6 7 8 2 3 kthnumber25 21 98 100 76 22 43 60 89 87 4 43 pick a pivot and separate into list based on pivot partition based on pivot linear time if we get lucky pivot might be the element we want we can easily see this small elements smaller than k pivot kth element big elements larger than k pivot is in elements bigger than k pivot is in elements smaller than k choose a random pivot for the list we can use a more sophisticated algorithm here such as the median of medians algorithm return the kth smallest number in lst kth_number 2 1 3 4 5 3 3 kth_number 2 1 3 4 5 1 1 kth_number 2 1 3 4 5 5 5 kth_number 3 2 5 6 7 8 2 3 kth_number 25 21 98 100 76 22 43 60 89 87 4 43 pick a pivot and separate into list based on pivot partition based on pivot linear time if we get lucky pivot might be the element we want we can easily see this small elements smaller than k pivot kth element big elements larger than k pivot is in elements bigger than k pivot is in elements smaller than k
from __future__ import annotations

from random import choice


def random_pivot(lst):
    
    return choice(lst)


def kth_number(lst: list[int], k: int) -> int:
    
    
    pivot = random_pivot(lst)

    
    
    small = [e for e in lst if e < pivot]
    big = [e for e in lst if e > pivot]

    
    
    
    
    
    if len(small) == k - 1:
        return pivot
    
    elif len(small) < k - 1:
        return kth_number(big, k - len(small) - 1)
    
    else:
        return kth_number(small, k)


if __name__ == "__main__":
    import doctest

    doctest.testmod()