136. Single Number

Question

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one
You must implement a solution with a linear runtime complexity and use only constant extra space

Example 2

Input: nums = [4,1,2,1,2]
Output: 4

Solution 1: Brute Force

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: Sorting + Linear Search

Time Complexity: O(N*Log(N))
Space Complexity: O(1)

Solution 3: Hash Counter

Time Complexity: O(N)
Space Complexity: O(N)

Solution 4: Set

Time Complexity: O(N)
Space Complexity: O(N)

Solution 5: XOR

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = nums[0]
        for i in range(1, len(nums)):
            ans ^= nums[i]
        return ans

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/single-number/discuss/1771771/Think-it-through-oror-Time%3A-O(n)-Space%3A-O(1)-oror-Python-Explained

Follow-up List:

• Single Number II
• Medium
• Single Number III
• Medium
• Missing Number
• Easy
• Find the Duplicate Number
• Medium
• Find the Difference

TODO

Time Complexity: O()
Space Complexity: O()