Solution by awice


  • 0

    Approach #1: Sorting [Accepted]

    Intuition

    Let's sort the array. Then, all duplicate values will be side by side, making it easy to identify the unique value.

    Algorithm

    Sort the array. While nums[2*j] == nums[2*j + 1], the unique value must occur later in the array. Otherwise, it occurs at nums[2*j]. In our implementation, we will set i = 2*j.

    Python

    class Solution(object):
        def singleNumber(self, nums):
            nums.sort()
            for i in range(0, len(nums), 2):
                if i + 1 == len(nums) or nums[i] != nums[i + 1]:
                    return nums[i]
    

    Complexity Analysis

    • Time Complexity: $$O(N \log N)$$, where $$N$$ is the length of the given array nums, for sorting the array. Afterwards, the $$O(N)$$ factor of searching the array is dominated by this factor.

    • Space Complexity: $$O(N)$$ for sorting with Timsort, the default sorting algorithm built in Python. Other sorting algorithms may have different complexities depending on their implementation.


    Approach #2: Count With Dictionary [Accepted]

    Intuition

    Let's count the number of occurrences of each number. The answer is the number that occurs exactly once.

    Algorithm

    For each number, increment it's count in a dictionary or HashMap type structure. Then, loop through each number and return it if it has a count of 1.

    Python

    class Solution(object):
        def singleNumber(self, nums):
            count = {}
            for x in nums:
                count[x] = count.get(x, 0) + 1
    
            for x in count:
                if count[x] == 1:
                    return x
    

    Alternate Implementation

    class Solution(object):
        def singleNumber(self, nums):
            count = collections.Counter(nums)
    
            for x in count:
                if count[x] == 1:
                    return x
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the given array nums. Every unique value is processed up to three times: twice when adding to the count, and once when searching the answer.

    • Space Complexity: $$O(N)$$, where $$N$$ is as defined above. Each number must be stored in the dictionary, and there are at least $$N/2$$ of them (and at most $$O(N)$$), which is order $$O(N)$$.


    Approach #3: Manage Set of Uniques [Accepted]

    Intuition and Algorithm

    Let's remember all currently unique values in some Set or Object structure. At the end, we'll only have one unique value.

    Python

    class Solution(object):
        def singleNumber(self, nums):
            uniques = set()
            for x in nums:
                if x in uniques:
                    uniques.remove(x)
                else:
                    uniques.add(x)
            return uniques.pop()
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the given array nums. Every value is processed once.

    • Space Complexity: $$O(N)$$, where $$N$$ is as defined above. The set uniques could contain up to $$\left \lceil{N/2}\right \rceil$$ elements, which is order $$O(N)$$.


    Approach #4: Mathematical [Accepted & Optimal]

    Intuition

    Motivated by not using additional space, let's ask what state (of constant complexity) we would need to know upon processing some of the numbers, to be able to construct the answer upon processing the rest of the numbers.

    Additionally, if we have an algorithm that works on binary numbers, we can extend our algorithm to work on non-negative integers by performing the algorithm for each bit. For example, [2, 2, 1] is [10, 10, 01] in binary, and our algorithm on [1, 1, 0] -> 0 and [0, 0, 1] -> 1 can be used to determine the final answer of 01 in binary.

    Investigation

    For binary numbers, it's clear that there are 4 differentiated states that we could be in after looking at some of the numbers:

    • State X: Seen no uniques - eg. [0, 0, 1, 1]
    • State Y: Seen a unique of 0 - eg. [0, 1, 1]
    • State Z: Seen a unique of 1 - eg. [1, 1, 1]
    • State A: Seen a unique of 0 and 1 - eg. [0, 0, 0, 1]

    And that we would like the following transitions:

    • X + 0 = Y; X + 1 = Z
    • Y + 0 = X; Y + 1 = A
    • Z + 0 = A; Z + 1 = X
    • A + 0 = Z; A + 1 = Y

    where + is some operator (not necessarily commutative).

    Bit-wise operators also naturally work on all bits of the integer at once. If the operator is the bit-wise XOR operator, then $$X = Y = 0$$, $$Z = A = 1$$ is a solution, so let's use that.

    Algorithm

    Simply XOR-sum all the numbers together.

    Python

    class Solution(object):
        def singleNumber(self, nums):
            ans = 0
            for x in nums:
                ans ^= x
            return ans
    

    Alternative Implementation

    class Solution(object):
        def singleNumber(self, nums):
            return reduce(operator.xor, nums)
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the given array nums. Every value is processed once.

    • Space Complexity: $$O(1)$$. The current answer is stored as a single integer.


  • 0

    I don't think sorting is O(1) space. I think it's only "in-place" in the sense of modifying the list instead of returning a new one. Not in the sense of not using extra space for its work. Python uses Timsort and Wikipedia's article says space complexity is O(n).

    In the transitions for the last solution, shouldn't "X + 0 = 0" be "X + 0 = Y" (and some others similarly)?


  • 0

    @StefanPochmann Right again on both counts, I corrected it.


  • 0

    @awice Timsort isn't the default for Java, for primitive types Java uses a Quicksort variant.


  • 0

    @StefanPochmann What is the space complexity for c++ std::sort and java Arrays.sort with a typical implementation? I guess Arrays.sort is timsort, except on primitive types it is a quicksort variant? Is that variant log N space?


  • 0

    @awice Sorry, I don't know the space complexities of standard library sort functions, probably because I don't care :-P. I'm pretty certain they're O(n) or better and that's good enough for me.

    Yes, Java's Arrays::sort is a Timsort "adaption" for objects and that quicksort variant for primitive types. Check out the sort method documentations on the Arrays doc page for some more details.

    LeetCode sometimes/often (?) uses Lists instead of arrays, and List::sort is documented as using a Timsort adaption as well (unsurprisingly, as List automatically means objects, not primitives).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.