Start learning free

LESSON 347 OF 347 · BIT MANIPULATION

Single Number in C#: Sort and Compare Neighbors

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

    SingleNumber(nums) receives a non-empty int[] in which every value appears exactly twice, except one value that appears once. It returns that value. The array holds between 1 and 30,000 elements, each between -30,000 and 30,000.

    For [4, 1, 2, 1, 2] the answer is 4. For [2, 2, 1] it is 1, and for [1] it is 1. The lesson asks for O(n log n) time and O(1) extra space, which points at sorting.

    Approach: sort, then look at each value's neighbors

    Before sorting, the pairs can be anywhere in the array. After sorting, equal values sit next to each other. Take [2, 1, 3, 1, 3]: sorted, it becomes [1, 1, 2, 3, 3]. The pairs are side by side, and the single value, 2, is the only one that differs from both of its neighbors.

    So the test for index i is: the left neighbor (if there is one) is different, and the right neighbor (if there is one) is different. The first index that passes holds the answer. A hash set would also work, but it needs O(n) extra space, and the lesson sets O(1). Other lessons in this chapter show faster ideas, such as combining all the values with the bitwise XOR operator ^, which cancels equal pairs and runs in O(n) time with O(1) space. This lesson practices the sorting idea, which needs no bit tricks and shows why sorting turns "find the odd one out" into a local check.

    Walk through [4, 1, 2, 1, 2]. Sorting gives [1, 1, 2, 2, 4]. Index 0 holds a 1 whose right neighbor is also 1, so it fails. Index 1 holds a 1 whose left neighbor is 1, so it fails. Indices 2 and 3 fail the same way, with the 2s. Index 4 holds 4: it has a left neighbor, 2, which differs, and no right neighbor at all. It passes, and the method returns 4.

    Step by step

    1. Write a helper, IsSingleNumber(nums, index), that answers "does this position have no matching neighbor?".
    2. Check the left neighbor. If index > 0 and nums[index - 1] == nums[index], the value has a pair on its left, so return false. The index > 0 test comes first so the code never reads before the start of the array; nums[-1] would throw IndexOutOfRangeException.
    3. Check the right neighbor the same way, guarded by index < nums.Length - 1, and return false if it matches.
    4. Return true at the end of the helper. Neither neighbor matched, so this value has no pair.
    5. Handle a one-element array at the top of SingleNumber by returning nums[0]. The helper would also cope with it, but the early return skips the sort and the loop.
    6. Sort the array in place with Array.Sort(nums). This is the O(n log n) part.
    7. Loop over every index and return nums[i] for the first one where IsSingleNumber(nums, i) is true.
    8. Add a fallback return -1 after the loop. The input always contains a single number, so the line is never reached; the compiler still requires a return on every path.

    The solution in C#

    class Solution {
    private bool IsSingleNumber(int[] nums, int index) {
        if (index > 0 && nums[index - 1] == nums[index]) {
            return false;
        }
        if (index < nums.Length - 1 && nums[index] == nums[index + 1]) {
            return false;
        }
        return true;
    }
    public int SingleNumber(int[] nums) {
        if (nums.Length == 1) {
            return nums[0];
        }
        Array.Sort(nums);
        for (int i = 0; i < nums.Length; i++) {
            if (IsSingleNumber(nums, i)) {
                return nums[i];
            }
        }
        return -1;
    }
}

    C# details worth knowing

    • Array.Sort(nums) sorts the array in place, so the caller's array is reordered. After running the method on [4, 1, 2, 1, 2], the same array holds [1, 1, 2, 2, 4]. If the original order matters, sort a copy.
    • The && operator stops at the first false operand. That is what makes index > 0 && nums[index - 1] == nums[index] safe: when the first part is false, the array access never runs.
    • Indexing outside an array throws IndexOutOfRangeException. C# does not return a default value or wrap around.
    • The helper is marked private, so only the class can call it. That's also the default for members with no modifier.

    Complexity

    Sorting takes O(n log n) time. The loop then makes one pass, and each call to the helper does a constant amount of work, so the pass is O(n). The total is O(n log n), dominated by the sort. No extra arrays are created, which gives O(1) extra space apart from what the sorting routine itself uses internally.

    Edge cases and common mistakes

    • One element. [1] returns 1 right away.
    • The single value at either end. For [7, 3, 3], which sorts to [3, 3, 7], the last position has no right neighbor, and the guard on index keeps the check from running off the end. For [-5, -1, -1] the first position has no left neighbor.
    • Negative values. Sorting handles them with no extra code, and the neighbor comparison only tests equality, so the sign never matters.
    • Comparing only one side. Checking just the right neighbor would wrongly accept the second copy of a pair, since its right neighbor can differ.
    • Skipping the guards. Reading nums[index + 1] on the last index throws.

    Testing

    [4, 1, 2, 1, 2]  ->  4
[2, 2, 1]        ->  1
[1]              ->  1
[-1, -1, -5]     ->  -5
[7, 3, 3]        ->  7
    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