Find the unique number in linear time

You are fifteen minutes into a Cisco phone screen when the interviewer says, "I have an array where every number appears twice except one. Find the Single Number." It sounds straightforward, and the HashMap solution is exactly that, but this problem (also known as Single Number on other platforms) is a great litmus test for how cleanly you handle counting patterns and whether you can discuss trade-offs between space and cleverness.

TL;DR

Use a HashMap to count how many times each number appears. Iterate through the array once to build the frequency map, then scan the map for the key whose count is 1. This runs in O(n) time and O(n) space. If duplicates always appear exactly twice, mention the XOR trick as an O(1) space optimization.

Why This Problem Matters

Finding the unique element in an array is one of the first problems where you get to choose between multiple valid strategies: brute force nested loops, sorting, hash-based counting, or bit manipulation. The HashMap approach is the most generalizable and the one interviewers expect you to reach first. Once you are comfortable with it, the XOR optimization becomes a natural follow-up that shows deeper algorithmic thinking.

Understanding the Problem

Given an array of integers where every number except one appears at least twice, find and return the number that appears exactly once.

uniqueNumber([1,1,2,2,3,4,4,5,5]) -> 3
uniqueNumber([2,1,1,3,3])         -> 2
uniqueNumber([-1])                -> -1

Constraints:

• Array length: 1 to 10,000
• Values: -10^9 to 10^9
• The array is never empty
• Exactly one number appears only once

Edge Cases

1. Single element: The array contains only one number, which is the answer by definition
2. Negative numbers: The algorithm handles negatives the same as positives since HashMap keys can be any integer
3. Duplicates appearing more than twice: The counting approach still works correctly since we check for count equal to 1
4. Large values: No overflow concern since we are only counting, not summing

Solution Approach

The idea is simple: if we could count how many times each number appears, the one with a count of 1 is our answer. A HashMap gives us O(1) insertion and lookup, making this a single-pass counting problem.

Here is how it works for [2, 1, 1, 3, 3]:

Phase 1 - Count occurrences:

We walk through each element and update its count in the map. By the end, every number has an accurate frequency.

Phase 2 - Find the unique entry:

We scan the map and return the first key with a count of 1. In this case, 2 is the unique number.

Tracing a Second Example

For [1, 1, 5, 3, 3], the counting phase builds the full frequency map:

After counting, we scan the map: 1 has count 2 (skip), 5 has count 1 (return it). The answer is 5.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.HashMap;
import java.util.Map;

public class Solution {
  public int uniqueNumber(int[] arr) {
    Map<Integer, Integer> counts = new HashMap<>();

    for (int num : arr) {
      counts.put(num, counts.getOrDefault(num, 0) + 1);
    }

    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
      if (entry.getValue() == 1) {
        return entry.getKey();
      }
    }

    return -1;
  }
}

Let's walk through the code:

1. Create the frequency map: HashMap<Integer, Integer> maps each number to its occurrence count
2. Count occurrences: For each number, getOrDefault returns the current count (or 0 if not yet seen), then we increment it by 1
3. Find the unique number: Iterate through the map's entries and return the key whose value is 1
4. Fallback return: The -1 is a safety net that should never be reached given the problem constraints

Complexity Analysis

Time: O(n) where n is the array length. We make two passes: one over the array to count (O(n)), and one over the map to find the unique entry (at most O(n) since the map has at most n entries). HashMap operations are O(1) amortized, so the total is O(n).

Space: O(n) for the HashMap. In the worst case, the map stores (n/2 + 1) entries (when every pair has a distinct value plus the unique number). This grows linearly with n.

The XOR Alternative

If the problem guarantees that duplicates appear exactly twice, there is an elegant O(1) space trick: XOR all elements together.

int result = 0;
for (int num : arr) {
    result ^= num;
}
return result;

XOR has two properties that make this work:

• a ^ a = 0 (any number XOR itself is 0)
• a ^ 0 = a (any number XOR 0 is itself)

So for [2, 1, 1, 3, 3]: 2 ^ 1 ^ 1 ^ 3 ^ 3 = 2 ^ 0 ^ 0 = 2.

This is brilliant but fragile. If duplicates can appear three or more times, XOR breaks. The HashMap approach is more robust, and in an interview, showing both earns you points for versatility.

Common Pitfalls

1. Using nested loops: Checking each element against every other element gives O(n^2) time. Interviewers expect O(n).

2. Sorting first: Sorting and scanning adjacent elements works in O(n log n) time but the problem asks for linear time.

3. Forgetting getOrDefault: Without a default value, the first occurrence of a number would throw a NullPointerException when you try to increment null.

   // Wrong - throws NullPointerException on first occurrence
   counts.put(num, counts.get(num) + 1);
   // Correct
   counts.put(num, counts.getOrDefault(num, 0) + 1);
   

4. Returning the count instead of the key: A common slip is returning entry.getValue() (the count) instead of entry.getKey() (the number).

Interview Tips

When presenting this solution:

• Start by confirming constraints: "Are duplicates always exactly two, or could they appear more times?"
• Present the HashMap approach first. It is the safe, general solution.
• After explaining it, mention XOR as an optimization if duplicates are strictly pairs. This shows depth.
• Note the trade-off: HashMap uses O(n) space but handles all cases; XOR uses O(1) space but only works for pairs.
• If the interviewer pushes for O(1) space, pivot to XOR and explain why it works using the two XOR properties.

Key Takeaways

• A HashMap counting pattern solves this in O(n) time and O(n) space by tallying occurrences, then finding the element with count 1.
• The getOrDefault method (Java) or equivalent in other languages prevents null/missing-key errors when building the frequency map.
• The XOR trick (a ^ a = 0 and a ^ 0 = a) reduces space to O(1) when every duplicate appears exactly twice, but breaks for higher multiplicities.
• Always present the general solution first in interviews, then optimize. Jumping straight to XOR without explaining the HashMap approach can look like you memorized a trick without understanding the problem.
• This counting pattern is foundational. It reappears in anagram grouping, frequency-based sorting, top-K problems, and many other interview questions.

Practice and Related Problems

Once you are comfortable with finding the unique number, try these progressions:

• Group anagrams (HashMap with sorted-key counting)
• Top K frequent elements (HashMap + heap)
• First unique character in a string (same counting pattern)
• Single Number II (every element appears three times except one)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

class Solution:
    def unique_number(self, arr):
        counts = {}

        for num in arr:
            counts[num] = counts.get(num, 0) + 1

        for num, count in counts.items():
            if count == 1:
                return num

        return -1

JavaScript

class Solution {
  uniqueNumber(arr) {
    const counts = new Map();

    for (const num of arr) {
      counts.set(num, (counts.get(num) || 0) + 1);
    }

    for (const [num, count] of counts) {
      if (count === 1) {
        return num;
      }
    }

    return -1;
  }
}

TypeScript

class Solution {
  uniqueNumber(arr: number[]): number {
    const counts = new Map<number, number>();

    for (const num of arr) {
      counts.set(num, (counts.get(num) ?? 0) + 1);
    }

    for (const [num, count] of counts) {
      if (count === 1) {
        return num;
      }
    }

    return -1;
  }
}

C++

#include <unordered_map>

class Solution {
public:
  int uniqueNumber(std::vector<int> arr) {
    std::unordered_map<int, int> counts;

    for (auto num : arr) {
      counts[num]++;
    }

    for (const auto &[num, count] : counts) {
      if (count == 1) {
        return num;
      }
    }

    return -1;
  }
};

Go

package solution

func (s *Solution) UniqueNumber(arr []int) int {
    counts := map[int]int{}

    for _, num := range arr {
        counts[num]++
    }

    for num, count := range counts {
        if count == 1 {
            return num
        }
    }

    return -1
}

Scala

import scala.collection.mutable

class Solution {
  def uniqueNumber(arr: Array[Int]): Int = {
    val counts = mutable.Map[Int, Int]()

    arr.foreach { num =>
      counts(num) = counts.getOrElse(num, 0) + 1
    }

    counts.find { case (num, count) => count == 1 } match {
      case Some((num, _)) => num
      case None => -1
    }
  }
}

Kotlin

class Solution {
    fun uniqueNumber(arr: IntArray): Int {
        val counts = mutableMapOf<Int, Int>()

        for (num in arr) {
            counts[num] = counts.getOrDefault(num, 0) + 1
        }

        for ((num, count) in counts) {
            if (count == 1) {
                return num
            }
        }

        return -1
    }
}

Swift

import Foundation

class Solution {
    func uniqueNumber(_ arr: [Int]) -> Int {
        var counts = [Int: Int]()

        for num in arr {
            counts[num, default: 0] += 1
        }

        for (num, count) in counts {
            if count == 1 {
                return num
            }
        }

        return -1
    }
}

Rust

impl Solution {
    pub fn unique_number(&self, arr: Vec<i32>) -> i32 {
        let mut counts: HashMap<i32, i32> = HashMap::new();

        for &num in &arr {
            *counts.entry(num).or_insert(0) += 1;
        }

        for (&key, &value) in &counts {
            if value == 1 {
                return key;
            }
        }

        -1
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public int uniqueNumber(int[] arr) {
        var counts = new Dictionary<int, int>();

        foreach (int num in arr) {
            counts[num] = counts.GetValueOrDefault(num, 0) + 1;
        }

        foreach (var entry in counts) {
            if (entry.Value == 1) {
                return entry.Key;
            }
        }

        return -1;
    }
}

Dart

class Solution {
  int uniqueNumber(List<int> arr) {
    Map<int, int> counts = {};

    for (int num in arr) {
      counts[num] = (counts[num] ?? 0) + 1;
    }

    for (var entry in counts.entries) {
      if (entry.value == 1) {
        return entry.key;
      }
    }

    return -1;
  }
}

PHP

class Solution {
    public function uniqueNumber(array $arr): int {
        $counts = [];

        foreach ($arr as $num) {
            $counts[$num] = ($counts[$num] ?? 0) + 1;
        }

        foreach ($counts as $num => $count) {
            if ($count === 1) {
                return $num;
            }
        }

        return -1;
    }
}

Ruby

class Solution
  def unique_number(arr)
    counts = {}

    arr.each do |num|
      counts[num] = (counts[num] || 0) + 1
    end

    counts.each do |key, value|
      return key if value == 1
    end

    -1
  end
end