Start learning free

LESSON 343 OF 343 · BIT MANIPULATION

Single Number in C++: 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 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 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
    Ctrl + Enter to check

    C++ · BIT MANIPULATION

    Single Number in C++, explained

    Problem overview

    The method singleNumber receives a non-empty vector of integers, nums, in which every value appears exactly twice except one value, which appears once. It returns that single value. For [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4, and for [1] it is 1.

    The statement asks for O(n log n) time and O(1) extra space. The lesson says that faster solutions exist and come later, so the goal here is a clean approach built on sorting.

    Approach: sort, then look for the number without a twin

    Without any structure, finding the odd one out means comparing each value against all the others, which costs O(n²). Sorting removes that work. After sorting, equal values sit next to each other, so a value's twin can only be its left or right neighbour.

    Take [4, 1, 2, 1, 2]. Sorted, it is [1, 1, 2, 2, 4]. The 1s are side by side, so are the 2s, and the 4 has a different value on its left and nothing on its right. The single number is the one element that matches neither neighbour.

    That gives a test for position i: it holds the single number if

    • i is 0 or nums[i - 1] differs from nums[i], and
    • i is the last position or nums[i + 1] differs from nums[i].

    Sorting costs O(n log n), and the scan afterwards is O(n), so the sort is the expensive step.

    Step by step

    1. Write a helper bool isSingleNumber(vector<int>& nums, int index) that reports whether the value at index has no equal neighbour.
    2. Check the left neighbour. The condition is index > 0 && nums[index - 1] == nums[index]. The index > 0 part comes first so the code never reads before the start of the vector. In &&, the right side runs only if the left side is true.
    3. Return false in that case: an equal left neighbour means the value has its twin.
    4. Check the right neighbour with index < (int)nums.size() - 1 && nums[index] == nums[index + 1]. The cast matters, as explained below.
    5. Return false again for an equal right neighbour.
    6. Return true at the end of the helper: neither neighbour matched.
    7. Handle a one-element vector in singleNumber with an early check on nums.size() == 1. The helper would also give the right answer here, but the shortcut skips the sort and the loop.
    8. Return nums[0] in that case.
    9. Sort the vector with sort(nums.begin(), nums.end()), so twins become adjacent.
    10. Loop over every index i.
    11. Ask the helper about each position: if (isSingleNumber(nums, i)).
    12. Return nums[i] when it says yes.
    13. Return -1 after the loop. The lesson guarantees a single number exists, so this line is a fallback that never runs on valid input.

    The solution in C++

    class Solution {
public:
    bool isSingleNumber(vector<int>& nums, int index) {
        if (index > 0 && nums[index - 1] == nums[index]) {
            return false;
        }
        if (index < (int)nums.size() - 1 && nums[index] == nums[index + 1]) {
            return false;
        }
        return true;
    }
    int singleNumber(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (isSingleNumber(nums, i)) {
                return nums[i];
            }
        }
        return -1;
    }
};

    C++ details that matter here:

    • Unsigned size(). nums.size() returns an unsigned type. Computing nums.size() - 1 on an empty vector wraps around to a huge number instead of -1. Casting first, (int)nums.size() - 1, keeps the arithmetic signed, so the comparison with the signed index behaves as it reads. Without the cast, index would also be converted to unsigned for the comparison. A helper can't be sure its caller never passes an empty vector, so the cast is a good habit.
    • Out-of-range reads. nums[-1] or nums[nums.size()] on a vector is undefined behaviour. The compiler does not stop you, and the program may seem to work or may crash. The bounds tests that come before the comparisons are what keep the reads valid.
    • Short-circuit evaluation. a && b evaluates b only when a is true. That is why index > 0 && nums[index - 1] == nums[index] is safe at index 0.
    • Sorting in place. sort comes from <algorithm>, takes a pair of iterators, and reorders the caller's vector, because nums is passed by reference. If the caller needs the original order, sort a copy instead. The statement's O(1) extra space refers to the algorithm's own extra memory, and in-place sorting keeps to it.
    • Signed and unsigned loop bound. In i < nums.size(), the int i is converted to unsigned for the comparison. That's fine here since i is never negative, though some compilers warn about it.

    Complexity

    Time: O(n log n). Sorting dominates. The scan calls the helper for each index, and each call does constant work.

    Space: O(1) extra, apart from the small working memory of the sort. No additional array or map is built.

    Edge cases and common mistakes

    • One element. [1] returns 1, through the early return.
    • The single number at either end. In [4, 1, 1], sorted to [1, 1, 4], the 4 is last, and its right-neighbour check is skipped because there is no right neighbour. In [1, 2, 2] the 1 is first, and the left check is skipped.
    • Negative values. They sort like any other integer. For [-3, 5, -3] the answer is 5.
    • Checking only one side. Looking only at the left neighbour would report the first element of every pair, since the first of a pair has a different left neighbour. Both sides are required.
    • Skipping the sort. On an unsorted vector, neighbours say nothing about twins, so the test gives wrong answers.
    • Reading past the end. Removing the bounds tests is undefined behaviour in C++, even if it seems to work on your machine.

    Testing

    • [2, 2, 1] gives 1.
    • [4, 1, 2, 1, 2] gives 4.
    • [1] gives 1.
    • [-3, 5, -3] gives 5.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free