CareerCup

* Validate null arrays
* Validate empty arrays
* Create a Hashmap, worstcase Size: N
* Iterate through the array O(n) and set in the Hashmap if the current element is unique or already exists in the map, this also could be achieved using a Hashmap<Integer, Integer> and set the count of the element, but the problem doesn't case about how many times any given element is repeated, only if it is unique or not.
* Iterate on the hashmap O(n) and print only the unique items.

public static void printUnique(int[] array){
		if(array==null){
			throw new IllegalArgumentException("Array cannot be null");
		}		
		if(array.length == 0){
			System.out.println("Empty array");
			return;
		}		
		HashMap<Integer, Object> hashmap = new HashMap<Integer, Object>();
		Object unique = new Object();
		Object duplicated = new Object();		
		for(int i=0; i < array.length ; i++){			
			int current = array[i];			
			if(hashmap.containsKey(current)){
				hashmap.put(current, duplicated);
			}else{				
				hashmap.put(current, unique);				
			}			
		}
		
		Iterator<Integer> iterator = hashmap.keySet().iterator();
		while(iterator.hasNext()){
			Integer key = iterator.next();
			Object tmp = hashmap.get(key);
			if(tmp==unique){
				System.out.print(key + ",");
			}			
		}		
	}

How space complexity for hashmap is O(n)?it has to be O(k)k-width between minimum and maximum in de array.so is time

bit array space - O(log (max_element_size - min_element_size))
[get the range in one iteration O(n) ]
Time Complexity - O(n)

first sort the array in (NLOGN)
then use the following function

void prin_unique(int arr[],int size)
{
     int *a,*b,*c;
     a=&arr[0];
     b=&arr[1];
     c=&arr[2];
     while(b<=&arr[size-1])
     {
       if(*a!=*b && *b!=*c)
         cout<<"unique is "<<*b<<endl;
       a++;
       b++;
       c++;
     }
}

to print the unique elements
extra space is only 3 integer pointer.

We need not sort. We haven't been asked a constant space algorithm.
So,
Step 1) Walk thru array (say A) and find largest number => O(N).
Step 2) Create parallel array B in which just the number of occurences of each element are stored (frequency array line in couting sort) => O(N) in time and O(K) in space where K doesnt depend on N and is the largest number in the array that we found in step 1)

Now go thru array B and print i for all B[i] = 1. => O(N).

Complete algo: O(3N) in time and O(K) in space.

There might be more efficient ways.

Using the bitmap is the way to go.

if its given that you can use extra space then i think hashing will be the best solution... but if no extra space can be use then in that case just use this program which puts the duplicate value to -1 and at the same time print the unique value if its not equal to -1

void removeduplicate(int a[],int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
temp=a[i];
if(temp!=-1&&i!=n-1)
{
for(j=i+1;j<n;j++)
{
if(a[j]!=-1)
{
if(a[i]==a[j])
{
temp=-1;
a[j]=-1;
}

}
}
if(temp!=-1)
cout<<" "<<temp;
}
}

I think we can construct Binary Search tree and hence we can get all Unique element Suppose no of unique element is m then Construction require O(n log m ) time and extra space required is O(m)

If we do not want to use additional storage like HashTable and just print the unique values provided that the array is sorted before hand, here is the C# code below. FindUnique function assumes that nums is already sorted:

private static void FindUnique(int[] nums)
{
    int i = 0;
    int j = i + 1;
    while(i < nums.Length - 1 && j < nums.Length)
    {
        if (nums[i] == nums[j])
        {
            j++;
            if (j < nums.Length && nums[j - 1] != nums[j])
            {
                i = j;
                j = i + 1;
            }
            continue;
        }
        else
        {
            Console.Write("{0} ", nums[i]);
            i++;
            j = i + 1;
        }
    }
}

Is this bad implementation?!

Integer[] ik = {23,53,1,3,6,23,1,7,9,53,9};
		Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
		for(int n: ik){
			
			if(mp.containsKey(n)){
				mp.remove(n);
			}
			else{
				mp.put(n, 1);
			}
			
		}
		
		System.out.println(mp.toString());

In python:

#usr/bin/python

l=[23,53,1,3,6,23,1,7,9,53,9]
l.sort()
r=[]
for i in l : 
    c=l.count(i)
    if c==1 :
        r.append(i)
    i=i+1
print(r)

it can be solved in nlogn complexity using heap sort( dose not matter which u use, mix heap or max heap) below is example using max heap sort:-

a) Heap sort in each iteration gives the max element of the element to be sorted. store it in a temp var say test_unique
b) when u get the max_element from the next iteration of the heap sort compare it with the test_unique from the previous iteration. If they are not same then add test_unique into to unique array.

when the heap sort completes you have your array sorted & as well as unique array with unique elements in the array.

Note heap sort is an in place sort so space complicity is less ( in fact only for the loop variants )

Do a single pass. Keep on adding the elements to a Hashset. Check if the elements exists every time we add. If found, remove the element. Finally the Hashset will only have unique elements.

O(n)