TuSimple Interview Question: How to get the k smallest element in O(klogk) time

Notifications

TuSimple

How to get the k smallest element in O(klogk) time

Anonymous

May 21, 2018

do you mean O(nlogn)? where n is size of array?

Anonymous

Jan 27, 2019

To find k smallest elements among n elements in total, efficient implementation takes O(n logk), using a binary heap of size k.

Anonymous

Oct 18, 2018

I think it was nlogn, otherwise if k = 1, O(1) seems impossible for unsorted array