• Common Leetcode solution templates
• Common Leetcode Python builtin module/api
• Some notes as my own reminders

Common Leetcode solution templates

Template - Backtracking

ans = []
def dfs(start_index, path, [...additional states]):
    if is_leaf(start_index):
        ans.append(path[:]) # add a copy of the path to the result
        return
    for edge in get_edges(start_index, [...additional states]):
        # prune if needed
        if not is_valid(edge):
            continue
        path.add(edge)
        if additional states:
            update(...additional states)
        dfs(start_index + len(edge), path, [...additional states])
        # revert(...additional states) if necessary e.g. permutations
        path.pop()

Template - binary_search while left <= right

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    first_true_index = -1
    while left <= right:
        mid = (left + right) // 2
        if feasible(mid):
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_index

Template - binary_search while lo < hi

import bisect
bisect.bisect_left


# implementation of bisect.bisect_left()
def bisect_left(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid

    return lo

# similar to Leetcode-302, find left/right/top/bottom callable
# unified search api
def search(self, image: List[List[str]], start: int, end: int, check: Callable) -> int:
    while start < end:
        mid = start + (end - start) // 2
        if check(image, mid):
            end = mid
        else:
            start = mid + 1
    return start

Template - tree bfs

def bfs(root):
    queue = deque([root])
    while len(queue) > 0:
        node = queue.popleft()
        for child in node.children:
            if is_goal(child):
                return FOUND(child)
            queue.append(child)
    return NOT_FOUND

Template - tree dfs

def dfs(root, target):
    if root is None:
        return None
    if root.val == target:
        return root
    left = dfs(root.left, target)
    if left is not None:
        return left
    return dfs(root.right, target)

Template - graph bfs

def bfs(root):
    queue = deque([root])
    visited = set([root])
    while len(queue) > 0:
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor in visited:
                continue
            queue.append(neighbor)
            visited.add(neighbor)

Template - graph dfs

def dfs(root, visited):
    for neighbor in get_neighbors(root):
        if neighbor in visited:
            continue
        visited.add(neighbor)
        dfs(neighbor, visited)

Template - matrix bfs

num_rows, num_cols = len(grid), len(grid[0])
def get_neighbors(coord):
    row, col = coord
    delta_row = [-1, 0, 1, 0]
    delta_col = [0, 1, 0, -1]
    res = []
    for i in range(len(delta_row)):
        neighbor_row = row + delta_row[i]
        neighbor_col = col + delta_col[i]
        if 0 <= neighbor_row < num_rows and 0 <= neighbor_col < num_cols:
            res.append((neighbor_row, neighbor_col))
    return res

from collections import deque

def bfs(starting_node):
    queue = deque([starting_node])
    visited = set([starting_node])
    while len(queue) > 0:
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor in visited:
                continue
            # Do stuff with the node if required
            # ...
            queue.append(neighbor)
            visited.add(neighbor)

Template - mono_stack

def mono_stack(insert_entries):
    stack = []
    for entry in insert_entries:
        while stack and stack[-1] <= entry:
            stack.pop()
            # Do something with the popped item here
        stack.append(entry)

Template - sliding_window_fixed

def sliding_window_fixed(input, window_size):
    ans = window = input[0:window_size]
    for right in range(window_size, len(input)):
        left = right - window_size
        remove input[left] from window
        append input[right] to window
        ans = optimal(ans, window)
    return ans

Template - sliding_window_flexible_longest

def sliding_window_flexible_longest(input):
    initialize window, ans
    left = 0
    for right in range(len(input)):
        append input[right] to window
        while invalid(window):        # update left until window is valid again
            remove input[left] from window
            left += 1
        ans = max(ans, window)        # window is guaranteed to be valid here
    return ans

Template - sliding_window_flexible_shortest

def sliding_window_flexible_shortest(input):
    initialize window, ans
    left = 0
    for right in range(len(input)):
        append input[right] to window
        while valid(window):
            ans = min(ans, window)      # window is guaranteed to be valid here
            remove input[left] from window
            left += 1
    return ans

Template - Topological Sort

def find_indegree(graph):
    indegree = { node: 0 for node in graph }  # dict
    for node in graph:
        for neighbor in graph[node]:
            indgree[neighbor] += 1
    return indegree


def topo_sort(graph):
    res = []
    q = deque()
    indegree = find_indegree(graph)
    for node in indegree:
        if indegree[node] == 0:
            q.append(node)
    while len(q) > 0:
        node = q.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    return res if len(graph) == len(res) else None

Template - trie

class Node:
    def __init__(self, value):
        self.value = value
        self.children = {}

    def insert(self, s, idx):
        # idx: index of the current character in s
        if idx != len(s):
            self.children.setdefault(s[idx], Node(s[idx]))
            self.children.get(s[idx]).insert(s, idx + 1)

Template - UnionFind

class UnionFind:
    def __init__(self):
        self.id = {}

    def find(self, x):
        y = self.id.get(x, x)
        if y != x:
            self.id[x] = y = self.find(y)
        return y

    def union(self, x, y):
        self.id[self.find(x)] = self.find(y)

Common Leetcode Python builtin module/api

# Python comparator for a given class
ListNode.__lt__ = lambda x, y: (x.val < y.val)

---

bisect.insort(list, value)
heapq.heappush(heap, value)
filter(lambda x: x>0, list)

---

heapq.heappush(heap, node)

left = list(filter(lambda x: x[1] < start, intervals)) # cast via list()
right = list(filter(lambda x: x[0] > end, intervals))

---

# Median
left = (m + n + 1) // 2
right = (m + n + 2) // 2

---

import bisect
bisect.bisect_left


# implementation of bisect.bisect_left()
def bisect_left(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid

    return lo

# similar to Leetcode-302, find left/right/top/bottom callable
# unified search api
def search(self, image: List[List[str]], start: int, end: int, check: Callable) -> int:
    while start < end:
        mid = start + (end - start) // 2
        if check(image, mid):
            end = mid
        else:
            start = mid + 1
    return start

---

# https://leetcode.ca/2015-12-25-25-Reverse-Nodes-in-k-Group/

def reverseList(head):
    pre, p = None, head
    while p:
        q = p.next
        p.next = pre
        pre = p
        p = q
    return pre

---

# https://leetcode.ca/2016-01-18-49-Group-Anagrams/
k = "".join(sorted(s))

### sorted(str) will return a list of chars
>>> a = "sdfddxyz"
>>> sorted(a)
['d', 'd', 'd', 'f', 's', 'x', 'y', 'z']
>>> "".join(sorted(a))
'dddfsxyz'

---

Int(Boolean)
return int(k == cnt + 1)

>>> a = "000"
>>> int(a)
0

>>> a = "00011"
>>> int(a)
11

>>> int(True)
1
>>> int(False)
0
>>> 1+True
2
>>> 1+False
1

---

>>> divmod(17,3)
(5, 2)

---

ans.append(f"{left}{right}")

res = [f"{' ' * (base + (i < mod))}" for i in range(cnt)]

---

>>> a = "a(b(c("
>>> a.find("(")
1
>>> a.index("(")
1
>>> a.find("(", 2)
3
>>> a.index("(", 2)
3

---

>>> list("aabcc")
['a', 'a', 'b', 'c', 'c']
>>> sorted("aabcc") # sorted on string, return list
['a', 'a', 'b', 'c', 'c']

---

>>> a = set([11,22,33])
>>> a.remove(22)
>>> a
{33, 11}

>>> a = set([11,22,33])
>>> a.discard(22)
>>> a
{33, 11}

>>> a=set([1,2,3])
>>> a.discard(555)
>>> a.remove(555)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 555


>>> s = "ababbc"
>>> set(s)
{'b', 'a', 'c'}
>>> s.count('a')
2
>>> s.count('b')
3
>>> s.split('a')
['', 'b', 'bbc']

---

list.remove(v): for list, remove by value, the first occurrence of v

    >>> a=[1,2,3]
    >>> a.remove(2) # by value
    >>> a
    [1, 3]

    >>> a=[1,2,3]
    >>> a.pop(2) # by index
    3
    >>> a
    [1, 2]

del my_dict[v]: for dict, delete by key 'v'

    # not return anything
    >>> my_dict = {'a': 1, 'b': 2, 'c': 3}
    >>> del my_dict['b']
    >>> my_dict
    {'a': 1, 'c': 3}

    # raises a KeyError if the key does not exist
    >>> my_dict = {'a': 1, 'b': 2, 'c': 3}
    >>> del my_dict['d']
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    KeyError: 'd'

my_dict.pop('b') # similar to 'del d[k]'

    # returning deleted value
    >>> my_dict = {'a': 1, 'b': 2, 'c': 3}
    >>> val = my_dict.pop('b')
    >>> print(my_dict)
    {'a': 1, 'c': 3}
    >>> print(val)
    2

    >>> item = my_dict.pop()
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: pop expected at least 1 argument, got 0

    # allows specifying a default return value if the key does not exist,
    # thus optionally preventing a KeyError.
    >>> my_dict = {'a': 1, 'b': 2, 'c': 3}
    >>> my_dict.pop('d', 'default')
    'default'
    >>> my_dict.pop('d', '12345')
    '12345'
    >>> my_dict.pop('d', 12345)
    12345

my_dict.popitem()

    my_dict = {'a': 1, 'b': 2, 'c': 3}
    item = my_dict.popitem()
    print(my_dict)  # {'a': 1, 'b': 2}
    print(item)  # ('c', 3)

filter() and lambda
    my_dict = {'a': 1, 'b': 2, 'c': 3}
    my_dict = dict(filter(lambda item: item[0] != 'b', my_dict.items()))
    print(my_dict)  # {'a': 1, 'c': 3}

---

# reversed(): returns a reverse iterator
#             but can directly re-assign back to list

>>> s = "aabbcc"
>>> reversed(s)
<reversed object at 0x108384a60>
>>> ''.join(reversed(s))
'ccbbaa'

>>> s = "aabbcc"
>>> s[::-1]
'ccbbaa'

def reverseString(self, s: List[str]) -> None:
    s[:] = s[::-1]

t[i : i + k] = reversed(t[i : i + k])

---

from functools import reduce

def singleNumber(self, nums: List[int]) -> int:
    return reduce(lambda x, y: x ^ y, nums)

---

cnt = sum(num >> i & 1 for num in nums)

---

for v in dfs(u - 2):
    for l, r in ('11', '88', '69', '96'):
        ans.append(l + v + r)
    if u != n:
        ans.append('0' + v + '0')

---

for num in reversed(nums):
  idx = bisect.bisect_left(bst, num)
  ans.append(idx)
  bisect.insort(bst, num)

---

freqs = Counter(nums)
sorted_freqs = sorted(freqs.items(), key=lambda x: x[1], reverse=True)


return sorted(cnt, key=lambda x: (-cnt[x], x))[:k]
return [v for _, v in sorted(d.items())] # d = defaultdict(list)

---

if root is None or root == p or root == q:
    return root

---

return root if left and right else (left or right)

---

# append() vs extend() vs '+'

>>> x = [1, 2, 3]
>>> x.append([4, 5])
>>> print(x)
[1, 2, 3, [4, 5]]

>>> x = [1, 2, 3]
>>> x.extend([4, 5])
>>> print(x)
[1, 2, 3, 4, 5]

>>> [1, 2, 3] + [4, 5]
[1, 2, 3, 4, 5]

---

@cache
def dfs(exp):

---

>>> from sortedcontainers import SortedList
>>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
>>> sl
SortedList(['a', 'b', 'c', 'd', 'e'])
>>> sl *= 10_000_000
>>> sl.count('c')
10000000
>>> sl[-3:]
['e', 'e', 'e']

>>> from sortedcontainers import SortedDict
>>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
>>> sd
SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.popitem(index=-1)
('c', 3)

>>> from sortedcontainers import SortedSet
>>> ss = SortedSet('abracadabra')
>>> ss
SortedSet(['a', 'b', 'c', 'd', 'r'])
>>> ss.bisect_left('c')
2


>>> a=10_000_000
>>> a
10000000
>>> b=10000000
>>> b
10000000
>>> a==b
True

---

### SortedDict vs OrderedDict
>>> from sortedcontainers import SortedDict
>>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
>>> sd
SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.popitem(index=-1)
('c', 3)


# https://docs.python.org/3/library/collections.html
>>> import collections
>>> od = collections.OrderedDict()
>>> od['a'] = 1
>>> od['b'] = 2
>>> od['c'] = 3
>>>
>>> od
OrderedDict([('a', 1), ('b', 2), ('c', 3)])
>>>
>>> od.move_to_end('a')
>>> od
OrderedDict([('b', 2), ('c', 3), ('a', 1)])
>>>
>>> od.get('a')
1
>>>
>>> od.popitem()
('a', 1)
>>> od['a'] = 1
>>> od
OrderedDict([('b', 2), ('c', 3), ('a', 1)])
>>>
>>> od.popitem(last=False)
('b', 2)
>>> od
OrderedDict([('c', 3), ('a', 1)])

---

>>> a = []
>>> a.append((3, 5))
>>> a.append((3, -5))
>>> a.append((2, -10))
>>> a.append((2, 10))
>>> a
[(3, 5), (3, -5), (2, -10), (2, 10)]

>>> a.sort()
>>> a
[(2, -10), (2, 10), (3, -5), (3, 5)]

# default sort, is sort by 1st element of each item
>>> intervals = [[111,222],[1,3],[2,6],[8,10],[15,18]]
>>> intervals.sort()
>>> intervals
[[1, 3], [2, 6], [8, 10], [15, 18], [111, 222]]

---

>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>>
>>> pq.put([1,2,3])
>>> pq.put([-10,20,30])
>>> pq.put([11,22,33])
>>>
>>> pq
<Queue.PriorityQueue instance at 0x10aec51b8>
>>> pq.queue[0][0]
-10
>>> pq.get()
[-10, 20, 30]
>>> pq.queue[0][0]
1

---

intervals.sort(key=lambda x: x[0])

---

return max(accumulate(delta))


>>> accumulate([1,2,3])
<itertools.accumulate object at 0x108f38340>
>>> list(accumulate([1,2,3]))
[1, 3, 6]
>>> list(accumulate([1,2,3], initial=0))
[0, 1, 3, 6]
>>> list(accumulate([1,2,3], initial=10))
[10, 11, 13, 16]

---

>>> from functools import reduce
>>> import operator

>>> m = 3
>>> n = 3
>>> ops = [[2,2],[3,3]]

'''
zip(*...): 
Transposes the resulting list of lists, 
effectively grouping the corresponding elements of each sublist together.
'''
>>> ops + [[m, n]]
[[2, 2], [3, 3], [3, 3]]
>>> list(zip(*ops + [[m, n]]))
[(2, 3, 3), (2, 3, 3)]
>>> list(zip(*[[2, 2], [3, 3], [3, 3]]))
[(2, 3, 3), (2, 3, 3)]
>>> list(zip([1,2,3,33,333],[4,5,6,66,666],[7,8,9,99,999]))
[(1, 4, 7), (2, 5, 8), (3, 6, 9), (33, 66, 99), (333, 666, 999)]


>>> map(min, zip(*ops + [[m, n]]))
<map object at 0x10ff58880>
>>> list(map(min, zip(*ops + [[m, n]])))
[2, 2]

>>> reduce(operator.mul, map(min, zip(*ops + [[m, n]])))
4
>>> reduce(operator.mul,[2,3,4,5])
120

---

>>> from operator import *
>>> add(1,2)
3
>>> sub(1,2)
-1
>>> mul(1,2)
2
>>> div(1,2)
0

---

>>> numbers = [1, 2, 3, 4, 5]
>>> squared_numbers = map(lambda x: x ** 2, numbers)
>>> map(lambda x: x ** 2, numbers)
<map object at 0x10ff58ca0>
>>> list(map(lambda x: x ** 2, numbers))
[1, 4, 9, 16, 25]

---

min_heap = list(filter(lambda slot: slot[1] - slot[0] >= duration, slots1 + slots2))

---

from collections import Counter

return sum(v % 2 for v in Counter(s).values()) <= 1


>>> c=Counter({'a':1,'b':2}) # note: initialization
>>> c
Counter({'b': 2, 'a': 1})
>>> c.items()
dict_items([('a', 1), ('b', 2)])
>>> c.keys()
dict_keys(['a', 'b'])
>>> c.values()
dict_values([1, 2])


>>> c
Counter({'a': 1, 'c': 1, 'b': 1})
>>> c.pop(2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 2
>>>
>>> c.pop('c')
1
>>> c
Counter({'a': 1, 'b': 1})

---

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d["a"]=1
>>> d["b"]=2
>>> d
defaultdict(<class 'list'>, {'a': 1, 'b': 2})


>>> d.values()
dict_values([1, 2])
>>> list(d.values()) # convert to list
[1, 2]

---

single_perm=[]
single_perm.insert(index, num)
tmp_list.append(single_perm.copy())
single_perm.pop(index)


>>> my_list = [2, 3, 4]
>>> my_list.insert(0, 1)  # Insert 1 at the head of the list
>>> print(my_list)  # Output: [1, 2, 3, 4]

# cannot just deque(1), must be deque([1])
>>> a = deque([1, 2, 3])
>>> a.insert(0, 555)
>>> a
deque([555, 1, 2, 3])

---

q = collections.deque()
heapq.heappush(heap, -t)

---

return len(pattern) == len(s) and len(set(zip(pattern, s))) == len(set(pattern)) == len(set(s))

return len(set(nums)) < len(nums)


return any(dfs(i, j, 0) for i in range(m) for j in range(n))

>>> a="abc"
>>> a[1:99]
'bc'
>>> a[:0]
''

---

# inside a dfs(), nonlocal needed if 'prev' being modified
nonlocal prev, first, second
prev = root

---

envelopes.sort(key=lambda key: (key[0], -key[1]))

---

random.choice(self.a)

---

>>> a=set()
>>> a.add(1)
>>> a.append(2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'append'
>>> a = set([1,1,2,3])
>>> a
{1, 2, 3}
>>> a.pop()
1
>>> a
{2, 3}


>>> a = set([1,2,3])
>>> a.pop()
1
>>> a.pop()
2
>>> a.pop()
3
>>> a.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'pop from an empty set'


>>> a = [1,1,2,3,4,5,6]
>>> a.count(1)
2
>>> a.pop()
6
>>> a.pop()
5
>>> a.pop()
4
>>> a.pop()
3
>>> a.pop()
2
>>> a.pop()
1
>>> a.pop()
1
>>> a.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list


>>> a = deque([1,1,2,3,4,5,6])
>>> a.pop()
6
>>> a.popleft()
1
>>> a.popleft()
1
>>> a.popleft()
2
>>> a.popleft()
3
>>> a.popleft()
4
>>> a.popleft()
5

---

delimiter = s.index("#", i)

---

ans.append('{:4}'.format(len(s)) + s)

>>> s = 'abcde'
>>> '{:4}'.format(len(s)) + s
'   5abcde'
>>>
>>> '{:4}'.format(333)
' 333'
>>>
>>> '{:4}'.format(1234)
'1234'
>>> '{:4}'.format(12345)
'12345'

>>> '{0:4}'.format(12345)
'12345'
>>> '{1:4}'.format(12345)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: Replacement index 1 out of range for positional args tuple
>>> '{1:4}'.format(12345, 678910)
'678910'
>>> '{:4}'.format(12345, 678910)
'12345'
>>> '{0:4}'.format(12345, 678910)
'12345'

---

>>> 1e9
1000000000.0
>>> int(1e9 + 7)
1000000007
1e9 is a method of writing the number 1,000,000,000 in scientific notation, and is short for 1*(10^9)

---

>>> a=[1,2,3,1,2,3,1,2,3]
>>> bisect.bisect_left(a, 2)
1
>>> bisect.bisect_right(a, 2)
8

bisect.insort(bst, num)

---

from threading import Semaphore

    self.fizzSemaphore = Semaphore(0)
    self.buzzSemaphore = Semaphore(0)
    self.fizzbuzzSemaphore = Semaphore(0)
    self.numberSemaphore = Semaphore(1)

    self.numberSemaphore.acquire()
    self.numberSemaphore.release()

---

>>> float('-inf')+1
-inf
>>> float('-inf')-1
-inf

---

return [f'{v} {s}' for s, v in cnt.items()]

---

countDownLatch1 = new CountDownLatch(1);
countDownLatch2 = new CountDownLatch(1);
countDownLatch1.await();
countDownLatch2.countDown();

---

p = list(range(n)) # parent[], uf

---

>>> a = ['aaa', 'bbb', 'ccc', 'aaa']
>>> a.count('aaa')
2
>>> a.count('zzz')
0

---

# from interview question, print to console x-y map, and modify some of coordinates to be star *
>>> a = "abcdef"
>>> a[2]="x"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment


>>> l=list(a)
>>> l[2]="x"
>>> "".join(l)
'abxdef'

---

import abc
from abc import ABC, abstractmethod

class Node(ABC):
    @abstractmethod
    # define your fields here
    def evaluate(self) -> int:
        pass


class MyNode(Node):
    def __init__(self, val):
        self.val = val

    def evaluate(self) -> int:
        return self.val

---

from concurrent.futures import ThreadPoolExecutor

	def scrape_page(self, url):
		try:
			res = requests.get(url, timeout=(3, 30))
			return res
		except requests.RequestException:
			return

self.pool = ThreadPoolExecutor(max_workers=5)
self.pool.submit(self.scrape_page, "https://a.b.c")

---

vals = data.split(',')
first = vals.pop(0)

>>> nums=[4,5,5,6]
>>> mid = (len(nums) - 1) // 2
>>> mid
1

>>> nums[mid::-1]
[5, 4]
>>> nums[:mid:-1]
[6, 5]
>>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]
>>> nums
[5, 6, 4, 5]

>>> nums[mid::1]
[5, 5, 6]
>>> nums[mid:]
[5, 5, 6]
>>> nums[:mid:1]
[4]
>>> nums[:mid]
[4]

---

>>> from itertools import pairwise
>>> a = ['a','b','c']
>>> pairwise(a)
<itertools.pairwise object at 0x108458730>
>>> list(pairwise(a))
[('a', 'b'), ('b', 'c')]

# same as pairwise()
>>> zip(a, a[1:])
[('a', 'b'), ('b', 'c')]

---

>>> inDegree = {'a':11, 'b':22, 'c':33}

>>> [print(c) for c in inDegree.keys()]
a
b
c
[None, None, None]

# same as for c in inDegree.keys()
>>> [print(c) for c in inDegree]
a
b
c
[None, None, None]

>>> [print(c) for c in inDegree.values()]
11
22
33
[None, None, None]

>>> [print(c) for c in inDegree.items()]
('a', 11)
('b', 22)
('c', 33)
[None, None, None]

>>> len(inDegree)
3

---

>>> l,r="ab"
>>> l
'a'
>>> r
'b'

>>> l,r="abc"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: too many values to unpack (expected 2)

---

j = next(j for j in range(len(nums)-1, i, -1) if nums[j] > nums[i])

>>> next(i for i in range(10))
0
>>> next(i for i in reversed(range(10)))
9

---

>>> ord('c')
99
>>> chr(98)
'b'


>>> int('1.0')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: '1.0'
>>> int('1')
1

>>> float(int('1'))
1.0
>>> float('1.0')
1.0

---

def partition(self, nums: List[int], lo: int, hi: int) -> int:
    pivot, l, r = nums[lo], lo + 1, hi
    while l <= r:
        if nums[l] < pivot and nums[r] > pivot:
            # larger num at left of pivot, easier to count for k-th lagest
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
        if nums[l] >= pivot:
            l += 1
        if nums[r] <= pivot:
            r -= 1
    # use nums[l] will lead to infinate looping
    nums[lo], nums[r] = nums[r], nums[lo]
    # possible there is duplicated num, but will be covered here
    return r

---

nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]

---

>>> 'abc' < 'def'
True
>>> 'abc' < 'aef'
True
>>> 'abc' < 'aaf'
False

---

while i >= 0 or j >= 0 or c:
    a = 0 if i < 0 else int(num1[i])
    b = 0 if j < 0 else int(num2[j])
    c, v = divmod(a + b + c, 10) # nice
    ans.append(str(v))

---

from typing import Callable

def greet(name: str) -> str:
    return f"Hello, {name}!"

def process(func: Callable[[str], str], value: str) -> str:
    return func(value)

result = process(greet, "Alice")
print(result)  # Output: Hello, Alice!

---

from typing import Callable
class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        right = self.search(image, y + 1, n, lambda col: not self.check_col(image, col))

    def check_col(self, image: List[List[str]], col: int) -> bool:
        return any(row[col] == '1' for row in image)    

---

  caller = lambda x, y: x >= y if a >= 0 else x <= y

  while i <= j:
      left_val = self.calculate(nums[i], a, b, c)
      right_val = self.calculate(nums[j], a, b, c)

      if caller(left_val, right_val):
          result[idx] = left_val
          i += 1

---

medians.append((window[k // 2] + window[~(k // 2)]) / 2.)

---

>>> s="abcdefg"
>>> [print(i,",",c) for i, c in enumerate(s, 1)]
1 , a
2 , b
3 , c
4 , d
5 , e
6 , f
7 , g
[None, None, None, None, None, None, None]
>>>

---

>>> import math
>>> a = math.inf
>>> a
inf

>>> x = float('-inf')
>>> y = float('inf')
>>> print(x < y)  # Output: True
True
>>>
>>> z = -math.inf
>>> x==z
True

---

>>> cur = [1]
>>> len(cur) - 1
0
>>> ( len(cur) - 1 or 1 )
1

---

# api: string.ljust(width[, fillchar])

>>> "Hello".ljust(10)
'Hello     '
>>> "Hello".ljust(10, '-')
'Hello-----'
>>> "Hello".ljust(2)
'Hello'

>>> "Hello World".ljust(20)
'Hello World         '
>>> "Hello World".ljust(20, '-')
'Hello World---------'


# api: string.rjust(width[, fillchar])
>>> "Hello".rjust(10)
'     Hello'
>>> "Hello".rjust(10, '-')
'-----Hello'
>>> "Hello".rjust(2)
'Hello'

>>> "Hello World".rjust(20)
'         Hello World'
>>> "Hello World".rjust(20, '-')
'---------Hello World'

---

>>> nums = ["a", "a", "b", "c", "c"]

>>> cnt = Counter(nums)
>>> cnt
Counter({'a': 2, 'c': 2, 'b': 1})

# default to keys
>>> sorted_freqs = sorted(cnt, key=lambda x: (-cnt[x], x))
>>> sorted_freqs
['a', 'c', 'b']

---

set1 = {1, 2, 3}
set2 = {2, 3, 4}


intersection = set1 & set2
print(intersection)  # Output: {2, 3}
intersection = set1.intersection(set2)
print(intersection)  # Output: {2, 3}


union = set1 | set2
print(union)  # Output: {1, 2, 3, 4}
union = set1.union(set2)
print(union)  # Output: {1, 2, 3, 4}


difference = set1 - set2
print(difference)  # Output: {1}
difference = set1.difference(set2)
print(difference)  # Output: {1}


symmetric_difference = set1 ^ set2
print(symmetric_difference)  # Output: {1, 4}
symmetric_difference = set1.symmetric_difference(set2)
print(symmetric_difference)  # Output: {1, 4}

---

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def dfs(i, j, x):
            if i >= j: # i==j, then it's an odd one, not valid
                return 0
            if s[i] == s[j] and s[i] != x:
                return dfs(i + 1, j - 1, s[i]) + 2
            return max(dfs(i + 1, j, x), dfs(i, j - 1, x))

        ans = dfs(0, len(s) - 1, '')
        dfs.cache_clear() # <=== memory optimization
        return ans

---

>>> delta = 1
>>> 1+1==2
True
>>> 1+1==2 and delta
1
>>>
>>>
>>> delta = -1
>>> 1+1==2 and delta
-1
>>>
>>> delta = -100
>>> 1+1==2 and delta
-100
>>>
>>> delta = -100
>>> 1+1==99 and delta
False
>>>

Some notes as my own reminders

---

# If there are remaining characters in inDegree, it means there's a cycle
if any(inDegree.values()):
    return ''

---

for num in nums:
    new_res = []
    for perm in res:
        for i in range(len(perm) + 1):
            if i > 0 and perm[i - 1] == num:
                break # skip duplicate
            new_perm = perm[:i] + [num] + perm[i:]
            # or perm.insert(index, num), like in lc-46
            new_res.append(new_perm)
    res = new_res

---

# unified search api
def search(self, image: List[List[str]], start: int, end: int, check: Callable) -> int:
    while start < end:
        mid = start + (end - start) // 2
        if check(image, mid):
            end = mid
        else:
            start = mid + 1
    return start

---

first = vals.pop(0)

>>> a = [1,2,3]
>>> a.pop()
3
>>> a
[1, 2]

>>> a = [1,2,3]
>>> a.pop(0)
1
>>> a
[2, 3]

---

# next() default value
>>> b = (i for i in range (10, -1, -1) if i < 0)

>>> next(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

>>> next(b, -1)
-1

---

# good dp initialization
def combinationSum4(self, nums: List[int], target: int) -> int:
    f = [1] + [0] * target

---

# without this del, it will be huge/duplicated loop
# over time limit for input [7,7,7,7,7,....7,7]
del idx[v] # avoid dedup

---

return mi < root.val < ma and dfs ()

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

.