Start learning free

LESSON 344 OF 344 · BIT MANIPULATION

Single Number in Python: 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

    PYTHON · BIT MANIPULATION

    Single Number in Python, explained

    Problem overview

    The method singleNumber receives a non-empty list nums of integers. Every value appears exactly twice, except one value that appears once. The method returns that single value. The lesson asks for O(n log n) time and O(1) extra space.

    In the second example, nums = [4, 1, 2, 1, 2]. The values 1 and 2 each appear twice, so the answer is 4. In the third example, nums = [1], the only element is the single one, so the answer is 1.

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

    The quickest idea to write is to count each value with a dictionary and return the one with count 1. That takes O(n) extra space, which the lesson wants to avoid, and the same space limit rules out a set of seen values.

    Sorting solves it without a separate structure. After sorting in ascending order, equal values sit next to each other. For [2, 1, 3, 1, 3] the sorted list is [1, 1, 2, 3, 3]. Each pair is a block of two equal neighbors, and the single value is the only element that is different from both of its neighbors.

    Edges of the list need care. The first element has no left neighbor, and the last one has no right neighbor. An element is the single one when each neighbor that exists is different from it.

    The lesson splits the work in two. A helper, isSingleNumber, tests one index. The main method sorts the list and checks each index in turn. (Faster methods exist, such as XOR-ing all the values together, but this lesson practises sorting.)

    Step by step

    1. Define the helper isSingleNumber(self, nums, index) to answer: does the value at this index have no equal neighbor?
    2. Check the left neighbor. If index > 0 and nums[index - 1] equals nums[index], the value is part of a pair.
    3. Return False in that case.
    4. Check the right neighbor. If index < len(nums) - 1 and nums[index] equals nums[index + 1], there is a pair as well.
    5. Return False in that case too.
    6. Return True at the end of the helper: no neighbor matched.
    7. In singleNumber, handle a one-element list first. If len(nums) == 1, that element is the answer.
    8. Return nums[0] for that case.
    9. Sort nums in place with nums.sort(), so equal values become adjacent.
    10. Loop over every index with for i in range(0, len(nums)).
    11. Ask the helper about each index with self.isSingleNumber(nums, i).
    12. Return nums[i] for the first index that passes.
    13. Return -1 after the loop. The input always has a single number, so this line is only a fallback.

    The solution in Python

    class Solution:
    def isSingleNumber(self, nums, index):
        if index > 0 and nums[index - 1] == nums[index]:
            return False
        if index < len(nums) - 1 and nums[index] == nums[index + 1]:
            return False
        return True

    def singleNumber(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        nums.sort()
        for i in range(0, len(nums)):
            if self.isSingleNumber(nums, i):
                return nums[i]
        return -1

    The Python details worth a closer look:

    • The guard index > 0 matters. In Python, a negative index counts from the end, so nums[-1] is the last element and doesn't raise an error. Without the guard, index 0 would be compared with the last element of the list, which gives wrong answers.
    • The right guard avoids an IndexError. Reading nums[len(nums)] is out of range. The condition index < len(nums) - 1 is checked first, and and stops evaluating as soon as it is false, so the out-of-range access never happens.
    • sort() against sorted(). nums.sort() sorts the list in place and returns None. sorted(nums) returns a new sorted list and leaves nums alone. Writing nums = nums.sort() would replace the list with None.
    • The caller's list is reordered. Because the sort is in place, the list that was passed in comes back sorted. That's acceptable here, but copy the list first if the original order matters.
    • The helper is a method. It takes self and is called as self.isSingleNumber(...).
    • Comparing integers. == compares values, which is what is needed. Python integers don't overflow, whatever their size.

    Complexity

    Time: O(n log n). Sorting costs O(n log n). The loop then makes one pass, and each call to the helper does a constant amount of work, so the pass costs O(n). The sort dominates.

    Space: O(1) beyond the sort. The code creates no extra list, set or dictionary. In practice, Python's sort may use a temporary buffer of up to about n / 2 items while it merges, so the space is exactly O(1) only if you count the sort as in place.

    Edge cases and common mistakes

    • One element. [1] returns 1 right away. The helper would handle this case too, but the early return skips the sort and the loop.
    • The single value is the smallest or the largest. For [2, 2, 1], the sorted list is [1, 2, 2] and the answer is at index 0. For [5, 3, 3] it is at the last index. The guards in the helper make both work.
    • Negative numbers. [-1, -1, -2] returns -2. Sorting handles negatives like any other integers.
    • Comparing only one neighbor. Checking just the left neighbor would wrongly return the first element of the first pair. In [1, 1, 2], index 0 has no left neighbor, but its right neighbor is equal.
    • Missing the guards. Without index > 0, index 0 is compared with nums[-1]. Without the right guard, the last index raises an IndexError.
    • Returning the index. The method returns the value nums[i], not the position i.
    • Sorting without saving the result. sorted(nums) on its own line does nothing useful, because the result is discarded.

    Testing

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