136. Single Number - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

Given a non-empty array of integers, every element appears twice except for one. Find that single element.

Note:
Your algorithm should have a linear runtime complexity and use constant extra space.

Example 1:
- Input: [2, 2, 1]
- Output: 1
- Explanation:
  The number 1 appears only once, whereas 2 appears twice.
Example 2:
- Input: [4, 1, 2, 1, 2]
- Output: 4
- Explanation:
  The number 4 is the only element that appears once while the others appear twice.

Hash Table Approach:
- You can count the frequency of each element using a hash table and then identify the one with a count of 1.
XOR Approach:
- Consider using the bitwise XOR operator.
- Properties of XOR:
  - a ^ a = 0
  - 0 ^ a = a
- When you XOR all elements together, pairs cancel each other out, leaving only the single element.

Traverse the array and use a dictionary (or hash map) to count the occurrences of each element.
Iterate through the hash map to find the element with a count of 1.
Time Complexity: O(n)
Space Complexity: O(n) in the worst case.

Python3

. . . .

Java

. . . .

Initialize a variable result with 0.
Iterate through each number in the array and perform the XOR operation with result:
- result ^= num
The XOR operation cancels out duplicate numbers (because a ^ a = 0), leaving the unique number.
Time Complexity: O(n)
Space Complexity: O(1)

Python3

. . . .

Java

. . . .

Brute Force (Hash Table):
- Time Complexity: O(n)
- Space Complexity: O(n)
Optimal (XOR):
- Time Complexity: O(n)
- Space Complexity: O(1)

Single Element Array:
- Example: [x] should return x.
Array with Negative Numbers:
- The XOR approach works correctly with negative numbers as well.
Large Arrays:
- Ensure the algorithm can handle arrays of maximum allowed size efficiently.

Using Extra Space Unnecessarily:
- While the hash table approach is valid, it does not meet the optimal space requirement.
Incorrect XOR Initialization:
- Forgetting to initialize the result to 0 or misusing XOR operations can lead to errors.
Overlooking Edge Cases:
- Ensure that the solution handles cases such as a single-element array or arrays with negative numbers.

Single Number II (LeetCode 137):
- Every element appears three times except for one. A different bit manipulation approach is needed.
Single Number III (LeetCode 260):
- Two numbers appear once while all others appear twice. The problem requires finding the two unique numbers.