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...
Top comments (0)