Single Number - Solution & Explanation
Problem Statement
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 * 104- Each element in the array appears twice except for one element which appears only once.
Approach Overview
Problem Overview: You receive an integer array where every element appears exactly twice except for one element that appears only once. The task is to find that single element. The solution must work efficiently even when the array grows large.
Approach 1: Hash Map Counting (O(n) time, O(n) space)
This approach uses a frequency map to count how many times each number appears. Iterate through the array and store counts using a hash map where the key is the number and the value is its frequency. After building the map, scan through the entries and return the number with frequency 1. The logic is straightforward and easy to implement, which makes it a good baseline approach when you first reason about the problem. However, it requires extra memory proportional to the number of unique elements.
This technique relies on constant-time hash lookups and works well for many array counting problems. The tradeoff is memory usage since the hash map stores up to n keys.
Approach 2: XOR Operation (O(n) time, O(1) space)
The optimal solution uses properties of the XOR bitwise operator. XOR has two useful rules: a ^ a = 0 and a ^ 0 = a. When you XOR all numbers in the array together, duplicate numbers cancel each other out because each pair produces zero. The only value left after the full pass is the number that appears once.
Implementation is simple: initialize a variable result = 0, iterate through the array, and update result ^= num for each element. After processing the entire array, result holds the unique element. The algorithm performs a single pass and uses only one variable for storage, giving constant extra space.
This approach is a classic example of using bit manipulation to reduce memory usage. It avoids auxiliary data structures while maintaining linear runtime, which makes it both elegant and efficient.
Recommended for interviews: Interviewers usually expect the XOR solution. Starting with the hash map approach demonstrates you understand the problem using counting and hash lookups. Moving to the XOR technique shows deeper algorithmic thinking and familiarity with bitwise operations. The XOR solution achieves the optimal O(n) time and O(1) space, which is the key improvement interviewers look for.
Approach 1: Approach 1: XOR Operation
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.
Complexity
Time Complexity: O(n) - We go through the array once.
Space Complexity: O(1) - We only use a single integer to store the result.
Approach 2: Approach 2: Hash Map
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.
Complexity
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 3: Bitwise Operation
The XOR operation has the following properties:
- Any number XOR 0 is still the original number, i.e.,
x \oplus 0 = x; - Any number XOR itself is 0, i.e.,
x \oplus x = 0;
Performing XOR operation on all elements in the array will result in the number that only appears once.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
C
Swift
Approach 4: Default Approach
Code
Java
Complexity Comparison
| 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). |
| Bitwise Operation | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Counting | O(n) | O(n) | When simplicity and clarity matter more than memory usage |
| XOR Bit Manipulation | O(n) | O(1) | Best general solution when duplicates appear exactly twice |
Video Solution
Single Number - Leetcode 136 - Python • NeetCode • 148,005 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Single Number easy or hard?
Single Number Python/Java solution
How to solve Single Number in O(n)?
What is the best approach for Single Number?
Is Single Number asked at Google/Amazon/Meta?
What data structure is used in Single Number?
What is the time complexity of Single Number?
Ready to solve this problem?
Practice Single Number with our built-in code editor and test cases.
Practice on FleetCode