Start learning free

LESSON 348 OF 348 · BIT MANIPULATION

Single Number in TypeScript: O(n log n) by 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

    TYPESCRIPT · BIT MANIPULATION

    Single Number in TypeScript, explained

    Problem overview

    The method singleNumber receives a non-empty array nums of integers in which every value appears twice except one. It returns that one 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 allows O(n log n) time and O(1) extra space. It also says faster solutions exist and will come in later lessons, so this lesson solves the problem with sorting.

    Approach: sort, then look for the value with no equal neighbour

    The direct way to count how often a value appears is to compare it with every other element, which costs O(n²). A hash map of counts is faster, but it needs O(n) extra space. Sorting gets between the two: it costs O(n log n) and uses no extra array of our own.

    After sorting, equal values sit next to each other. Take [2, 1, 3, 1, 3], which sorts to [1, 1, 2, 3, 3]. Every value that appears twice has an equal neighbour, either on its left or on its right. The single value has no equal neighbour on either side. So the scan checks each position: is the left neighbour different (or missing, at index 0), and is the right neighbour different (or missing, at the last index)? The first position where both answers are yes holds the answer.

    Step by step

    1. Write the helper isSingleNumber(nums, index), which returns a boolean: does the value at index lack a matching neighbour?
    2. Check the left side. If index > 0 and nums[index - 1] === nums[index], return false. The value has a pair on its left. The guard index > 0 comes first, so the code never reads before the start of the array.
    3. Check the right side. If index < nums.length - 1 and nums[index] === nums[index + 1], return false. The guard avoids reading past the end.
    4. Return true at the end of the helper: neither neighbour matched.
    5. Handle a one-element array in singleNumber: if nums.length === 1, return nums[0]. The helper would also work here, but the early return skips the sort and the loop.
    6. Sort numerically. Call nums.sort((a, b) => a - b). Pass the comparator so the order is numeric: without it, sort compares the values as strings.
    7. Scan every index i with a for loop. When this.isSingleNumber(nums, i) is true, return nums[i].
    8. Return -1 after the loop. The input always contains a single value, so this line is only a fallback.

    The solution in TypeScript

    class Solution {
    isSingleNumber(nums: number[], index: number): boolean {
        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: number[]): number {
        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;
    }
}

    TypeScript details worth knowing:

    • The default sort compares strings. [10, 9, 1, -2].sort() gives [-2, 1, 10, 9], because "10" comes before "9" as text. With the comparator (a, b) => a - b the result is [-2, 1, 9, 10]. A negative result from the comparator puts a first, a positive one puts b first. The compiler accepts nums.sort() without a comparator, so nothing warns you about the mistake.
    • sort changes the array and returns it. It sorts nums in place, and the return value is the same array, so the code needs no assignment. The caller's array is left sorted, which matters if the caller needs the original order. Copy first with [...nums].sort(...) in that case, at the price of O(n) extra space.
    • Reading outside an array. TypeScript does not throw for it: nums[-1] and nums[nums.length] are both undefined. The guards in the helper still matter for clarity, and they keep the logic correct even if a value were missing.
    • Strict equality. === compares numbers without converting types. Plain numbers are fine here: the constraint keeps values within about 30,000 in size, far from the point where doubles lose integer precision.
    • Types are erased. number[], boolean and number are checked by the compiler and vanish from the JavaScript it produces.

    Complexity

    Time: O(n log n). Sorting dominates. The scan afterwards visits each index once and does constant work per index, so it adds O(n).

    Space: O(1) extra, as far as this code goes. It creates no arrays of its own and changes the input in place. The engine's sort may use some temporary memory inside, which the statement's count does not include.

    Edge cases and common mistakes

    • One element. [1] returns 1 immediately.
    • The single value is first or last. In [1, 2, 2] the answer sits at index 0, so there is no left neighbour. In [1, 1, 2] it sits at the last index, so there is no right neighbour. The guards in the helper handle both.
    • Negative values. [-1, -1, -5] returns -5. The numeric comparator sorts negatives correctly, but the default sort would not.
    • Forgetting the comparator. Equal numbers have equal text, so even the default string order puts copies next to each other, and this particular scan would still find the answer. The order itself is wrong, though (10 before 9), and any code that relies on numeric order would break. Always pass the comparator when sorting numbers.
    • Checking only one neighbour. Looking only to the left would report the first element of every pair. Both sides must have no match.
    • Invalid input. For [1, 1, 2, 2], which has no single value, the loop finishes and the method returns the fallback -1.

    Testing

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