How to Solve Kth Smallest Element
What is the Kth Smallest Element Problem?
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
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
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.
During the interview, try not to spend more than 5 minutes discussing the brute force solution. The interviewer will be more interested in the optimal solution(s).
Time/Space Complexity
- Time Complexity:
O(n log(n)), wherenis 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
- Create a max heap of size
k. - Insert each element into the heap - with each insert, we “heapify”, which means we re-sort the elements to satisfy the heap property.
- If the size of the heap exceeds
k, pop the top element of the heap. - After traversing all the elements of the array, return the top element of the heap.
Note that if we were looking for the kth largest element, we would perform the same above steps with a min-heap.
Replacing the top element of the heap of size k takes logk time. So in the worst case, it would be done n times and effectively, the time taken would be O(nlogk).
Kth Smallest Element Python and Java Solutions - Heap
import heapq
class Solution:
def findKthSmallest(self, nums: List[int], k: int) -> int:
# 1: Create max heap (simulated by negative values)
max_heap = []
for element in nums:
# 2: Insert each element to the heap
heappush(max_heap, -element)
# 3: If the size of the heap exceeds k, pop the element at the top
if len(max_heap) > k:
heappop(max_heap)
# 4: return top element of max heap
return -heappop(max_heap)1import heapq
2class Solution:
3 def findKthSmallest(self, nums: List[int], k: int) -> int:
4 # 1: Create max heap (simulated by negative values)
5 max_heap = []
6
7 for element in nums:
8
9 # 2: Insert each element to the heap
10 heappush(max_heap, -element)
11 # 3: If the size of the heap exceeds k, pop the element at the top
12 if len(max_heap) > k:
13 heappop(max_heap)
14
15 # 4: return top element of max heap
16 return -heappop(max_heap)Time/Space Complexity
- Time Complexity:
O(n log(k)), wherenis the number of elements in nums andkis 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.
The average case time complexity of quickselect algorithm is O(n). However, in the worst case, the time complexity is O(n²) — this could be the case when you have lot of repeated elements. Make sure to discuss this with the interviewer before moving on to coding!
Kth Smallest Element Python and Java Solutions - Quickselect
class Solution:
def partition(self, left: int, right: int, nums: list[int]):
# get random pivot index
pivot_index = random.randint(left, right)
pivot_value = nums[pivot_index]
# move pivot element to the end
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
# when we find an element less than pivot_value, move it left of pivot_index and increment the swap position
i = left
for j in range(left, right):
if nums[j] < pivot_value:
nums[i], nums[j] = nums[j], nums[i]
i += 1
# move pivot to its final place
nums[right], nums[i] = nums[i], nums[right]
return i
def quickselect(self, left: int, right: int, k_target_index: int, nums: list[int]):
if left == right:
return nums[left]
# find the pivot's correct position
pivot_index = self.partition(left, right, nums)
# if the pivot index is equal to our target, we're done
if k_target_index == pivot_index:
return nums[pivot_index]
elif k_target_index < pivot_index:
return self.quickselect(left, pivot_index - 1, k_target_index, nums)
else:
return self.quickselect(pivot_index + 1, right, k_target_index, nums)
def findKthSmallest(self, nums: List[int], k: int) -> int:
n = len(nums)
return self.quickselect(0, n - 1, k - 1, nums)1class Solution:
2 def partition(self, left: int, right: int, nums: list[int]):
3 # get random pivot index
4 pivot_index = random.randint(left, right)
5 pivot_value = nums[pivot_index]
6 # move pivot element to the end
7 nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
8 # when we find an element less than pivot_value, move it left of pivot_index and increment the swap position
9 i = left
10 for j in range(left, right):
11 if nums[j] < pivot_value:
12 nums[i], nums[j] = nums[j], nums[i]
13 i += 1
14 # move pivot to its final place
15 nums[right], nums[i] = nums[i], nums[right]
16 return i
17
18 def quickselect(self, left: int, right: int, k_target_index: int, nums: list[int]):
19 if left == right:
20 return nums[left]
21 # find the pivot's correct position
22 pivot_index = self.partition(left, right, nums)
23 # if the pivot index is equal to our target, we're done
24 if k_target_index == pivot_index:
25 return nums[pivot_index]
26 elif k_target_index < pivot_index:
27 return self.quickselect(left, pivot_index - 1, k_target_index, nums)
28 else:
29 return self.quickselect(pivot_index + 1, right, k_target_index, nums)
30
31 def findKthSmallest(self, nums: List[int], k: int) -> int:
32 n = len(nums)
33 return self.quickselect(0, n - 1, k - 1, nums)Time/Space Complexity
- Time Complexity:
O(n)in average,O(n²)in worst-case. - Space Complexity:
O(1)
Practice the Kth Smallest Element Problem With Our AI Interviewer
Practice the Kth Smallest Element Problem With Our AI Interviewer
Kth Smallest Element Frequently Asked Questions (FAQ)
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.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
