Start learning free

LESSON 344 OF 344 · BIT MANIPULATION

Single Number in Java: O(n log n) by Sorting and Checking 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

    JAVA · BIT MANIPULATION

    Single Number in Java, explained

    Problem overview

    The method singleNumber receives a non-empty int[] named nums in which every value appears exactly twice, except for one value that appears once. It returns that single value. In [4, 1, 2, 1, 2] the 1s and the 2s come in pairs, so the answer is 4. In [2, 2, 1] the answer is 1, and in [1] it is 1.

    The note in the statement sets the target for this lesson: O(n log n) time and O(1) extra space. It also says that faster solutions exist and will come later.

    Approach: sort, then find the value without a twin

    The obvious way to count how often each value appears is a hash map, but that uses O(n) extra space, which the note rules out. Comparing every value with every other one avoids the space but takes O(n²) time.

    Sorting fixes both problems. After sorting, equal values sit next to each other, so each pair becomes two neighbors. The single value is the only element that equals neither its left neighbor nor its right neighbor. Sorting in place costs O(n log n) time and needs no second array, and the final scan is one pass.

    Take [4, 1, 2, 1, 2]. Sorted, it is [1, 1, 2, 2, 4]. Index 0 equals its right neighbor, index 1 equals its left neighbor, and so do indexes 2 and 3 with their partners. Index 4, holding 4, has a different left neighbor and no right neighbor, so 4 is the answer.

    Step by step

    1. Write a helper isSingleNumber(nums, index) that says whether the value at index has no twin next to it. It is private because only singleNumber uses it.
    2. Check the left neighbor. If index > 0 and nums[index - 1] == nums[index], the value has a partner, so return false. The index > 0 test comes first so the code never reads nums[-1].
    3. Check the right neighbor the same way: index < nums.length - 1 and nums[index] == nums[index + 1] mean a partner, so return false.
    4. Return true when neither neighbor matched.
    5. Handle a single element in singleNumber: if nums.length == 1, return nums[0]. The helper would also work for this case, but this check skips the sort and the loop.
    6. Sort with Arrays.sort(nums), so duplicates become adjacent.
    7. Scan every index with a for loop and return nums[i] as soon as isSingleNumber(nums, i) is true.
    8. Return -1 after the loop. The input guarantees a single number, so this line is only there because Java requires every path through the method to return something.

    The solution in Java

    class Solution {
    private boolean 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];
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (isSingleNumber(nums, i)) {
                return nums[i];
            }
        }
        return -1;
    }
}

    Java details worth a closer look:

    • Short-circuit &&. In index > 0 && nums[index - 1] == nums[index], the right side runs only when the left side is true. That is what keeps nums[index - 1] from being evaluated with a negative index. Java throws an ArrayIndexOutOfBoundsException for any index outside the array, instead of reading nearby memory.
    • Arrays.sort changes the array. It sorts in place, so the caller's nums comes back in ascending order. For primitive arrays like int[], it uses a dual-pivot quicksort. If the caller's order matters, sort a copy with nums.clone(), which costs O(n) extra space.
    • A boolean method as a condition. if (isSingleNumber(nums, i)) needs no == true, since the method already returns a boolean.
    • "O(1) extra space." The sort works within the array and creates no second copy. Like most sorting routines, it still uses a small amount of stack space for its own bookkeeping, so the note's "constant extra space" means that nothing grows with a copy of the data.

    Complexity

    Time: O(n log n). The sort dominates. The scan afterwards looks at each index once, and the helper does a constant number of comparisons, so it adds O(n).

    Space: O(1) extra, apart from the small working space of the sort. No extra array or map is created.

    A later idea does better: combine all the values with the XOR operator, result ^= num. Equal values cancel each other out, so only the single value is left. That runs in O(n) time with O(1) space and no sorting, but the sorting approach is the one this lesson practises.

    Edge cases and common mistakes

    • One element. [1] returns 1 straight away.
    • The single value at either end. In [1, 2, 2] the 1 is at index 0, with no left neighbor. In [2, 2, 1] the 1 is at the last index, with no right neighbor. The index guards in the helper handle both.
    • The single value in the middle. In [1, 1, 2, 3, 3] the 2 differs from both neighbors.
    • Negative numbers. [-3, 5, -3] sorts to [-3, -3, 5] and returns 5. The method only compares for equality, so signs don't matter.
    • Only checking one neighbor. Testing just the left neighbor would wrongly accept the first element of every pair, since its left neighbor is a different value.
    • Reading past the ends. Without the index > 0 and index < nums.length - 1 guards, the first or last element would throw an ArrayIndexOutOfBoundsException.
    • Expecting the original order. After the call, nums is sorted.

    Testing

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