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:
Explanation: 4 is the 2nd smallest element in the array.
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). 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.
You can sort the array, and return the kth element.
Time Complexity O(nlogn) 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.
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 k
th smallest element in the correct location.
Here's the code for this:
Time Complexity O(n) average, O(n2) 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(nlogn) 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).
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()