Melissa Guachun

Posted on

# LeetCode #136: Single Number

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.

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.

geraldew

As the topic here is half about the process of "crafting a solution to a problem" I'll respond to that rather than offer thoughts on the specific example.

( Which is of course hard, as my nerd brain wants to dive into that mix of: - what is the solution to that? - how would I tackle that?)

One thing about having been around a bit longer, is that I began my coding life well before there was any great chance to search the Internet for solutions. This means that my natural bent - even these days - is to start thinking on my own. It seems a strange thing to say now, but maybe that has imprinted a skill for that kind of thinking. A mental muscle for starting from scratch. To be honest that's not something I've explicitly meta-thought about for a very long time.

As all our experiences are exactly that: just our experiences - it means I have no basis for the following, but maybe:

• yes, it is well worth investing in the working out of solutions by ourselves.

Not because that 's the most efficient way to get something done - but instead because it builds a skill at solving problems. I could even go so far as to suggest it might also improve that skill for its benefit in evaluating solutions when looking for them online.

(Which is perhaps just a long way to say I agree that you're right to continue to trust the process.)

p.s. actually I felt like writing more on this so I've put that here: Meta Coding - Deriving Algorithms and Seeking Solutions

Melissa Guachun

Thanks, it's like working out a muscle. I'll check your article out!!