1

Recently I came across a question,

There is an unsorted array of n elements. Once we sort the array, i th index will have an element. How would you find which element is going to be present on i th index in O(n) complexity on the unsorted array?

I tried many methods, finally I came to a conclusion that we may need to use an hash map. But later I found that hash map implementation usually follow a tree structure which has an log n complexity in insertion.

How shall I proceed?

Sreeraj Chundayil
  • 5,548
  • 3
  • 29
  • 68
  • 1
    https://en.wikipedia.org/wiki/Selection_algorithm – Jeffrey Bosboom Mar 01 '15 at 18:55
  • 2
    **Hash** maps (as their name might suggest) are implemented using **hash** tables (which have an amortized insertion complexity of `O(1)`). Otherwise they would be called **tree** maps and be implemented using binary search **trees** (and have an amortized insertion complexity of `O(log(n))`). ;) – Regexident Mar 01 '15 at 20:25

1 Answers1

3

You need Linear Time Selection algorithm. Its running time is O(n) in the worst case. You can find its description in chapter "9.3 Selection in worst-case linear time" of Introduction to Algorithms, Second Edition or on the Internet e.g. here.
You can also use Randomized select algorithm. It has the expected linear time. You can find its description in chapter "9.2 Selection in expected linear time" of the same book.

Vadim
  • 567
  • 6
  • 13