Given an array of integer. Find the kth smallest element in the array in a most efficient manner. For example: A = [2, 1, 0, 3, -1, 3] and k=3 then the 3rd smallest element is 1. This is also (6-3) = 3rd largest element. A trivial solution is to sort the array. But question […]
Tag Archives: QuickSelect
Given an array containing N points find the K closest points to the origin in the 2D plane. You can assume K is much smaller than N and N is very large. Notice the key requirement here: “K is much smaller than N. N is very large”. Definitely the brute-force solution by finding distance of […]