Given a read only array of $n$ integers, find the $k$ largest numbers in the array in $O(n)$ time possibly using $O(k)$ extra space.
EDIT: Note $k$ is not a constant, so when I say $O(n)$ the constant factor in $O(n)$ shouldn't depend on k.
Posted: Jul 01 '12
Seen: 137 times
Last updated: Jul 11 '12
@rizwanhudda : k is not a constant... i.e., the constants within O(n) should be independent of k.... right ?
Shiva Kintali (Jul 05 '12)edit@kintali Yes. k is not constant.
rizwanhudda (Jul 11 '12)edit