0%

If all you have is a hammer, everything looks like a nail

- Abraham Maslow, 1962

List, Stack, LinkedList

Heap, Priority Queue

Sliding Window

Monotonic Stack

Monotonic Queue

Rare technique

  1. KMP
  2. Manacher’s algorithm

Tree

DFS

BFS

Trie

Advanced Tree

Binary Index Tree (Fenwick Tree)

Segment Tree

Self-Balanced Tree, RB Tree

Union-Find

Graph

DFS/BFS

Cycle Detection

Topologic Sort

Euler Path

Shortest Path

Dijkstra

Bellman-Ford

Floyd-Warshall

Minimal Spanning Tree

Kruskal’s Algorithm

Prim’s Algorithm

Tarjan’s Algorithm

Strong Connected Component

Cutting Edge

Cutting Point

Dynamic Programming

Bit Mask

##

uncategorized

  1. Binary Lifting

What is a Graph

Non-directed

Directed

Cycle Detection

Non-directed Graph

Union-Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class UF:
def __init__(self):
self.uf = {}

def find(self, x: int) -> int:
uf = self.uf
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = self.find(uf[x])
return uf[x]

def union(self, x: int, y: int) -> None:
# x -> y
uf = self.uf
uf[self.find(x)] = self.find(y)

def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:
uf = UF()

for u, v in edges:
if uf.find(u) == uf.find(v):
return True
uf.union(u, v)

return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 1), (2, 1), (1, 3)])

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:

def dfs(u: int, p: int) -> bool:
visited.add(u)

for v in graph[u]:
if v == p: continue
if v in visited or dfs(v, u):
return True

return False

graph, visited = defaultdict(set), set()

for u, v in edges:
graph[u].add(v)
graph[v].add(u)

for u in range(n):
if u not in visited and dfs(u, None):
return True
return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 1), (2, 1), (1, 3)])

Directed Graph

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:

def dfs(u: int) -> bool:
visited.add(u), stack.add(u)

for v in graph[u]:
if v in stack or v not in visited and dfs(v):
return True

stack.remove(u)
return False

graph, visited, stack = defaultdict(set), set(), set()

for u, v in edges:
graph[u].add(v)

for u in range(n):
if u not in visited and dfs(u):
return True
return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 2), (0, 1), (2, 1), (1, 3)])

Euler Path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_euler_path(start: int, edges: List[Tuple[int, int]]) -> List[int]:
# Assume euler path does exist
def dfs(u):
while graph[u]:
v = graph[u].pop()
dfs(v)
ret.append(u)

graph, ret = defaultdict(set), []
for u, v in edges:
graph[u].add(v)

dfs(start)
return ret[::-1]

print(find_euler_path(0, [(0, 1), (1, 0), (1, 2), (2, 3), (3, 1), (1, 4)] ))

Shortest Path

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from sortedcontainers import SortedList
def dijkstra(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> List[int]:
graph, dist, prev = defaultdict(dict), defaultdict(lambda: math.inf), {}

for u, v, w in edges:
graph[u][v] = w

q = SortedList([(0, begin)])
dist[begin] = 0
while q:
_, u = q.pop(0)
for v, w in graph[u].items():
if dist[v] > dist[u] + w:
q.discard((dist[v], v)) # this will reduce the time complexity from O(E*log(V)) to O(V*log(V))
prev[v] = u
dist[v] = dist[u] + w
q.add((dist[v], v))

if dist[end] == math.inf:
return []

def bt(cur):
if cur == begin:
return [begin]
return bt(prev[cur]) + [cur]
return bt(end)

print(dijkstra(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Bellman Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def bellman_ford(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> List[int]:
dist = defaultdict(lambda: math.inf)
dist[begin], prev = 0, {}

for _ in range(n):
upd = 0
for u, v, w in edges:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
prev[v] = u
upd += 1
if not upd:
break

for u, v, w in edges:
if dist[u] + w < dist[v]:
raise Exception('Negative cycle')

def bt(u):
if u == begin:
return [begin]
return bt(prev[u]) + [u]
return bt(end)

print(bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Floyd Warshall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def floyd_warshall(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> int:
dist = defaultdict(lambda: math.inf)

for u, v, w in edges:
dist[(u, v)] = w

for k in range(n):
for u in range(n):
for v in range(n):
if dist[(u, k)] + dist[(k, v)] < dist[(u, v)]:
dist[(u, v)] = dist[(u, k)] + dist[(k, v)]

return dist[(begin, end)]

print(floyd_warshall(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Minimal Spanning Tree

Kruskal’s method

1
2
3
4
5
6
7
8
9
10
11
def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> int:
uf, ret = UF(), []

for u, v, w in sorted(edges, key=lambda x: x[2]):
if uf.find(u) != uf.find(v):
ret.append((u, v, w))
uf.union(u, v)

return ret if len(set(map(uf.find, range(n)))) == 1 else []

print(kruskal(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Prim’s method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from sortedcontainers import SortedList
def prim(n: int, edges: List[Tuple[int, int, int]]) -> int:
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = w

start = 0
pq, ret, visited, prev = SortedList([(0, start, None)]), [], set(), {}

while pq:
if len(visited) == n:
break
w, u, p = pq.pop(0)
if u in visited: continue

visited.add(u), ret.append((p, u, w))

for v, w in graph[u].items():
if v in visited: continue
if v in prev and prev[v][1] >= w:
pq.remove((prev[v][1], v, prev[v][0]))
prev[v] = (u, w)
pq.add((w, v, u))

return ret[1:] if len(visited) == n else []

print(prim(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Tarjan’s algorithm

Strong Connected Component

Cutting Edge

Cutting Vertex

Q1. 1592. Rearrange Spaces Between Words

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def reorderSpaces(self, text: str) -> str:
words = text.split()
spaces, n = text.count(' '), len(words)
ret = ''

for i, word in enumerate(words):
ret += word
if n > 1 and i != n-1:
ret += ' ' * (spaces // (n-1))

return ret + ' ' * ((spaces % (n-1)) if n>1 else spaces)
Read more »

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Fraction:
def __init__(self, numerator: int, denominator: int):
self.numerator = numerator
self.denominator = denominator

def __str__(self):
return f'{self.numerator} / {self.denominator}'

def __lt__(self, rhs: Fraction):
l, r = self.numerator * rhs.denominator, self.denominator * rhs.numerator
return l < r

def __add__(self, rhs: Fraction):
numerator, denominator = self.numerator * rhs.denominator + rhs.numerator * self.denominator, \
self.denominator * rhs.denominator
gcd_val = math.gcd(numerator, denominator)
return Fraction(numerator // gcd_val, denominator // gcd_val)

def __sub__(self, rhs: Fraction):
numerator, denominator = rhs.numerator, rhs.denominator
return self.__add__(Fraction(-numerator, denominator))

Prerequisite

  1. What is a binary-heap
  2. It takes O(N) to heapify an array contains N integer

N*Log(K)

1
2
3
4
5
6
7
def get_k_smallest(k: int, arr: List[int]):
heap = []
for num in arr:
heapq.heappush(heap, -num) # we push -num as we want to build a max-heap
if len(heap) > k:
heapq.heappop(heap)
return [-num for num in heap]

K*Log(N)

1
2
3
def get_k_smallest(k: int, arr: List[int]):
heapq.heapify(arr)
return [heapq.heappop(arr) for i in range(k)]

K*Log(K)

1
2
3
4
5
6
7
8
9
10
def get_k_smallest(k: int, arr: List[int]):
heapq.heapify(arr)
heap = [(arr[0], 0)]
ret = []
for _ in range(k):
num, idx = heapq.heappop(heap)
ret.append(num)
heapq.heappush(heap, (arr[idx*2+1], idx*2+1))
heapq.heappush(heap, (arr[idx*2+2], idx*2+2))
return ret

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import heapq
import timeit


def timer(function):
def new_function(*args, **kw):
start_time = timeit.default_timer()
ret = function(*args, **kw)
elapsed = timeit.default_timer() - start_time
print('Function "{name}" took {time} seconds to complete.'.format(name=function.__name__, time=elapsed))
return ret
return new_function

@timer
def addition():
total = 0
for i in range(0,1000000):
total += i
return total



@timer
def get_k_smallest1(k: int, arr: List[int]):
heap = []
for num in arr:
heapq.heappush(heap, -num) # we push -num as we want to build a max-heap
if len(heap) > k:
heapq.heappop(heap)
return [-num for num in heap]


@timer
def get_k_smallest2(k: int, arr: List[int]):
heapq.heapify(arr)
return [heapq.heappop(arr) for i in range(k)]


@timer
def get_k_smallest3(k: int, arr: List[int]):
heapq.heapify(arr)
heap = [(arr[0], 0)]
ret = []
for _ in range(k):
num, idx = heapq.heappop(heap)
ret.append(num)
heapq.heappush(heap, (arr[idx*2+1], idx*2+1))
heapq.heappush(heap, (arr[idx*2+2], idx*2+2))
return ret

k = 5
arr = [randrange(0, 100000000) for i in range(10000000)]

ans = set(sorted(arr)[:k])
assert ans == set(get_k_smallest1(k, list(arr)))
assert ans == set(get_k_smallest2(k, list(arr)))
assert ans == set(get_k_smallest3(k, list(arr)))

'''
» /usr/local/opt/python@3.8/bin/python3.8 /Users/yongcao/Program/tmp/py.py yongs-MBP
Function "get_k_smallest1" took 3.168419736999999 seconds to complete.
Function "get_k_smallest2" took 0.3814774750000005 seconds to complete.
Function "get_k_smallest3" took 0.37742361599999974 seconds to complete.
'''

Find Strong Connected Components (SCC)

Video

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def find_scc(n: int, edges: List[List[int]]):
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

ids, low = [-1] * n, [-1] * n
stack, in_stack = [], [False] * n
id_max = 0

def dfs(u):
nonlocal id_max
stack.append(u)
in_stack[u] = True
ids[u] = low[u] = id_max
id_max += 1

for v in graph[u]:
if ids[v] == -1: dfs(v)
if in_stack[v]:
low[u] = min(low[u], low[v])

if low[u] == ids[u]:
while True:
node = stack.pop()
in_stack[node] = False
if node == u: break

for i in range(n):
if ids[i] == -1:
dfs(i)
return low
Read more »

Undirected Graph

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def hasCycle(n: int, edges: List[List]) -> bool:
def dfs(u, parent):
visited.add(u)
for v in graph[u]:
if v == parent: continue
if v in visited or dfs(v, u):
return True
return False

graph, visited = defaultdict(set), set()
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

for u in range(n):
if u not in visited and dfs(u, None):
return True
return False
Read more »

Q1. 1534. Count Good Triplets

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
Where |x| denotes the absolute value of x.

Return the number of good triplets.

Note

From constrain 3 <= arr.length <= 100, we know this can be solved by complete search aka Brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def countGoodTriplets(self, A: List[int], a: int, b: int, c: int) -> int:
ret = 0
def dfs(arr, idx):
nonlocal ret
if len(arr) == 3:
if abs(arr[0]-arr[1]) <= a and abs(arr[1]-arr[2]) <= b and abs(arr[0]-arr[2]) <= c:
ret += 1
return
for i in range(idx, len(A)):
dfs(arr+[A[i]], i+1)
dfs([], 0)
return ret
Read more »

Ranking: 256 / 14309 🧐🤔😑

Q1. 1528. Shuffle String

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

1
2
3
4
5
6
class Solution:
def restoreString(self, s: str, indices: List[int]) -> str:
ret = [None] * len(s)
for i, c in zip(indices, s):
ret[i] = c
return ''.join(ret)
Read more »