Skip to main content

12. Single Number

easyAsked at Figma

Find the element that appears once in an array where every other element appears twice. Figma probes whether you reach for XOR or default to a hash map.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a non-empty array where every element appears twice except for one, find the single element. Your solution should run in linear time and use constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Exactly one element appears once; all others appear twice

Examples

Example 1

Input
nums = [2,2,1]
Output
1

Example 2

Input
nums = [4,1,2,1,2]
Output
4

Approaches

1. Hash map of counts

Count occurrences, return the key with count 1.

Time
O(n)
Space
O(n)
function singleNumber(nums) {
  const c = new Map();
  for (const x of nums) c.set(x, (c.get(x) || 0) + 1);
  for (const [k, v] of c) if (v === 1) return k;
}

Tradeoff:

2. XOR fold

XOR is commutative and self-inverse, so duplicates cancel and only the unique value remains. Constant space, single pass.

Time
O(n)
Space
O(1)
function singleNumber(nums) {
  let result = 0;
  for (const x of nums) {
    result ^= x;
  }
  return result;
}

Tradeoff:

Figma-specific tips

Figma's bar is the O(1)-space XOR insight; talk through the algebraic properties (commutativity, self-inverse) rather than just writing the loop.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Single Number and other Figma interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →