# 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 ()


>>> t = [11,22,33,44,55]
>>>
>>>
>>> t[1:3][::-1]
[33, 22]
>>>
>>> reversed(t[1:3])
<list_reverseiterator object at 0x109022950>
>>>
>>> list(reversed(t[1:3]))
[33, 22]























































































































































































































































































.