Single Number

Problem Statement

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.

Approach

• First if there are no elements in the list return None.
• Keep track of numbers occurring once in singleSet and multiple times in multipleSet.
• Now go over each element in singleSet, and return the first element in singleSet.

Algorithm

Code

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        if len(nums) < 1: return None

        singleSet: set = set()
        multipleSet: set = set()

        startingPoint: int = 0
        endingPoint: int = len(nums) - 1

        while startingPoint <= endingPoint:
            if nums[startingPoint] in singleSet:
                singleSet.remove(nums[startingPoint])
                multipleSet.add(nums[startingPoint])

            elif nums[startingPoint] not in multipleSet:
                singleSet.add(nums[startingPoint])

            if startingPoint == endingPoint:
                startingPoint += 1
                endingPoint -= 1
                continue

            if nums[endingPoint] in singleSet:
                singleSet.remove(nums[endingPoint])
                multipleSet.add(nums[endingPoint])

            elif nums[endingPoint] not in multipleSet:
                singleSet.add(nums[endingPoint])

            startingPoint += 1
            endingPoint -= 1

        for num in singleSet:
            return num

        return None

Leetcode Result

So that's it... make sure if you liked the post and got to learn something, like the post and follow us. If you want me to improve at some point... leave that in the comment...