LeetCode Problem #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 1:

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

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

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴

Initial Solution:

It is a easy question which can be solved in many ways, you can sort the array and check 2 items at once (most optimal solution). or use set/hashmap like below to approach it.

HashSet:

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> numbers = new HashSet<>();
        for (int num : nums) {
            if(numbers.contains(num)) numbers.remove(num);
            else numbers.add(num);
        }
        return numbers.stream().findFirst().get();
    }

HashMap:

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> numbers = new HashMap<>();
        for (int num : nums) {
            if (numbers.containsKey(num)) {
                numbers.put(num, numbers.get(num) + 1);
            } else numbers.put(num, 1);
        }
        return numbers.entrySet().stream().filter(n -> n.getValue() == 1).map(Map.Entry::getKey).findFirst().get();
    }
}

Peformance:

N/A