CODEWITHSUNDEEP
algorithmtime-complexity
Aman Jagga
Aman Jagga

Reputation: 305

Finding all unique elements from a big sorted array in log n time?

I have a very big sorted array. How can I count or print all the unique elements of an array??

Suppose my array is [2,3,3,3,4,6,6,7] then output should be 2,3,4,6,7

I know to do it in a n(complexity) time. But interviewer asked me to do this in log n time?? Is it possible?

Upvotes: 4

Views: 3308

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is an algorithm which requires O(logn*k) where k is unique elements:-

set uniQ
int ind = 0;

do {

 uniQ.add(arr[i]);
 ind = BinSearchGreater(arr,arr[ind],ind+1);
 if(ind >= arr.length)
   break;

} while(true);


BinSearchGreater(arr,key,start_ind) : returns index of first element greater than key in subarray starting at start_ind

Time complexity :- Note this algorithm is only good when no of unique elements are small. This is asymptotically O(n*logn) if all are unique so worse than linear.

Upvotes: 7

Flupp
Flupp

Reputation: 886

I would like to know how he (the interviewer) counts every unique element in the array [1,2,3,4,5] without picking at least every element. In this case you have to pick every element to count every element and this will be done in O(n). In my opinion impossible to get a complexity of O(log n), if there are no other requirements to the given array.

Upvotes: 0

Related Questions