Find the kth minimum element in an array without sorting

Question

Mohaan · Accepted Answer

If it is not so stressed on time complexity, we can find it in O(n^2).
Use two loops. Outer loop will take element one by one sequentially from 0 to n-1 and second loop will run from 0 to n-1 finding whether the arr[i] > arr[j], if so have a count array and increment it based on i.

Finally loop through the count array and find which one is equal to k and display that value in arr.

Anonymous · Answer

If the array is not sorted then we can use min heap to get kth smallest element.
1. Forming a Min heap O(n logn) complexity.
2. For values 1 to k, remove elements from root and re-form the heap O(k logn) complexity

Freshworks

Freshworks Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches