Single Number III

MEDIUM

Description

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

2 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each integer in nums will appear twice, only two integers will appear once.

Approaches

Checkout 2 different approaches to solve Single Number III. Click on different approaches to view the approach and algorithm in detail.

Using HashMap

Use a HashMap to store the frequency of each number in the array. Then iterate through the HashMap to find the two numbers with frequency 1.

Algorithm

Create a HashMap to store number-frequency pairs
Iterate through the array and count frequency of each number
Iterate through the HashMap
Find numbers with frequency 1 and add them to result array
Return the result array

This approach uses a HashMap to keep track of the frequency of each number in the array. We first iterate through the array and store the count of each number in the HashMap. Then, we iterate through the HashMap to find the two numbers that appear only once (frequency = 1).

public int[] singleNumber(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    
    // Count frequency of each number
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    
    int[] result = new int[2];
    int index = 0;
    
    // Find numbers with frequency 1
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            result[index++] = entry.getKey();
        }
    }
    
    return result;
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the input arraySpace Complexity: O(n) to store the HashMap

Pros and Cons

Pros:

Easy to understand and implement
Works for any range of numbers

Cons:

Does not meet the constant space requirement
Requires extra space proportional to input size

Code Solutions

Checking out 5 solutions in different languages for Single Number III. Click on different languages to view the code.

public class Solution {
    public int[] SingleNumber(int[] nums) {
        int xs = nums.Aggregate(0, (a, b) => a ^ b);
        int lb = xs & -xs;
        int a = 0;
        foreach(int x in nums) {
            if ((x & lb) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {
            a,
            b
        };
    }
}

Video Solution

Watch the video walkthrough for Single Number III

Patterns:

Bit Manipulation

Data Structures:

Array