Finding first non-repeating number in integer array

Question

I got this question for an exam:

Given an integer array find the first number which is not repeating in array using O(N) time complexity and O(1) space complexity.

I couldn't think of any solution. I know I can iterate over the array and maintain a linkedhashmap which will store both array element and number of times it appears and then in the end I have to search hashmap to find that number. Space complexity is greater than O(1) but I couldn't think of other solution.

I also read problem carefully and the said that max size of array would be 1million. I think if we can create a custom hashmap which will utilise an fixed size array of 1 million size then this can be achieved in O(1) space complexity as in that case storage required would be constant but nore sure if I am correct. Please let me know if there is any other solution.

Answer 1

If there are exactly TWO (or in multiples of 2) entries for all elements except one element, which will be non-repeating, you can use XOR operator.

Example:

int x=arr[0];
for(i=1;i<1000;i++)
  x^=a[i];
printf("Non-repeating: %d",x);

Any number XORed with itself is 0. So, if any number appears twice it will be 0 in the overall XOR result, thus leaving only the non-repeating number in x.

Note: If you have 1 million numbers, the variable to store the XOR result must be large enough.

Answer 2

I believe the trick to solve the problem is :

max size of array would be 1million

since :

O(1) space means that the memory required by the algorithm is constant

then space complexity will automatically becomes O(1) given the constant 1M. NOTE. 1M is still a constant number even though its a really large number. thus we only need to concentrate on time complexity.

Using a LinkedHashMap we can add a new element with O(1) and retrieve element with O(1) thus updating an entry will take O(1) too. it also preserves the order. therefore, we can find the earliest entry

then the problem will become simple in two steps:

1. build up the LinkedHashMap --> O(n)
2. find the earliest number which its count is 0 --> O(n)

each of the above steps requires O(n) thus overall time complexity is O(2n) = O(n).

Answer 3

To find first non-repeating number in given integer array

UPDATE: Found a better solution. I think we can solve it in O(n) time complexity using an additional data structure such as HashMap. Iterate through the array, and put the element as key and the element's index position in array as the value in the map. if the key already exists, can either remove the key-value pair or just set the value to -1. Once the entire array is traversed, then we can get the keySet() from the hashmap, and then find the key which has lowest value(ignore -1). so this would be Time Complexity: O(N) Space Complexity: O(N)

Old solution: We can solve this by, creating another array which is obtained by sorting the given array. This would take O(nlogn) time. then we can iterate through each element in given input array, try to find the element & compare with next element in the sorted array, if repeated continue for the next element in given array, if not repeated, then we found the first non-repeating element in given input array of integers.

time complexity: O(nlogn)
space complexity: O(n)

P.S: I am sorry, hadn't read all the comments, James Kanze has already provided this solution in comments, credits to him.

Answer 4

I did this using PowerShell

[int[]]$arr = @(6,2,1,2,6,1,7)

$Collection = New-Object 'System.Collections.Generic.list[System.Object]'
$props=[ordered]@{"Index"=9999;"Value"=9999;"Numcount"=9999}
$record = New-Object -TypeName psobject -Property $props
$Collection.Add($record) #This record is added to do a Contains operation 
#for future items to be added in the $collection object

for($i =0;$i -lt $arr.Length;$i++)
{
if($i -eq 0)
{
    $props=[ordered]@{"Index"=$i;"Value"=$arr[$i];"Numcount"=1}
    $record = New-Object -TypeName psobject -Property $props
    $Collection.Add($record)
}


elseif($Collection.value.Contains($arr[$i]))
{

    $count = ($Collection | ?{$_.Value -eq $arr[$i]} | select -First `
1).Numcount
    ($Collection | ?{$_.Value -eq $arr[$i]} | select -First 1).Numcount = `
$count+1
}
else
{
    $props=[ordered]@{"Index"=$i;"Value"=$arr[$i];"Numcount"= 1}
    $record = New-Object -TypeName psobject -Property $props
    $Collection.Add($record)
}

}
Write-Output "The first non repeating number in the array is listed below"
$Collection | Sort-Object Numcount -Descending | ?{$_.Numcount -eq 1} | 
Select -First 1

OUTPUT:-
The first non repeating number in the array is listed below
Index Value Numcount
----- ----- --------
6     7        1