Leetcode Daily Challenge - Single Number

Leetcode Challenges are extremely helpful to build and revise your concepts of Problem Solving. Presenting you the Daily Challenge of 15th February. Click on this link to solve it on Leetcode on 15th Febraury 2022 and get 10 points assured.

Approach 1: Brute Force
It asks you to find which number has a sole occurrence in the list. Very wise of Leetcode of to put up the question the very next day after Valentine's Day, maybe the lonely number in the list is a coder too.

Jokes aside, the simplest approach we can have is to pick a number and check if it is present twice or more and continue checking until we we get the one which has no doppelganger. This would cost us a time complexity of O(n^2) as we will compare each number to the whole list with a space complexity of O(1).

for i in range(len(nums)):
            if nums.count(nums[i]) == 1:
                return nums[i]

Approach 2: Hash table
Using a hash table can save you from TLE as it reduces the time complexity and makes the solution more readable with better code. How we approach is we will store the occurrences of each numbers in the list, which will transform into keys of the hash table.

Once we are done creating a hash table, either you can sort the dictionary and the return the first first key which will be having a single occurrence or traverse through the list to check the number having one occurrence. I prefer the lateral one having O(n) complexity because no sorting algorithm in the world assures a time complexity below O(n*logn). Since we created a hashtable, the space complexity would be O(n)

ht = {}
        for i in nums:
            if i not in ht:
                ht[i] = 1
            else:
                ht[i] += 1

        for k,v in ht.items():
            if v == 1:
                return k

ht = {}
        for i in nums:
            if i not in ht:
                ht[i] = 1
            else:
                ht[i] += 1

        ht = sorted(ht.items(), key = lambda x: x[1])
        a = ht[0]
        return a[0]

Hope you understood how I handled this problem. See you with some other problem. Happy Leetcoding!!!
To learn the fundamentals of python do checkout my YouTube Channel.