Start learning free

LESSON 338 OF 338 · BIT MANIPULATION

Single Number in Go: O(n log n) with Sorting and Neighbor Checks

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

    GO · BIT MANIPULATION

    Single Number in Go, explained

    Problem overview

    The function singleNumber receives a non-empty slice of integers, nums, in which every value appears exactly 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. For [1] it is 1, since a lone element is the single one by definition. The values lie between -30,000 and 30,000, and the slice has up to 30,000 elements.

    The statement allows O(n log n) time and O(1) extra space, which is the budget that sorting fits in.

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

    The obvious ways to count occurrences cost memory: a map from value to count uses O(n) extra space. Sorting avoids that. After sorting in ascending order, equal values sit next to each other, so every value that appears twice forms a pair of adjacent equal elements.

    The single value is the only one with no equal neighbour. For [4, 1, 2, 1, 2], the sorted slice is [1, 1, 2, 2, 4]. The 1s are a pair, the 2s are a pair, and 4 has a different value on its left and nothing on its right. That's the answer.

    So the test for position index in a sorted slice has two halves. The left neighbour must not equal it (or there is no left neighbour, at index 0), and the right neighbour must not equal it (or there is none, at the last index). The two checks need guards so that they never read outside the slice.

    Faster approaches exist, but this one needs nothing beyond the standard library's sort.

    Step by step

    1. Write the helper isSingleNumber(nums, index) first, returning a bool. It answers one question: does the value at index lack an equal neighbour?
    2. Check the left neighbour. If index > 0 and nums[index-1] == nums[index], the value has a twin on its left, so return false. The condition index > 0 comes first, so nums[-1] is never evaluated, because && stops as soon as its left side is false.
    3. Check the right neighbour the same way: if index < len(nums)-1 and nums[index] == nums[index+1], return false.
    4. Return true at the end. If neither side matched, the value has no twin.
    5. In singleNumber, handle a one-element slice early: if len(nums) == 1, return nums[0]. The helper would also handle that case, but the early return skips the sort and the loop.
    6. Sort nums in place with sort.Ints. This is the step that sets the running time.
    7. Loop over every index i and call the helper. The first index for which it returns true holds the answer, so return nums[i].
    8. Return -1 after the loop. Valid input always has a single number, so this line is unreachable in practice. Go still requires the function to end with a return statement.

    The solution in Go

    func isSingleNumber(nums []int, index int) bool {
    if index > 0 && nums[index-1] == nums[index] {
        return false
    }
    if index < len(nums)-1 && nums[index] == nums[index+1] {
        return false
    }
    return true
}

func singleNumber(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        if isSingleNumber(nums, i) {
            return nums[i]
        }
    }
    return -1
}

    The Go details worth knowing:

    • The sort import. sort.Ints lives in the standard sort package, which the file must import: import "sort". Without it the compiler reports "undefined: sort". If you work outside the lesson's editor, add the import yourself.
    • Sorting changes the caller's slice. A slice is a small header that points to an array. Passing it to a function copies the header and not the elements, so sort.Ints(nums) reorders the caller's data. After singleNumber([]int{4, 1, 2, 1, 2}) runs on a variable a, a holds [1 1 2 2 4]. Copy the slice first if you still need the original order.
    • Short-circuit evaluation. In index > 0 && nums[index-1] == nums[index] the second operand is evaluated only when the first is true. That's what makes the guard work. Reading nums[-1] panics at run time with "index out of range".
    • Booleans can be returned directly. The helper returns false or true from inside if blocks, and the call isSingleNumber(nums, i) is itself a valid if condition, so no comparison with true is needed.
    • Functions can be declared in any order, but here the helper sits above singleNumber because that's the order the lesson builds them.

    Complexity

    Time: O(n log n). Sorting costs O(n log n). The loop then makes at most one pass over the slice, calling a helper that does a constant amount of work, so it adds O(n), which the sort dominates.

    Space: O(1) extra, apart from the sort's own bookkeeping. The slice is sorted in place and no new slice or map is created. The sort routine uses a small amount of stack for its recursion.

    Edge cases and common mistakes

    • One element. [1] returns 1 through the early check.
    • The single value is the smallest or the largest. In [1, 2, 2] the answer 1 is at index 0, where there is no left neighbour. In [3, 3, 9] the answer 9 is at the last index, where there is no right neighbour. The guards index > 0 and index < len(nums)-1 are what make both cases work.
    • Negative numbers. [-3, 5, -3] sorts to [-3, -3, 5] and returns 5. Sorting treats negatives like any other value.
    • Checking only one side. If the helper looked only at the left neighbour, the first element of every pair would pass the test. In [1, 1, 2] it would return the first 1 instead of 2.
    • Skipping the guards. Reading nums[index-1] at index 0 or nums[index+1] at the last index panics.
    • Forgetting to sort. On the unsorted [2, 1, 2] the first 2 has no left neighbour and its right neighbour is 1, so the helper would accept it and return 2, although 1 is the single value.

    Testing

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