Python For Algorithm

Defaultdict

from collections import defaultdict
adj = defaultdict(list)

Priority queue

import heapq
heapq.heappush(heap, item)
smallest = heapq.heappop(heap)
smallest = heapq.heappushpop(heap, item) # more efficient than separated
heapq.heapify(x) # inplace
heapq.nlargest(k, nums) # a list of k largest numbers

Queue, stack

que = deque([i])
while que:
  x = que.popleft()
  for j in adj[x]:
    que.append(j)

st = []
for x in li:
  while st and st[-1] > x:
    st.pop()
  st.append(x)

Sort by custom key

sorted_list = sorted(tuples, key=lambda x : x[1])
coordinates.sort(key=lambda x : (x[0], -x[1]))

Char to Int, Int to char

ord('a') == 97
chr(97) == 'a'

Cache

import functools
@functools.cache
def dp(x, y):
  pass
dp.cache_clear() # clear space

Example question: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-v/

Bit

(x >> i) & 1 # getting i-th bit, counting from right

x = 15
x.bit_count()
# 4

Bisect

https://docs.python.org/3/library/bisect.html

bisect.bisect_right() is the default bisect.bisect()
It inserts at a position which is after all the existence of x
bisect.bisect_left() insertion point is before any existence of x

import bisect
l = [0, 1, 1, 5]
bisect.bisect_left(l, 1, lo=0, hi=len(l)) == 1
bisect.bisect_right(l, 1, lo=0, hi=len(l)) == 3

l2 = [(0, 1), (2, 4), (2, 7), (7, 8)]
bisect.bisect_left(l2, (2,)) == 1

Insort. Similar to bisect but slower because it inserts elements.

The insort() functions are O(n) because the logarithmic search step is dominated by the linear time insertion step.

Fraction. Sometimes it can be useful. It is hashable.

from fractions import Fraction
Fraction(9, 3) == 3

Combinations & Permutations

>>> from itertools import combinations, permutations
>>> list(combinations(range(3), 2))
[(0, 1), (0, 2), (1, 2)]
>>> list(permutations(range(3)))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]