Start learning free

LESSON 348 OF 348 · BIT MANIPULATION

Single Number in Kotlin: O(n log n) with Sorting, O(1) Extra Space

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

    KOTLIN · BIT MANIPULATION

    Single Number in Kotlin, explained

    Problem overview

    The function singleNumber receives a non-empty IntArray named nums in which every value appears exactly twice, except for one value that appears once. It returns that single value.

    For nums = [4, 1, 2, 1, 2] the answer is 4: the 1s and the 2s come in pairs, and 4 has no partner. For [2, 2, 1] the answer is 1, and for [1] the answer is the lone element, 1.

    The task asks for O(n log n) time and O(1) extra space. The space limit rules out copying the values into a hash set or a map, which would take O(n) extra memory.

    Approach: sort, then look for the element with no equal neighbour

    Pairs are hard to spot when equal values sit far apart. Sorting fixes that: after sorting, equal values are next to each other. For [4, 1, 2, 1, 2] the sorted array is [1, 1, 2, 2, 4], and the pairs are visible at a glance. The single value is the only element that differs from both of its neighbours.

    So the algorithm is:

    1. Sort the array in place.
    2. Scan it from the left. The first element whose left neighbour and right neighbour are both different (or missing) is the answer.

    Sorting costs O(n log n) and the scan costs O(n), so the total is O(n log n). Sorting in place needs no extra array. Faster solutions exist, and the bit manipulation chapter returns to this problem: XORing all the values cancels every pair and leaves the single one, in O(n) time and O(1) space. This lesson practises the sorting idea first.

    Step by step

    1. Write a helper private fun isSingleNumber(nums: IntArray, index: Int): Boolean that answers: does the value at index lack an equal neighbour?
    2. Check the left neighbour. If index > 0 and nums[index - 1] equals nums[index], return false: the value has a partner on the left. The index > 0 test comes first so the code never reads before the start of the array.
    3. Check the right neighbour. If index < nums.size - 1 and nums[index] equals nums[index + 1], return false. The size guard keeps the read inside the array.
    4. Return true at the end of the helper: neither neighbour matched.
    5. Handle one element first. In singleNumber, if nums.size == 1, return nums[0]. The helper would also work, but this skips the sort and the loop.
    6. Sort with nums.sort(), which sorts the array in ascending order and in place.
    7. Scan. Loop with i over every index, and when isSingleNumber(nums, i) is true, return nums[i].
    8. Add a fallback. After the loop, return -1. Every valid input has a single number, so this line is never reached for valid input. It exists because the function must return something on every path.

    The solution in Kotlin

    class Solution {
    private fun isSingleNumber(nums: IntArray, index: Int): Boolean {
        if (index > 0 && nums[index - 1] == nums[index]) {
            return false
        }
        if (index < nums.size - 1 && nums[index] == nums[index + 1]) {
            return false
        }
        return true
    }
    fun singleNumber(nums: IntArray): Int {
        if (nums.size == 1) {
            return nums[0]
        }
        nums.sort()
        for (i in 0 until nums.size) {
            if (isSingleNumber(nums, i)) {
                return nums[i]
            }
        }
        return -1
    }
}

    The Kotlin details worth a closer look:

    • sort() versus sorted(). On an IntArray, nums.sort() rearranges the array itself and returns nothing useful. nums.sorted() returns a new List<Int> and leaves the array alone. This solution needs the in-place version, both for the O(1) space bound and because the helper indexes into nums.
    • The caller's array changes. Because the sort is in place, the array passed in is reordered. After singleNumber(intArrayOf(4, 1, 2, 1, 2)) on a variable a, a holds [1, 1, 2, 2, 4]. Copy it first with copyOf() if you need the original order.
    • 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 protects nums[-1], which would throw an ArrayIndexOutOfBoundsException.
    • == on Int values compares the numbers, which is what is wanted for primitive array elements.
    • private fun. Members are public by default in Kotlin. private makes the helper visible only inside the class.
    • 0 until nums.size excludes the upper bound, so i runs over exactly the valid indices. nums.indices is the same range.

    Complexity

    Time: O(n log n). The sort takes O(n log n). The loop runs at most n times, and each call to the helper does two comparisons, so the scan is O(n). The sort dominates.

    Space: O(1) extra. The array is sorted in place and the loop keeps only an index.

    Edge cases and common mistakes

    • One element. [1] returns 1 from the early check.
    • The single value is the smallest or the largest. In [1, 2, 2] the single 1 sits at index 0, so it has no left neighbour. In [2, 2, 5] the 5 has no right neighbour. The guards index > 0 and index < nums.size - 1 treat a missing neighbour as "different".
    • Negative numbers. Sorting handles them like any other value. [-1, 3, 3] sorts to [-1, 3, 3] and returns -1, which is the genuine single value. The fallback uses -1 as well, so a returned -1 does not tell the two cases apart. Valid input never needs the fallback.
    • Dropping the bounds guards. Without index > 0 the check at index 0 reads nums[-1], and without the upper guard the last index reads past the end. Both throw ArrayIndexOutOfBoundsException.
    • Checking only one neighbour. Testing only the left neighbour accepts the first element of every pair as the answer. Both sides must differ.
    • Using sorted(). Calling nums.sorted() and ignoring the result leaves nums in its original order, so the neighbour checks run on unsorted data.
    • Input outside the contract. If every value is paired, as in [1, 1, 2, 2, 3, 3], no index passes the helper and the function returns the fallback -1.

    Testing

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