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:

arr = [7,1,5,4]k = 2=> returns 4\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:

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:

Time Complexity O(n+klogn)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)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.

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

Mark as Completed:
Submits:
kthSmallestElement
Test your code to get an output here!
kthSmallestElement(
)
Test your code to get an output here!