how to search in O(1)

I want to search an element in an integer array in O(1), what is the best way to do it, and values of elements are greater than array size. thank you.

Use hash (HashSet) if you only insert, remove and check if set contains a distinct value.

If you use c++ then the alternative would be to use std::unordered_map it is internally implemented as Hash Table and hence gives you an O(1) search time in average case. Refer this and this for more details.

If your data points are from a set of discrete values (such as integers from 1 to 1,000,000) you can keep an array of the count of each possible value. This is simpler than a hash table and doesn’t need rehashing or collision detection, but uses more memory.

Else specify the details of your requirements, like functions to be performed and required time complexity, Number of elements.

is it for java or c++


I typically use java, so HashSet came to my mind.

unordered map in c++ is same as HashSet in java will give O(1) amortised time complexity, while ordered map give O(logN) time complexity.

1 Like