Tuesday, March 25, 2014

Number of unique elements in sorted array with repeated elements

Problem
Find the number of unique elements in sorted array with repeated elements.
Follow up - How can you do it without using extra space
Example
Input = [1,1,1, 2]
Output = 2 i.e. 1 and 2.

Example for follow up
Input = [1,1,2]
Output = 2



Solution
It's not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. If you do restrict the collection to only having unique items, then the answer is trivial; it's the number of items in the collection since they all have to be distinct.

But now lets take the case, where we can't use any space - we have to simply compare the adjacent space.
Method 1 - Iterate through the array and compare adjacent elements

Here is the code (java) which returns the number of unique elements and changes the array structure inplace to contain only unique elements :

public int removeDuplicates(int[] A) {
    if(A.length < 2)
        return A.length;

    int j = 0;
    int i = 1;

    while(i < A.length){
        if(A[i] == A[j]){
            i++;
        }else{
            A[++j] = A[i++];
        }    
    }

    return j+1;
}

Time complexity - O(n)

Method 2- Using hashtable
Here we can add the element to hashset if it is not present, otherwise ignore it. This size of hashset will give us the number of unique elements. But this is not very useful as array is already sorted. So method 1 is better approach.

Reactions:

0 comments:

Post a Comment