Solving the Single Number Problem in Python

The challenge

Given a non-empty array of integers, every element appears twice except for one. Find that single one.


Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

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

The solution in Python

def singleNumber(nums):
    # create a dictionary/hashmap
    found = {}

    # loop through the nums
    for i in nums:
        # add to map if not found
        if i not in found:
            found[i] = i
            # otherwise remove it
            del found[i]

    # loop through the found map and return the first item
    for i in found:
        return i