Start learning free

LESSON 372 OF 414 · BIT MANIPULATION

Single Number in Rust: 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 (when the array is sorted in place).
(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, the element at index i is the single element if both these conditions hold true:
  • i is the first index, or the previous element is different from the element at index i
  • i is the last index, or the next element is different from the element at index i


We sort the array, thus the Time Complexity is O(n log n).
If we sort nums in place, we don't use any extra arrays, so the Extra Space used is O(1). (Sorting a copy, as Swift's sorted() does, would take O(n) extra space.)

STEP 1 OF 11
    Ctrl + Enter to check

    RUST · BIT MANIPULATION

    Single Number in Rust, explained

    Problem overview

    The function single_number receives a non-empty vector nums of integers in which every value appears twice except for one. It returns the value that appears once. The statement asks for O(n log n) time and O(1) extra space.

    For nums = [4, 1, 2, 1, 2] the answer is 4: the 1 and the 2 each appear twice, and the 4 appears once. For [2, 2, 1] the answer is 1, and for [1] it is 1.

    Approach: sort, then find the value without a twin

    Checking, for each element, whether another copy exists would take O(n²) time. A hash map of counts is faster but uses O(n) extra space. Sorting avoids both. After [4, 1, 2, 1, 2] is sorted, it becomes [1, 1, 2, 2, 4], and equal values sit next to each other. Every value that has a partner has an equal neighbor on one side. The single value is the only one whose left neighbor and right neighbor both differ from it, or are missing.

    So the plan is: sort, then walk through the positions and return the first value that matches neither neighbor. The lesson puts that check into a helper, is_single_number, which says whether the value at a given index has no equal neighbor.

    Here is the check on the sorted vector [1, 1, 2, 2, 4]:

    • Index 0 holds 1. It has no left neighbor, but its right neighbor is also 1, so it fails.
    • Index 1 holds 1. Its left neighbor is 1, so it fails.
    • Index 2 holds 2 and index 3 holds 2. Each has an equal neighbor, so both fail.
    • Index 4 holds 4. Its left neighbor is 2 and it has no right neighbor, so it passes, and the function returns 4.

    The scan can't return the wrong value, because every value that appears twice occupies two adjacent positions after sorting, and each of those two has the other as a neighbor. Only the single value has no equal neighbor on either side.

    Step by step

    1. Write the helper's signature. is_single_number takes the slice nums: &[i32] and an index: usize and returns a bool.
    2. Check the left neighbor. If index > 0 and nums[index - 1] equals nums[index], the value has a twin on its left, so return false.
    3. Check the right neighbor. If index < nums.len() - 1 and nums[index] equals nums[index + 1], return false.
    4. Return true when neither neighbor matched.
    5. Sort in place in single_number, so equal values become adjacent. The parameter is declared mut nums to allow this.
    6. Loop over every index and call the helper. Return nums[i] for the first index where it answers true.
    7. Return -1 after the loop. The input always contains a single number, so this line is only a safety fallback.

    The solution in Rust

    impl Solution {
    fn is_single_number(nums: &[i32], index: usize) -> bool {
        if index > 0 && nums[index - 1] == nums[index] {
            return false;
        }
        if index < nums.len() - 1 && nums[index] == nums[index + 1] {
            return false;
        }
        true
    }
    fn single_number(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        for i in 0..nums.len() {
            if Self::is_single_number(&nums, i) {
                return nums[i];
            }
        }
        -1
    }
}

    Rust details worth a closer look:

    • Guards come first. && stops as soon as its left side is false. Writing index > 0 && nums[index - 1] == ... means nums[index - 1] is only evaluated when index is at least 1. The index is a usize, which can't go below zero: index - 1 at 0 would wrap in an optimized build and panic in a debug build, and either way the indexing that follows would be out of bounds.
    • Borrowing the vector. The helper takes &[i32], and the call passes &nums, a reference to the vector, which converts to a slice. The vector isn't moved, so the loop can still read nums[i] afterwards.
    • In-place sort. nums.sort() changes the vector itself and returns nothing. That requires mut nums in the parameter list. The sort is stable and takes O(n log n) time. sort_unstable() also works here, because equal integers are interchangeable, and it sorts without allocating temporary storage. The standard sort() may allocate temporary storage, so strictly speaking only sort_unstable() keeps the extra space at O(1).
    • Returning values. true and -1 are the last expressions of their functions, with no return and no semicolon. The earlier return false; and return nums[i]; exit early.

    Complexity

    Time: O(n log n). Sorting costs O(n log n). The loop calls the helper at most n times, and each call looks at two neighbors in constant time, so the scan is O(n) and sorting dominates.

    Space: O(1) beyond the input, apart from whatever temporary buffer the standard sort uses. The vector is sorted in place and the helper keeps no data.

    Edge cases and common mistakes

    • A single element. For [1] both neighbor checks are skipped, because index > 0 is false and index < nums.len() - 1 is 0 < 0, also false. The helper returns true.
    • The single value at either end. For [2, 2, 1] the 1 is the last element and has no right neighbor. For [1, 2, 2] it is first. Both work because each side is checked only when it exists.
    • Negative values. [-3, 5, -3] sorts to [-3, -3, 5] and returns 5. The sort handles negative integers, and the comparisons need no special treatment.
    • Checking only one side. Looking only at the left neighbor wrongly accepts the first element of every pair. Both sides must be checked.
    • Skipping the sort. Without it, equal values aren't adjacent and the neighbor test says nothing.
    • Using index <= nums.len() - 1. That allows nums[index + 1] on the last element, which is out of bounds and panics.

    Testing

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