0%

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[0] = 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 »

Ranking: 1197 / 15151 😔😂😭

Q1. 1518. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def numWaterBottles(self, A: int, B: int) -> int:
ret = 0
while A:
if A >= B:
drink = (A // B) * B
else:
drink = A
ret += drink
A = A - drink + drink // B
return ret
Read more »