How to Solve Kth Smallest Element

What is the Kth Smallest Element Problem?

The Kth Smallest Element in an Array problem that involves searching through an array of integers and finding the k'th smallest element. Although on the surface this task is trivial, the challenge is in applying advanced sorting algorithms and data structures, such as a heap, recursion, and quickselect, and communicating tradeoffs in time complexity.

Kth Smallest Element in an Unsorted Array Examples

Given an integer array nums and an integer k, return the kth smallest element in the array.

Example 1

Input: nums = [1,5,7,6,4,3,2], k = 3
Output: 3

Example 2

Input: nums = [1,1,1,2,2,3], k = 3
Output: 1

Example 3

Input: nums = [1], k = 1
Output: 1

Constraints

• 1 <= nums.length <= 100000
• -10000 <= nums[i] <= 10000

Solution to the Kth Smallest Element Interview Question

There are three strategies you can use to solve the kth smallest element in an unsorted array problem — Brute Force, Heap, and Quickselect.

1. Brute Force

The naïve approach to solving the problem would be to:

• sort the array in increasing order and then,
• pick the kth element of the array

However, sorting the array would take O(n log(n)) worst-case time complexity here, where n is the size of the array.

Time/Space Complexity

• Time Complexity: O(n log(n)), where n is the number of elements in nums.
• Space Complexity: O(1), no additional data structure used.

2. Heap Approach

By using the brute force sorting technique, we are unnecessarily sorting the entire array of n elements. Since we are interested only in the kth element in sorted order, we could possibly restrict the sorting/re-arrangement to k elements, which would limit the sorted array to a length of k. The heap data structure helps us to achieve this optimization.

Heap Approach Steps

1. Create a max heap of size k.
2. Insert each element into the heap - with each insert, we “heapify”, which means we re-sort the elements to satisfy the heap property.
3. If the size of the heap exceeds k, pop the top element of the heap.
4. After traversing all the elements of the array, return the top element of the heap.

Time/Space Complexity

• Time Complexity: O(n log(k)), where n is the number of elements in nums and k is the heap size.
• Space Complexity: O(k), for the heap.

3. Quickselect Approach

Quickselect algorithm is an algorithm quite similar to quicksort algorithm where you repeatedly partition a given array based on a pivot element, repeating the process until you have a subarray of length of one. Elements less than the pivot are moved to the left, and elements greater than the pivot are moved to the right. After each partition step, the pivot element is at the correct position in the ordered list. Since we are interested in the kth element, we would have derived that when the pivot element index in the array becomes k-1. If the pivot index is greater than target index k-1, continue partitioning on the left side; if the pivot index is smaller than target index k-1, then partition on the right side. In a particular iteration, if the pivot element index becomes k-1, we can return the pivot element itself.

Time/Space Complexity

• Time Complexity: O(n) in average, O(n²) in worst-case.
• Space Complexity: O(1)

Kth Smallest Element Frequently Asked Questions (FAQ)

How do you find the kth smallest element in an array?

There are 3 ways to solve this problem: brute force, using a heap, and using quickselect. The brute force approach would be to sort the array, and then pick the kth element in the array. This approach runs in O(n log(n)) time because you have to sort. A more efficient approach is to use a heap. To do this, you would create a max heap of size k and insert each element into the heap. If the size of the heap exceeds k, pop the top element of the heap. Finally, after traversing all the elements of the array, return the top element of the heap. This approach runs in O(nlogk) time. Finally, you could use quickselect. The idea behind quickselect is similar to quicksort, but instead of sorting the entire array, quickselect only focuses on the elements that are needed to find the kth smallest element. The average case time complexity of the quickselect algorithm is O(n), but in the worst case the time complexity is O(n²) - this could be the case when you have a lot of repeated elements.

What's the most efficient way to find the kth smallest element in an array?

It depends. Using a heap will run in O(nlogk) time, and using quickselect will run in O(n) on average but could go up to O(n²) in the worst case.