Python Tricks Learnt from Coding Data Structures & Algorithm Questions

This story is a result of spending two years of intensive coding of questions on Data Structures and Algorithm questions on platforms like Lintcode and Leetcodes. I had always publish on solutions to thorny questions that I encountered so as to alleviate the pain of the next learner.

I will take a different tack here and focused on the efficient Python techniques picked up. These are usually non-obvious tricks through much searching of techniques to be more efficient in writing less code and be more Pythonic. So credits go to the great wide web.

Photo by Alex Chumak on Unsplash

1. Sum of a 2D matrix with least amount of code

adjacencyList = [[1, 0, 0], [1, 1, 0], [0, 1, 1]]
totalSum = sum(sum(adjacency, []))
print(totalSum)
> 5

What is the magic of summing the 2D array with a empty list?

adjacencyList = [[1, 0, 0], [1, 1, 0], [0, 1, 1]]
partialStep = sum(adjacencyList, [])
print(partialStep)
> [1, 0, 0, 1, 1, 0, 0, 1, 1]

The magician’s trick revealed — [1, 0, 0, 1, 1, 0, 0, 1, 1]. This is just concatenating each of the arrays [1, 0, 0], [1, 1, 0], [0, 1, 1] into a list. We know that we already can concatenate two array list into one using the + operator (Refer to below).

a = [3, 2]
b = [4, 5]
c = a + b

In our case, the sum operators take the elements of the 2D list which are the three sub-arrays and concatenate with an empty array []. You may ask why we need to present an empty array to the sum operator to perform the concatenation. The answer is simple — sum operators work with iterables. So when you present a list (list is an iterable) of list, it will take the elements (which are list themselves) in the list and perform concatenation to something. That something is the empty array to concatenate to.

2. Creation of a 2D matrix succinctly

Use list comprehension.

array2D = [[0 for _ in range(rows)] for _ in range(cols)]

Variable rows and cols are the the number of rows and columns respectively.

3. Adding on a list as we traverse it

initial = [1, 2, 3, 4]
others = [5, 6, 7]
result = []
for element in initial:
  result.append(element)
  if others:
    initial.append(others.pop(0))
print(result)
> [1,2,3,4,5,6,7]

In the end, all the elements in both initial and others are added to result list and printed. This shows that as we traverse the for loop, elements can be added to initial and these newly added elements will also be traversed.

However, be careful. The traversal works because we are using the “for-in” syntax. A common mistake is to think that this works the same with using the “for-index-range-len” loop. See below.

initial = [1, 2, 3, 4]
others = [5, 6, 7]
result = []
for i in range(len(initial)):
  result.append(initial[i])
  if others:
    initial.append(others.pop(0))print(result)
print(result)
> [1,2,3,4]

In the “for-index-range-len” scenario, the later added on elements in initials are not traversed and appended to result list. Why? This is because the range of index is already frozen to 0, 1, 2, 3 by the execution of “len(initial)”. So no matter how new elements are added, the for loop execution will end at the 4th element.

4. Using DefaultDict and not Dictionary

In creating a dictionary, if we are storing lists or sets in the dictionary, we often have to set-up the dictionary. In the code below, you can see that the creation of the lists for each key i, before adding the first j element into the list. Not only is this ugly, it’s also a lot of code that could get wrong. Would the if statement be using j or i equals to zero?? To avoid the complications, defaultdict class comes to the rescue. It’s the same old dictionary on steroids.

aDict = dict()
for i in range(10):
  for j in range(10):
    if j == 0:
      aDict[i] = [] #set-up of a list using an if-condition
    
    aDict[i].append(j)

The defaultDict class is in the in-built collections python module. You would have to import it.

from collections import defaultdict

After that, to use it to achieve the same as the code above, we write less code:

aDictOfList = defaultdict(list) # notice the use of the list class 
for i in range(10):
  for j in range(10):
    aDictOfList[i].append(j) # we just append to the list 
print(aDictOfList)

The use of the list class above as parameter of the using instance creation basically tells the defaultdict to create a new list as value for each key.

You could also use “int” as parameter and the defaultdict will have the default value of ‘0’ for every element associated with each key at the get-go. For example:

from collections import defaultdict
aDictOfZeros = defaultdict(int) # int as parameter
for i in range(3):
  print(aDictOfZeros[i])
print(aDictOfZeros)
> 0
0
0

What if you want to threes instead of zeros for all the dictionary values at the beginning? Read on to the next section.

5. Initializing a DefaultDict that contains Non-Zeros

After reading the preceding section, we learnt how to get a defaultdict object that will be initialised to zero with the “int” initializer. What if we want the default value of the dictionary to be say “4”.

from collections import defaultdict
fourDict = defaultdict(lambda: 4)
result = []
for i in range(10):
  result.append(fourDict[i])
print(result)

The result would be ten ‘4’s.

6. Using Decorator to time function calls

Oft-time, we want to time how long a function solution takes and we want to be able to write a utility function once. We can do that using a decorator function. To understand how to put together a decorator function, we first have to understand about nested function.

def aFunction():
  def nested_function():
    return "I am nested"
  result = f"I called nested function and the output is {nested_function()}"
  return result
> aFunction() 

From above, you can see that nesting a function within another is easy since function are “first-class” objects in the Python language.

Let’s see how do we make use of the nested function idea to create a working decorator.

import time
def profile_time(function): # name of decorator function
  def wrapper_function(): # always have nested "wrapper_function"
    before = time.time()
    function()
    after = time.time()
    profile_result = f"time taken for {function.__name__} is {after - before}"
    return profile_result
  return wrapper_function # return the wrapper function - no ()"
@profile_time
def simple_loop():
  for i in range(1000000):
     i += 10
> profile_time() # will run function and show the time taken 

With the above definition, you can just use the @profile_time syntax to decorate any function. For the avoidance of doubt, the nested function returned from the decorator function also need not be named “wrapper_function”. You can use whatever naming you like.

7. Adjusting Recursion Limit

In learning Data Structure & Algorithm, you will have to solved problem using Depth-First Search (“DFS”) and backtracking. As Python does not have tail recursion optimization, the recursion frames will accumulate and eventually you will hit the recursion limit if the inputs are huge.

Bad Hair Day.

A little known tip is that the recursion is adjustable! You just have to invoke the commands below before you execute your DFS code to stop the recursion error. The tradeoff of course is that your code will now execute longer. But hey, at least we will arrive at an answer in lieu of the error.

import sys
sys.setrecursionlimit(10**6)

End. Article Updated on 22 Apr 2021

PS: I will update more as I encounter more useful tips to add to this article. Please subscribe / clap if you find this article useful. Happy coding!