136. Single Number (Easy)

Problem

Given a non-empty array of integers nums where every element appears twice except for one, find that single one. Solve in $O(n)$ time and $O(1)$ extra space.

Example

nums = [2, 2, 1] → 1
nums = [4, 1, 2, 1, 2] → 4
nums = [1] → 1

LeetCode 136 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Hash set

Track elements; add on first sight, remove on second. The remainder is the answer.

def single_number(nums):
    seen = set()                            # L1: O(1)
    for x in nums:                          # L2: single pass, n iterations
        if x in seen:
            seen.remove(x)                  # L3: O(1) amortized
        else:
            seen.add(x)                     # L4: O(1) amortized
    return seen.pop()                       # L5: O(1)

function singleNumber(nums: number[]): number {
    const seen = new Set<number>();          // L1: O(1)
    for (const x of nums) {                 // L2: single pass, n iterations
        if (seen.has(x)) seen.delete(x);    // L3: O(1) amortized
        else seen.add(x);                   // L4: O(1) amortized
    }
    return seen.values().next().value;      // L5: O(1)
}

func singleNumber(nums []int) int {
    seen := make(map[int]bool)              // L1: O(1)
    for _, x := range nums {               // L2: single pass, n iterations
        if seen[x] {
            delete(seen, x)                // L3: O(1) amortized
        } else {
            seen[x] = true                 // L4: O(1) amortized
        }
    }
    for k := range seen {                  // L5: O(1), only one key remains
        return k
    }
    return 0
}

final class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var unmatched = Set<Int>()
        for value in nums {
            if unmatched.remove(value) == nil {
                unmatched.insert(value)
            }
        }
        return unmatched.first ?? 0
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2-L4 (scan)	$O(1)$	n	$O(n)$ ← dominates
L5 (pop)	$O(1)$	1	$O(1)$

Complexity

Time: $O(n)$ , driven by L2/L3/L4 (single pass over all elements).
Space: $O(n)$ for the set.

Violates the $O(1)$ space constraint.

Approach 2: Sort + scan pairs

Sort; any non-pair is the answer.

def single_number(nums):
    nums.sort()                             # L1: O(n log n)
    for i in range(0, len(nums) - 1, 2):   # L2: scan in steps of 2
        if nums[i] != nums[i + 1]:         # L3: O(1)
            return nums[i]
    return nums[-1]                         # L4: last element is single

function singleNumber(nums: number[]): number {
    nums.sort((a, b) => a - b);                 // L1: O(n log n)
    for (let i = 0; i < nums.length - 1; i += 2) {  // L2: scan in steps of 2
        if (nums[i] !== nums[i + 1]) return nums[i]; // L3: O(1)
    }
    return nums[nums.length - 1];               // L4: last element is single
}

import "sort"

func singleNumber(nums []int) int {
    sort.Ints(nums)                             // L1: O(n log n)
    for i := 0; i < len(nums)-1; i += 2 {      // L2: scan in steps of 2
        if nums[i] != nums[i+1] {              // L3: O(1)
            return nums[i]
        }
    }
    return nums[len(nums)-1]                    // L4: last element is single
}

final class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        let sorted = nums.sorted()
        var index = 0
        while index + 1 < sorted.count {
            if sorted[index] != sorted[index + 1] {
                return sorted[index]
            }
            index += 2
        }
        return sorted.last ?? 0
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2-L3 (pair scan)	$O(1)$	n/2	$O(n)$

Complexity

Time: $O(n log n)$ , driven by L1 (sorting).
Space: $O(1)$ with in-place sort.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: XOR everything (optimal)

a ^ a = 0 and a ^ 0 = a. XOR all elements; duplicates cancel, leaving the unique.

def single_number(nums):
    result = 0                              # L1: O(1)
    for x in nums:                          # L2: single pass, n iterations
        result ^= x                         # L3: O(1), XOR accumulate
    return result

# Or:
# from functools import reduce
# from operator import xor
# return reduce(xor, nums)

function singleNumber(nums: number[]): number {
    let result = 0;                         // L1: O(1)
    for (const x of nums) {                // L2: single pass, n iterations
        result ^= x;                        // L3: O(1), XOR accumulate
    }
    return result;
}

func singleNumber(nums []int) int {
    result := 0                             // L1: O(1)
    for _, x := range nums {               // L2: single pass, n iterations
        result ^= x                         // L3: O(1), XOR accumulate
    }
    return result
}

final class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        nums.reduce(0, ^)
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2, L3 (XOR loop)	$O(1)$	n	$O(n)$ ← dominates

A single pass; each element is XORed in once.

Complexity

Time: $O(n)$ , driven by L2/L3 (single XOR pass).
Space: $O(1)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

Swift arrays have value semantics with copy-on-write storage. Calling sorted() creates a sorted value and leaves the caller’s array unchanged, but it still needs $O(n)$ extra storage in this implementation. Set also allocates proportional storage. XOR keeps one Int accumulator and preserves negative bit patterns.

Summary

Approach	Time	Space
Hash set	$O(n)$	$O(n)$
Sort + scan	$O(n log n)$	$O(1)$
XOR	$O(n)$	$O(1)$

XOR is the canonical bit-manipulation move, memorize it. Variants (Single Number II with triples, III with two singletons) build on this.

Test cases

# Quick smoke tests, paste into a REPL or save as test_136.py and run.
# Uses the canonical implementation (Approach 3: XOR).

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result

def _run_tests():
    assert single_number([2, 2, 1]) == 1
    assert single_number([4, 1, 2, 1, 2]) == 4
    assert single_number([1]) == 1                      # single element edge case
    assert single_number([0, 0, 99]) == 99              # zero appears twice
    assert single_number([-1, -1, 42]) == 42            # negative numbers
    assert single_number([2**31 - 1]) == 2**31 - 1      # max int, single element
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function singleNumber(nums: number[]): number {
    let result = 0;
    for (const x of nums) result ^= x;
    return result;
}

console.assert(singleNumber([2, 2, 1]) === 1);
console.assert(singleNumber([4, 1, 2, 1, 2]) === 4);
console.assert(singleNumber([1]) === 1);
console.assert(singleNumber([0, 0, 99]) === 99);
console.assert(singleNumber([-1, -1, 42]) === 42);
console.assert(singleNumber([2 ** 31 - 1]) === 2 ** 31 - 1);
console.log("all tests pass");

func singleNumber(nums []int) int {
    result := 0
    for _, x := range nums {
        result ^= x
    }
    return result
}

Arrays, input; XOR accumulator (no extra structures)

Bit Manipulation, the binary representation pattern for masks, toggles, shifts, and arithmetic shortcuts.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

136. Single Number (Easy)

Problem

Try it yourself

Approach 1: Hash set

Approach 2: Sort + scan pairs

Approach 3: XOR everything (optimal)

Swift notes

Summary

Test cases

Related data structures

Related concepts