136. Single Number

  • 1

    Approach #1 [Accepted]


    First, we create a HashMap to store the current integer as key, and the count as the value.

    Loop through every element in the nums array and declare a counter variable within the array so
    that the counter will restart with every iteration.

    Next, we check if the HashMap does not contain the current number from our array. If the number is not
    in the HashMap, we increase the counter by 1, and put the current number as key, and counter as value in
    the HashMap.

    However, if the current number is found in the map, we override its contents by adding 1 to the current value.

    To get the single numbers, we create a method "findSingleNum" that takes in the map as an argument,
    We loop through the Map's EntrySet, to find the value that is equal to 1 and return its key.


    public class Solution {
        public int singleNumber(int[] nums) {
            Map<Integer, Integer> ht = new HashMap<Integer, Integer>();
            for(int single = 0; single < nums.length; single++){
                int counter = 0;
                    ht.put(nums[single], counter);
                } else{
                	int value = ht.get(nums[single]);
                	ht.put(nums[single], value + 1);
            int singleNum = findSingleNum(ht);
            return singleNum;
        public static int findSingleNum(Map<Integer, Integer> ht){
        	int key = 0;
        	for(Map.Entry<Integer, Integer> entry : ht.entrySet()){
        		if(entry.getValue() == 1){
        			key = entry.getKey();
        	return key;

    Complexity Analysis

    • Time complexity : O(n) + O(m) = O(n + m). In the worst case, each number will be visited once, giving an O(n) complexity.
      We loop through the map contents to find the key, who's value is equal to 1, which is O(m). Thus, the complexity for this approach
      is O(n + m).

    • Space complexity : O(n) The space complexity is O(n) where n is the number of items in the HashMap.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.