Python in LeetCode

Life is short, you need Python! Life’s Pathetic, Let’s Pythonic!

We all use Python in LeetCode, with a comprehensive understanding of Python, you can write very elegant and pythonic code, which can both amaze interviewers and save our coding time. There even has a repository about solving the LeetCode with shortest lines rather than fastest :)

Here, I want to share some important and common tips and tricks in Python especially in solving these algorithm problems.

Table of Contents

Python Basics

Some people like C/C++ or Java in the interview, one major reason is their native functions and runtime is very clear. Python provides many grammar sugar and easy-to-use functions while we do not know how does it implemented and its time complexity, which will confuse the programmer. If you are not a CS major and do not have a basic understanding of algorithms, I would like to recommend MIT 6.006 and its open courseware version. It introduces the CLRS, which is widely used at many universities and also Python implementation in the lecture video.

Execution Model

How does Python works in deep? The cornerstone of Python is the Execution Model, which indicates Python’s basic execute unit is a code block. A block can be a module, a function body, a class definition or an interactive command.

Mutable vs Immutable Objects

Everything in Python is an object. The most important thing about this is the Built-in Types in Python:

Immutable: int, float, long, str, tuple
Mutable: list, set, dict

The immutable data type does not mean that it can not change the value, it means if you want to change the value of a variable, it will create a new object and bind the variable to it. As a result, the remaining old value will be waiting for the garbage collection. So, do not confuse about pass by reference or pass by value anymore. When you pass an immutable data to a function and change the value, since it will rebind to a new object, the variable outside the function scope will stay unchanged. However, when you pass a mutable data type to a function since it simply extends in the original memory address, the value change is visible outside naturally.

Memory Management in Python

Python has a lot of implementations, e.g. CPython, PyPy, Jython et al. For the default implementation, there are two GC mechanisms for CPython, Reference Counting and Generational Garbage Collection. At a basic view, the reference count is incremented whenever the object is referenced, and it’s decremented when an object is dereferenced. And when an object’s reference count is 0, the memory for the object is deallocated. You can simply use sys.getrefcount() to watch the current reference count of a variable.

>>> class MyClass(object):
...     pass
...
>>> a = MyClass()
>>> a.obj = a
>>> del a

However, the reference counting algorithm has a lot of issues, such as circular references, thread locking and memory and performance overhead. For example, when a variable has a reference to itself, the above counting will never down to 0, which will cause the memory leak.

Here comes the Generational GC, Unlike reference counting, cyclic GC does not work in real-time and runs periodically. To reduce the frequency of GC calls and pauses CPython uses various heuristics.

The GC classifies container objects into three generations. Every new object starts in the first generation. If an object survives a garbage collection round, it moves to the older (higher) generation. In order to decide when to run, each generation has an individual counter and threshold. The counter stores the number of object allocations minus deallocations since the last collection. Every time you allocate a new container object, CPython checks whenever the counter of the first generation exceeds the threshold value. If so Python initiates the сollection process. You can then check the configured thresholds of your garbage collector with the get_threshold() method. 1

Some Tricks

  1. use min and max to restrict the variable.

    • int: - sys.maxsize - 1, sys.maxsize
    • float: float('-inf'), float('inf')
    • return: max(-2**31, min(res, 2**31 - 1))
  2. array copy and init.

    • shadow copy

      x[:], x.copy()
      [x[:] for x in [[foo] * 10] * 10]
      import copy, copy.copy()
      
    • deep copy

      import copy, copy.deepcopy()
      
    • initiate

      [0 for _ in range(len(array))]
      [[0 for i in range(cols)] for j in range(rows)]
           
      row = len(matrix)
      col = len(matrix[0]) if row else 0
      
    • assign

      primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
      
    • tuple in list

      queue = [(i, j) for i, row in enumerate(rooms) 
                     for j, r in enumerate(row)]
      queue += (x, y),
      
  3. logical operators in str.

    • a and b: return b if a is True, else a.
    • a or b: return a if a is True, else b.
  4. int conversion increase time significantly.

    • use ord(str) - ord('0') instead of int(str) if necessary.
  5. iterator

    • iter(range(n)), next(item) to skip current or next iteration.
    • break the inner loop, and execute print only if the inner loop is exited normally.
      for i in range(10):
        for j in range(10):
            if i > j:
                break
        else:
            # only print 0, 9
           print(i, j)
      
  6. some math:

    • math.ceil(x / k) <=> (x-1) // k + 1
    • matrix transpose: zip(*A[::-1])

Algorithms Module Usage

This modules have integrated many useful tools and algorithms, and most of them are allowed in the interview. So please do not forget them and just keep in mind what the time complexity and how they implemented.

  1. binary search: bisect usage:

    • bisect / bisect_right: after if already exists.
    • bisect_left: before if already exists.
    • insort, insort_left, insort_right: insert
       bisect.bisect_right([1,2,2,3], 2) == 3
       bisect.bisect_left([1,2,2,3], 2) == 1
    
  2. high-performance container: collections usage:

    • deque: delete first item in list in $O(n)$.
      • append, appendleft, pop, popleft
    • Counter: count occurrences of items in a list, similar to multisets.
  3. set usage:

    • add, union, intersection
    • remove: delete exist item
    • discard: delete item without error if not exists
  4. functional programming 2

    • zip, map, filter
    • itertools module:
      • product, permutations, accumulate, repeat, chain, groupby, combinations(_with_replacement)
    • functools module:
      • partial, reduce

New in Python 3.8 3

Welcome to the Python 3.8 and try these new features out! 4

The Walrus Operator

Finally, Python have the walrus operator, which means you can assign values to a variable as part of an expression. Take the most common file reading scenario for example, before 3.8, you should do it seperately like this,

line = f.readline()
while line:
    ...  # process line
    line = f.readline()

However, now it can be done in one line.

while line := f.readline():
    ... # process line

Ordered dict and reversed

Since Python 3.7, the default dict is ordered, just like OrderedDict, and in 3.8, you can even reverse it.

>>> my_dict = dict(a=1, b=2)
>>> list(reversed(my_dict))
['b', 'a']
>>> list(reversed(my_dict.items()))
[('b', 2), ('a', 1)]

Iterable Unpacking in return

No more SyntaxError in iterable unpacking in return.

def baz():
    rest = (4, 5, 6)
   #  t = 1, 2, 3, *rest # before
   #  return t # before
    return 1, 2, 3, *rest # now derectly unpacking in return

f-strings Supports =

print(f"foo={foo} bar={bar}") # before
print(f"{foo=} {bar=}") # now support this

  1. https://rushter.com/blog/python-garbage-collector/ ↩︎

  2. https://docs.python.org/3/howto/functional.html ↩︎

  3. https://docs.python.org/3/whatsnew/3.8.html ↩︎

  4. https://deepsource.io/blog/python-3-8-whats-new/ ↩︎

Yang Li
Yang Li
@zjzsliyang

Related