LeetCode #136: Single Number

Photo by Marcel Eberle on Unsplash

By now I’m starting to see how Big O Notation is playing a role crafting a solution to a problem. The basis of the problem is to take a non empty array of integers called nums and to identify the element that only appears once. The only requirement is that the solution must utilize a linear runtime complexity and constant extra space.

We’ve seen these two Big O Notation time complexities in a prior article about the basics of Big Notation here. Linear runtime has a notation of O(n) meaning data scales linearly in relation to the amount of input. Constant time is O(1) where the time it takes for the function to perform its task will not be dependent on the amount of input.

To avoid getting overwhelmed, I’ve been trying to break down the steps of a challenge. Doing this helps me see the objectives I need to cover to achieve the solution while keeping my code clean.

//step1: count occurences of integers 
//step2: loop through integers
//step3: check to see if their value appears more than once

Essentially, what we are doing in these steps is keeping track of a value that doesn’t appear more than once. The counter() method does just that, for counting hashable objects. In this case we are keeping track how many of each integer are present in the array, and the integer that only appears once will be tracked. So now we know we must set a counter and place the array of integers nums as an argument.

def singleNumber(self, nums: List[int])
result = Counter(nums)

Now we have to extract the integer that only appears once from our counter method. To do so we use a for loop to iterate over the array of integers in nums. In each iteration, the conditional statement checks if there is an integer that only appears once. Since the counter() method is a subclass of a dictionary (which will be covered in a later post!), it checks if there is an integer with only one key in the dictionary with a count of 1. This will bring us to out solution.

def singleNumber(self, nums: List[int])
result = Counter(nums)
for i in result:
    if result[i] == 1;
       return i

Conclusion:

So far I’m feeling pretty content with transferring languages. Thanks to my bootcamp, the concepts I’ve learned have crossed over to learning Python which has made the adjustment less painful. As daunting as it is learning a new language, I find I learn more from diving into problems and googling if I don’t know the answer. A lot of times, there are handy methods like counter() that I wasn’t even aware of until I searched for them. I’ve been reminded by so many that googling is part of any software engineer’s workflow. There is so much knowledge and information out there, it is impossible to know it all.

At times I feel a bit defeated because I still haven’t been able to solve any of these algorithms yet on my own. But I continue to trust the process despite how painful it can be.