Iteration

Kth Smallest Element

Lesson

Problem: Given an array of integers arr and an integer k, return the kth smallest element in the array.

The array will contain unique elements.

Example:

\notag \begin{align*} & \texttt{arr = [7,1,5,4]} \\ & \texttt{k = 2} \\[4bp] & \texttt{=> returns 4} \end{align*}

Explanation: 4 is the 2nd smallest element in the array.

First Few Test Cases:

kthSmallestElement([1], 1)
# 1

kthSmallestElement([1, 2], 1)
# 1

kthSmallestElement([1, 2], 2)
# 2

To solve this problem, you can turn the array into a Heap.

To find the kth smallest element, you can pop the heap k-1 times. The kth smallest element will be at the top when you're done, and you can return it as the solution.

Here's the code for doing this:

import heapq

def kthSmallestElement(arr, k):
    
    heapq.heapify(arr) # turn array into heap

    for _ in range(k-1): # pop heap k-1 times
        heapq.heappop(arr)

    return arr[0] # return root of heap

Time Complexity $O(n + k \log n)$ . It takes O(n) time to create a heap. It takes O(log n) time to pop the heap, and you pop the heap k times. This gives a total time of O(n + k log n).

Space Complexity $O(1)$ . You only modify the input array, and use no additional space.

Another solution is to sort the array, but this is slow. See below for details.

Open SpoilerClose Spoiler

You can sort the array, and return the kth element.

def kthSmallestElement(arr, k):
    arr.sort()
    return arr[k-1]

Time Complexity $O(n \log n)$ with a regular comparison sorting algorithm. This is not optimal since you're only looking for a single element. Sorting the entire array is not needed.

Space Complexity $O(1)$

Amazingly, we can get the runtime down to $O(n)$ using academic algorithms like QuickSelect.

Open SpoilerClose Spoiler

The key idea is that sorting all the elements is redundant, because we only need to find a single, kth smallest element.

"QuickSelect" is an algorithm you can use to quickly place a single element in the correct location. To do this, you pick a random element in the Array, and place all the smaller elements to the left of it, and all the larger elements to the right of it. This is called partitioning the Array, and we implemented it in QuickSort.

You can partition the array recursively until you place the kth smallest element in the correct location. Here's the code for this:

import random 

def kthSmallestElement(arr, k):

    def quickSelect(i, j):
        # pick a random value in the array
        val = arr[random.randrange(i,j+1)]

        # partition the array based on the value
        pL, pR = partition(arr, i, j, val)

        # rename variable to `p` for convenience
        # elements are unique, so p = pL = pR
        p = pR

        # do a binary-type search for the `k`th smallest element
        if p == k-1: return arr[p]
        if p < k-1:  return quickSelect(p+1, j)
        else:        return quickSelect(i, p-1)

    return quickSelect(0, len(arr)-1)

Time Complexity $O(n)$ average, $O(n^2)$ worst-case. You can improve the worst-case complexity using "Median-Of-Medians" and "IntroSelect".

You might be wondering "doesn't this break the idea that sorting has to take at least $O(n \log n)$ time?" It doesn't actually break this idea, because this algorithm only essentially sorts a single element, and not all of the elements.

Space Complexity $O(1)$ .

Mark as Completed:

Submits:

kthSmallestElement

Test your code to get an output here!

kthSmallestElement(

)

Test your code to get an output here!