Scale Engineer

Single Number III

Med
#0248Time: O(n) where n is the length of the input arraySpace: O(n) to store the HashMap
Patterns
Bit Manipulation
Data structures
Array

Prompt

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 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

Approaches

2 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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

Time

O(n) where n is the length of the input array

Space

O(n) to store the HashMap

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem