Start learning free

LESSON 372 OF 414 · BIT MANIPULATION

Single Number in Scala: 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 (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 13
    Ctrl + Enter to check

    SCALA · BIT MANIPULATION

    Single Number in Scala, explained

    Problem overview

    The method singleNumber receives a non-empty Array[Int] called nums in which every value appears exactly twice, except one value that appears once. It returns that single value.

    For [4,1,2,1,2] the answer is 4: the 1s and the 2s form pairs, and 4 stands alone. For [2,2,1] it is 1, and for [1] it is 1. The statement sets a budget of O(n log n) time and O(1) extra space, which points at sorting.

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

    In an unsorted array, the two copies of a value can be anywhere, so finding the unpaired one means comparing a lot of positions. After sorting, equal values sit next to each other. In [4,1,2,1,2] the sorted array is [1,1,2,2,4], with every pair adjacent. The single value is the only one that differs from both of its neighbors.

    For a position i in the sorted array, the value is the single one when both of these hold:

    • it is at index 0, or nums(i - 1) is different from nums(i);
    • it is at the last index, or nums(i + 1) is different from nums(i).

    The lesson writes this test as a helper, isSingleNumber, which answers false as soon as it finds an equal neighbor. A loop over all positions returns the first value for which it answers true.

    Step by step

    1. Declare the helper above singleNumber: private def isSingleNumber(nums: Array[Int], index: Int): Boolean. private hides it from code outside the class.
    2. Check the left neighbor. If index > 0 && nums(index - 1) == nums(index), return false: this value has a twin on its left. The test index > 0 comes first so that nums(-1) is never read.
    3. Check the right neighbor. If index < nums.length - 1 && nums(index) == nums(index + 1), return false. The first test prevents reading past the end.
    4. Return true at the end of the helper: neither neighbor matched.
    5. Handle a single element. In singleNumber, if nums.length == 1, return nums(0). The helper would also give the right result, but this skips the sort and the loop.
    6. Sort in place with java.util.Arrays.sort(nums), so the pairs become adjacent.
    7. Loop over every index with for (i <- 0 until nums.length). The range excludes its end, so i stops at the last index.
    8. Test and return. If isSingleNumber(nums, i) is true, return nums(i).
    9. Add a fallback. After the loop, return -1. The input always contains a single value, so this line is never reached for valid input. It is there because the method must return an Int on every path.

    The solution in Scala

    class Solution {
    private def isSingleNumber(nums: Array[Int], index: Int): 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
    }
    def singleNumber(nums: Array[Int]): Int = {
        if (nums.length == 1) {
            return nums(0)
        }
        java.util.Arrays.sort(nums)
        for (i <- 0 until nums.length) {
            if (isSingleNumber(nums, i)) {
                return nums(i)
            }
        }
        return -1
    }
}

    Scala details worth a closer look:

    • Calling a Java method. Scala runs on the JVM and can call Java's standard library directly. java.util.Arrays.sort accepts the Array[Int] because it is a Java int[] at run time.
    • In place versus a copy. java.util.Arrays.sort(nums) reorders the caller's array. After singleNumber(a) with a = Array(4,1,2,1,2), a holds 1,1,2,2,4. Scala's own nums.sorted leaves the original untouched and returns a new array, so it would use O(n) extra space.
    • Short-circuit &&. In index > 0 && nums(index - 1) == nums(index), the right side is evaluated only when the left side is true. That is what makes the guard work. Reading nums(-1) directly throws ArrayIndexOutOfBoundsException.
    • return in Scala. Scala methods usually give their last expression as the value, and return is rare. Here the lesson uses it because the methods must stop in the middle. The return nums(i) inside the for body is a non-local return, which the Scala 3.5 compiler reports as a warning. The code still runs and returns the right value.
    • Return type. The type Int after the parameter list is declared, and a method that uses return must declare its result type.

    Complexity

    Time: O(n log n). Sorting takes O(n log n). The loop checks each position once, and each check looks at two neighbors, so it costs O(n). The sort dominates.

    Space: O(1) extra. The array is sorted in place and no other array is created. The sort itself uses a small amount of stack space. This is the cost of changing the input: if you need the original order afterwards, sort a copy.

    The statement mentions faster solutions. A single pass with the bitwise XOR operator, nums.reduce(_ ^ _), runs in O(n) time, because a value XORed with itself is 0 and 0 XOR a value is that value, so the pairs cancel. For [4,1,2,1,2] it also gives 4.

    Edge cases and common mistakes

    • One element. [1] returns 1 from the early check.
    • The single value at either end. In [1,1,2,2,4] the answer is the last element, and in [3,7,7,9,9] it is the first. The index guards make both ends work.
    • Negative numbers. [-3,5,-3] returns 5. Sorting orders negatives before positives, and the neighbor test needs no change.
    • Checking only one neighbor. A test that looks only to the right returns 1 for [1,1,2], because the second 1 has no equal neighbor on its right. Both sides are needed.
    • Missing guards. Without index > 0 or index < nums.length - 1, the first or last position reads outside the array and throws.
    • The input has changed. The caller's array is sorted afterwards. This surprises code that reuses the array.
    • Invalid input. If every value were paired, as in [1,1,2,2], the loop finds nothing and the method returns the fallback -1.

    Testing

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