Leetcode 136) Single Number

10 Nov 2021 in Algorithms

My Solution

• Time Complexity : O(n) => Set has constant search and insert time O(1)
  • cf) ArrayList.contains() method requires O(n) time
• Space Complexity : O(n) => Creating new data structure from given array.

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int i =0;i<nums.length; i++){
            if(!s.contains(nums[i])){
                s.add(nums[i]);
            }else{
                s.remove(nums[i]);
            }
        }
        int last= 0;
        for(int i : s){
            last= i;
        }
        return last;
    }
}

Other Solution

• Create set, add elements and keep sum, After done making set, iterate all and double the entire sum, substract

• Time Complexity : O(n)
• Space Complexity : O(n)

class Solution {
    public int singleNumber(int[] nums) {
        int sumOfSet = 0, sumOfNums = 0;
        Set<Integer> set = new HashSet();

        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
                sumOfSet += num;
            }
            sumOfNums += num;
        }
        return 2 * sumOfSet - sumOfNums;
    }
}