Lessons from leetcode: 347 Top K Frequent Elements

For future Simon to look back on...

As a self-taught dev, learning the ins-and-outs of Python usually happens as I am solving problems on leetcode or writing random programs in replit. This post is more for myself to remember what I've learned. If you're still interested in reading, then I hope this helps you!

List Comprehension

I learned the importance of initializing a list of empty lists using list comprehension or a for loop, over simply using multiplication thanks to this leetcode problem: Top K Frequent Elements.

I created a list of empty lists like this:

bucket = [[]] * 5 # [[], [], [] ,[] ,[]]

And whenever I tried to update one list in bucket, every other list was updated as well.

bucket[1].append(5) # [[5], [5], [5], [5], [5]]

I was scratching my head about this for a while, thinking it was the other parts of my code that was the problem. In reality, it all started with my bucket initialization. I had essentially created an object [] that I copied 5 times in bucket, and thus each [] was a reference to the first [] object. Updating one would mean updating all.

The way around this would be to create a for loop or to use list comprehension which allows us to write the code more compactly.

bucket = []
for _ in range(6):
  bucket.append([])

or

bucket = [[] for _ in range(6)]

Bucket sort

Another neat trick I learned from this leetcode problem was to use bucket sort to complete the task. Often times, I am thinking about using the least amount of resources as possible, and I usually run into a dead end doing so.

Funny thing is that my initial method of solving the problem involved using the same amount of space and more time than the solution I learned from neetcode. So, I really need to focus more about saving time first and optimize space second.