CareerCup

mantain a hash table...(element as key and index as value)
mantain another boolean array indicating the whether the element has been detected more than once...intialize it to false..
whnevr we encounter an element search in hash table..if found get it index n mark it as true and also the index of current element as true..
continue this for 1 to n elements in the array..
Then transverse the bool array...1st false indicates the unique no..
i suppose this will b linear n all

Assuming it is array of bytes.

public static int firstUniqueElement(byte a[])
{
byte temp[]=new byte[256];

byte b=0;
Arrays.fill(temp, b);

for(int i=0; i<a.length; i++)
{
b=a[i];
temp[b]++;
}
for(int i=0; i<a.length; i++)
{
b=a[i];
if(temp[b]>1)
continue;
else
return b; //first unique element will be returned
}

return -1;
}

The above code can be made more robust. But the general idea is to traverse once and increment the count and again re-traverse till you find the first unique element in the array (by looking up from the temp array).

1) First, scan the entire given array & load the hashtable (key = element, value = index). Repeated elements in the array will have hash collision. This takes O(n) to scan the entire array & O(1) for each insertion into the hash table. We will make n insertions into the hashtable.

2) Traverse the given array again for the second time, and, for each element, check in hashtable for repetition or hash collision. If yes, take it's index value and mark as true at the same index in another array of booleans. Else, mark as false at it's index in the boolean array. Again, O(n) overall for this step.

3) Now, traverse the boolean array & the index with the first false is the index in the given array with the first non-repeated unique element. This step will take O(n) worst time.

So, overall complexity comes to O(n).

1. Create hashtable: key = element, value = repeat (type: boolean)
2. Scan the entire array.
3. Load each array element into hashtable. Check if the element already exists in hashtable. If it does, check if its value is false. If it is false, then set it to true. If it is true, don't do anything. If the element does not exist then insert it in the hashtable with a value false.
4. Scan the entire array again.
5. The first unique element is the one for which the value in the hashtable entry is false.

This avoids the need for creating an additional boolean array.

Example Java code:

Hashtable<Integer, Boolean> positions = new Hashtable<Integer,Boolean>();
      int[] elements = {2, 2, 4, 5, 1, 6, 0, 9, 1, 4, 5, 10};
      for(int i=0; i<elements.length; i++) {
          if(positions.containsKey(elements[i])) {
              if(positions.get(elements[i]).booleanValue() == false) {
                  positions.put(elements[i],true);
              }
          }
          else {
              positions.put(elements[i], false);
          }
      }
      for(int j=0; j<elements.length; j++) {
          if (positions.get(elements[j]).booleanValue() == false) {
              System.out.println("First unique element is: " + elements[j] + " at position " + j);
              break;
          }
      }

//Sort entire array
//check by this condition
if (a[i]!=a[i+1]&&a[i+1]!=a[i+2]) return a[i+1] as first occurence

Solutions with with the hashTable, temp[256] etc. have the right idea. But what you want is ideally a hashSet<Integer>. If an element is already exists in the hashSet the add(Integer a) returns false, else true.

Here is the algorithm coded up in java

int firstRepeatedElement(int[] array){
assert(array != null);
hashSet<Integer> myset = new hashSet<Integer>()
for(int i= 0; i<array.length; i++)
if(myset.add(array[i])

}

Solutions with with the hashTable, temp[256] etc. have the right idea. But what you want is ideally a hashSet<Integer>. If an element is already exists in the hashSet the add(Integer a) returns false, else true.

Here is the algorithm coded up in java

int firstRepeatedElement(int[] array){
assert(array != null);
hashSet<Integer> myset = new hashSet<Integer>()
for(int i= 0; i<array.length; i++)
if(myset.add(array[i])
return array[i];

return -1;
}

}

The most efficient algorithm to solve the above problem statement will be to use a hash map we will store the count of every element in the array and then, after all, elements count are stored we will traverse the map and print the element whose count in the array is 1.