Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
Constraints:
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104Problem Overview: You get an integer array where every element appears exactly twice except for one element that appears once. Your task is to return that single number. The challenge is solving it efficiently without unnecessary extra work.
Approach 1: Hash Map (O(n) time, O(n) space)
The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map where the key is the number and the value is its count. After building the map, scan through the entries and return the element whose frequency is 1. This works because hash lookups and updates run in constant time on average. The trade‑off is extra memory proportional to the number of unique elements. This approach is intuitive and commonly used when you need frequency counting in array problems.
Approach 2: XOR Operation (O(n) time, O(1) space)
The optimal solution relies on properties of the XOR bitwise operator. XOR of a number with itself is 0, and XOR of a number with 0 is the number itself. Also, XOR is commutative and associative, meaning order does not matter. Iterate through the array and XOR every element into a running variable. All duplicate numbers cancel each other out because a ^ a = 0. After processing the entire array, only the unique element remains in the accumulator. This approach uses constant extra space and a single pass through the array.
The key insight is recognizing that pairwise duplicates can eliminate themselves using bitwise operations. This pattern appears frequently in bit manipulation problems where duplicates occur in predictable counts.
Recommended for interviews: The XOR approach is what most interviewers expect. It demonstrates understanding of bitwise properties and achieves the optimal O(n) time with O(1) extra space. The hash map approach still shows correct reasoning and is often the first step many candidates describe before optimizing. Showing both approaches communicates problem‑solving progression and awareness of trade‑offs.
This approach leverages the properties of XOR bitwise operation. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. Thus, XORing all elements in the array results in getting the single number because all other numbers cancel themselves out.
The function singleNumber iterates over the array and continuously performs an XOR operation. By the end of the loop, all pairs will cancel out, leaving the single number as the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - We go through the array once.
Space Complexity: O(1) - We only use a single integer to store the result.
In this approach, we use a hash map (or dictionary) to count occurrences of each number. The single number will have a count of 1. This isn't the optimal solution in terms of extra space but is valid if space was not constrained.
This C solution uses an array to simulate a hash map, where each index corresponds to a potential value of nums[i]. It maps numbers from -30000 to +30000 to indices 0 to 60000 to handle negative numbers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - We traverse the array twice (once for filling the map, once for checking the counts).
Space Complexity: O(n) - Extra space proportional to the input range.
| Approach | Complexity |
|---|---|
| Approach 1: XOR Operation | Time Complexity: O(n) - We go through the array once. |
| Approach 2: Hash Map | Time Complexity: O(n) - We traverse the array twice (once for filling the map, once for checking the counts). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Frequency Count | O(n) | O(n) | Good first approach when counting occurrences or when the duplicate pattern is not guaranteed |
| XOR Bit Manipulation | O(n) | O(1) | Best choice for this problem when every element appears exactly twice except one |
Single Number - Leetcode 136 - Python • NeetCode • 117,983 views views
Watch 9 more video solutions →Practice Single Number with our built-in code editor and test cases.
Practice on FleetCode