Start learning free

LESSON 344 OF 344 · BIT MANIPULATION

Single Number in JavaScript: O(n log n) with Sorting

Practice O(n log n) Read the full explanation

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space.
(There are faster solutions which we will discuss in future lessons)

Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another.
Let's take an example:

nums = [2,1,3,1,3]
sortedNums = [1,1,2,3,3]

The single element is 2. What property does it satisfy that the other elements don't?

After sorting the array, the single element is the only one that is different than both its neighbors.
More exactly, in sorted nums, nums[i] is the single element if both these conditions hold true:

i == 0 or nums[i - 1] != nums[i]
i == n - 1 or nums[i + 1] != nums[i]

We sort the array, thus the Time Complexity is O(n log n).
We don't use any extra arrays, so the Extra Space used is O(1).

STEP 1 OF 13

Guided

Ctrl + Enter to check

JAVASCRIPT · BIT MANIPULATION

Single Number in JavaScript, explained

Problem overview

The method singleNumber receives a non-empty array of integers, nums, in which every value appears exactly twice except one. It returns that one value. The note asks for O(n log n) time and O(1) extra space, and says that faster solutions come in later lessons.

For [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4. For [1] it is 1, since the only element is the single one.

Approach: sort, then find the value with no equal neighbor

The brute-force way is to count, for each value, how many times it occurs, which takes O(n²) time. A hash map of counts brings it down to O(n) time, but it uses O(n) extra space, and the note asks for constant extra space.

Sorting gives another route. After sorting, equal values sit next to each other. The input [2, 1, 3, 1, 3] becomes [1, 1, 2, 3, 3]: the pairs are side by side, and the single value 2 is the only one that differs from both of its neighbors. A value at position i is the answer when:

it is the first element or differs from the element before it, and
it is the last element or differs from the element after it.

The sort costs O(n log n) and the scan afterwards costs O(n), so the total is O(n log n), which matches the note. This lesson pulls the neighbor test out into a helper method, isSingleNumber, so the main method stays short.

Step by step

Define the helper isSingleNumber(nums, index). It answers whether the value at index has no equal neighbor.
Check the left neighbor. If index > 0 and nums[index - 1] === nums[index], the value has a twin on its left. The index > 0 test comes first and guards the lookup: nums[-1] would not fail in JavaScript, it would just be undefined, but the guard makes the intent explicit.
Return false in that case, since a value with a twin cannot be the answer.
Check the right neighbor. If index < nums.length - 1 and nums[index] === nums[index + 1], the twin is on the right.
Return false in that case as well.
Return true at the end of the helper: neither neighbor matched.
In singleNumber, handle the one-element array. If nums.length === 1, that element is the answer. The general code would also handle it, but returning early is clearer.
Return nums[0] in that case.
Sort numerically. Call nums.sort((a, b) => a - b). The comparator is essential: the default sort compares values as strings.
Loop over every index with for (let i = 0; i < nums.length; i++). The loop variable is declared with let because it changes.
Test each position with this.isSingleNumber(nums, i). The helper returns a boolean, so the call can be the condition.
Return nums[i] for the first position that passes.
Return -1 after the loop. Valid input always contains a single value, so this line is only a fallback.

On [4, 1, 2, 1, 2], sorting gives [1, 1, 2, 2, 4]. Index 0 has an equal right neighbor, so it fails. Index 1 has an equal left neighbor. Index 2 has an equal right neighbor. Index 3 has an equal left neighbor. Index 4, the value 4, has a different left neighbor (2) and no right neighbor, so it passes and 4 is returned.

The solution in JavaScript

class Solution {
    isSingleNumber(nums, index) {
        if (index > 0 && nums[index - 1] === nums[index]) {
            return false;
        }
        if (index < nums.length - 1 && nums[index] === nums[index + 1]) {
            return false;
        }
        return true;
    }
    singleNumber(nums) {
        if (nums.length === 1) {
            return nums[0];
        }
        nums.sort((a, b) => a - b);
        for (let i = 0; i < nums.length; i++) {
            if (this.isSingleNumber(nums, i)) {
                return nums[i];
            }
        }
        return -1;
    }
}

JavaScript details worth knowing:

The default sort is textual. [10, 9, 1].sort() gives [1, 10, 9], because "10" comes before "9" as text. With negative numbers it is worse, since "-3" and "-10" compare as strings too. The comparator (a, b) => a - b returns a negative number when a belongs first, positive when b does, and zero for equal values, so the array ends up in numeric ascending order. For example [10, 9, 1, -2].sort((a, b) => a - b) gives [-2, 1, 9, 10].
Sorting changes the input. sort works in place and returns the same array. The caller's nums is reordered. If that matters, sort a copy made with [...nums], which costs O(n) extra space.
The space claim is approximate. The solution allocates no array of its own, but the engine's sort routine may use temporary memory internally, so "constant extra space" describes this code, not necessarily every engine's sort.
=== compares without conversion. For numbers it behaves as expected. Using == would also work here but allows surprising conversions with mixed types.
Short-circuit evaluation. In index > 0 && nums[index - 1] === nums[index], the right side runs only when the left is true, so the bounds test protects the array lookup.
Methods reach each other through this. The helper is called as this.isSingleNumber(...).

Complexity

Time: O(n log n). Sorting takes O(n log n) comparisons. The loop calls the helper at most n times, and each call does constant work, so the scan adds O(n). The sort dominates.

Space: O(1) extra in this code, as discussed above, because the sort is in place and the loop keeps only an index. A hash-based solution would trade O(n) space for O(n) time. There is also a bit-manipulation solution with O(n) time and O(1) space, which later lessons cover.

Edge cases and common mistakes

A single element. [1] returns 1 through the early return.
The answer at either end. In [1, 2, 2] the answer is the first element, which has no left neighbor. In [2, 2, 3] it is the last, which has no right neighbor. The two if tests in the helper handle both ends.
Negative numbers. [-3, 5, -3] returns 5. The numeric comparator sorts it to [-3, -3, 5].
Forgetting the comparator. A text sort can still put equal values next to each other, since equal numbers have equal text, so the answer often comes out right by accident. The numeric order is still the correct habit, and it matters for problems that depend on order.
Checking only one neighbor. Testing just the left side would accept the first element of every pair.
Out-of-range reads. Reading nums[i + 1] at the last index gives undefined, not an error, so a missing guard fails silently instead of crashing.

Testing

[2, 2, 1] gives 1.
[4, 1, 2, 1, 2] gives 4.
[1] gives 1.
[-3, 5, -3] gives 5.
[2, 2, 3] gives 3.

Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free