136. Single Number

Linear Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
 var singleNumber = function(nums) {
    const map = {};
    
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (map[num] === 1) {
            delete map[num];
        } else {
            map[num] = 1;
        }
    }
    
    return Object.keys(map)[0];
};

Complexity

  • Time Complexity: O(N), where N is the size of nums.
  • Space Complexity: O(N), where N is at maximum the size of nums / 2.

Bit Manipulation Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
 var singleNumber = function(nums) {
    let res = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        res = res ^ nums[i];
        
    }
    
    return res;
};

Complexity

  • Time Complexity: O(N), where N is the size of nums.
  • Space Complexity: O(1).

All Solutions