Tag Archives: kth smallest

Top K or K-most frequent words in a document

Given a document (or stream) of words. Find the top k most frequent words in the document (or stream). For example, if stream = “aa bb cc bb bb cc dd dd ee ff ee dd aa ee”. That is, {“dd”=3, “ee”=3, “ff”=1, “aa”=2, “bb”=3, “cc”=2}. Then top 3 most frequent words are: {“dd”, “ee”, […]

Kth smallest/minimum element in a BST – Rank of a BST node

Given a binary search tree. Find the kth smallest element in the BST. A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current […]

Kth smallest/largest element in an array

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 […]

Kth Smallest Element and median of Two Sorted Arrays

Given two sorted arrays find the element which would be kth in their merged and sorted combination. For example, A=[1, 1, 2, 3, 10, 15] and B=[-1, 2, 3, 4, 6, 7] then k=8th smallest element would be 4 as it appears in 8th position of the merged sorted array=[-1, 1, 1, 2, 2, 3, […]

K closest points

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 […]