Friedrich Ewald My Personal Website

Leetcode: Single number

Given a list of integers [1,1,2], there is only one number which is not repeated. The numbers can be in any order. The minimum length of the array is 1. Numbers can be negative or positive. The algorithm should have a time complexity of O(n) and a space complexity should be constant O(1). Given this information, we can use the properties of a set or a map.

from typing import List, Optional

class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    s = set()
    for n in nums:
      if n in s:
    return s.pop()

if __name__ == '__main__':
  s = Solution().singleNumber
  print(s([1,2,1,2,3]), 3)
In the worst case this set uses the space O(n/2) which seems to be accepted according to the comments in the question.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.