Approach #1: Sorting [Accepted]
Intuition
Let's sort the array. Then, all duplicate values will be side by side, making it easy to identify the unique value.
Algorithm
Sort the array. While nums[2*j] == nums[2*j + 1]
, the unique value must occur later in the array. Otherwise, it occurs at nums[2*j]
. In our implementation, we will set i = 2*j
.
Python
class Solution(object):
def singleNumber(self, nums):
nums.sort()
for i in range(0, len(nums), 2):
if i + 1 == len(nums) or nums[i] != nums[i + 1]:
return nums[i]
Complexity Analysis

Time Complexity: $$O(N \log N)$$, where $$N$$ is the length of the given array
nums
, for sorting the array. Afterwards, the $$O(N)$$ factor of searching the array is dominated by this factor. 
Space Complexity: $$O(N)$$ for sorting with Timsort, the default sorting algorithm built in Python. Other sorting algorithms may have different complexities depending on their implementation.
Approach #2: Count With Dictionary [Accepted]
Intuition
Let's count the number of occurrences of each number. The answer is the number that occurs exactly once.
Algorithm
For each number, increment it's count in a dictionary or HashMap type structure. Then, loop through each number and return it if it has a count of 1.
Python
class Solution(object):
def singleNumber(self, nums):
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
for x in count:
if count[x] == 1:
return x
Alternate Implementation
class Solution(object):
def singleNumber(self, nums):
count = collections.Counter(nums)
for x in count:
if count[x] == 1:
return x
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the length of the given array
nums
. Every unique value is processed up to three times: twice when adding to the count, and once when searching the answer. 
Space Complexity: $$O(N)$$, where $$N$$ is as defined above. Each number must be stored in the dictionary, and there are at least $$N/2$$ of them (and at most $$O(N)$$), which is order $$O(N)$$.
Approach #3: Manage Set of Uniques [Accepted]
Intuition and Algorithm
Let's remember all currently unique values in some Set or Object structure. At the end, we'll only have one unique value.
Python
class Solution(object):
def singleNumber(self, nums):
uniques = set()
for x in nums:
if x in uniques:
uniques.remove(x)
else:
uniques.add(x)
return uniques.pop()
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the length of the given array
nums
. Every value is processed once. 
Space Complexity: $$O(N)$$, where $$N$$ is as defined above. The set
uniques
could contain up to $$\left \lceil{N/2}\right \rceil$$ elements, which is order $$O(N)$$.
Approach #4: Mathematical [Accepted & Optimal]
Intuition
Motivated by not using additional space, let's ask what state (of constant complexity) we would need to know upon processing some of the numbers, to be able to construct the answer upon processing the rest of the numbers.
Additionally, if we have an algorithm that works on binary numbers, we can extend our algorithm to work on nonnegative integers by performing the algorithm for each bit. For example, [2, 2, 1]
is [10, 10, 01]
in binary, and our algorithm on [1, 1, 0] > 0
and [0, 0, 1] > 1
can be used to determine the final answer of 01
in binary.
Investigation
For binary numbers, it's clear that there are 4 differentiated states that we could be in after looking at some of the numbers:
 State X: Seen no uniques  eg.
[0, 0, 1, 1]
 State Y: Seen a unique of 0  eg.
[0, 1, 1]
 State Z: Seen a unique of 1  eg.
[1, 1, 1]
 State A: Seen a unique of 0 and 1  eg.
[0, 0, 0, 1]
And that we would like the following transitions:
 X + 0 = Y; X + 1 = Z
 Y + 0 = X; Y + 1 = A
 Z + 0 = A; Z + 1 = X
 A + 0 = Z; A + 1 = Y
where + is some operator (not necessarily commutative).
Bitwise operators also naturally work on all bits of the integer at once. If the operator is the bitwise XOR operator, then $$X = Y = 0$$, $$Z = A = 1$$ is a solution, so let's use that.
Algorithm
Simply XORsum all the numbers together.
Python
class Solution(object):
def singleNumber(self, nums):
ans = 0
for x in nums:
ans ^= x
return ans
Alternative Implementation
class Solution(object):
def singleNumber(self, nums):
return reduce(operator.xor, nums)
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the length of the given array
nums
. Every value is processed once. 
Space Complexity: $$O(1)$$. The current answer is stored as a single integer.