Algorithm

Author: TickQ
Date: November 13, 2024
Version: 1.0

Let’s get 4K
 Contents

Chapter 1 Complexity 1
1.1 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Telescoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Chapter 2 Correctness 8
2.1 Loop Invariant & Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Chapter 3 Sorting Algorithms 10

3.1 Comparison Based Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Unstable Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Stable Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5 Complexity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Chapter 4 Divide and Conquer 16

4.1 Hoare’s Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Quick Select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Median of Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4 Dutch National Flag Partitioning (DNF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.5 Complexity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Chapter 5 Graphs and Shortest Distance 20

5.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 How to Represent Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 BFS and DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.5 Directed Acyclic Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.6 Complexity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Chapter 6 Minimum Spanning Tree 29

6.1 Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.3 Complexity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Chapter 7 Dynamic Programming 33

7.1 LeetCode 198: House Robber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.2 LeetCode 62: Unique Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
 CONTENTS

7.3 LeetCode 300: Longest Increasing Subsequence . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.4 LeetCode 1143: Longest Common Subsequence . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.5 LeetCode 72: Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.6 LeetCode 53: Maximum Subarray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Chapter 8 DP Graph Algorithm 42

8.1 Bellman Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.2 Floyd Warshall Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.3 Complexity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Chapter 9 Flow Network 49

9.1 Residual Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
9.2 Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9.3 Min-Cut Max-Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.4 Feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.5 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Chapter 10 String Retrieval Data Structures 55

10.1 Prefix Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
10.2 Suffix Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10.3 Suffix Array and Prefix Doubling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Chapter 11 Hashing 61
11.1 Collision Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11.2 Perfect Hash Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Chapter 12 AVL Tree 63

12.1 Balance Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
12.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
12.3 Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Chapter 13 Revision 66

ii
 Chapter 1 Complexity

There are many ways to solve problems using different algorithms in Computer Science, but how do we
identify which is better than the other? Does one work better in a specific situation? Therefore, we have two
methods to evaluate and compare which algorithm is more optimal. The two methods used are time complexity
and space complexity. In short words:
Time Complexity: The time taken by an algorithm to run based on input
Space Complexity: The amount of memory needed by the algorithm to solve given problem. We will
determine input space complexity, auxiliary space complexity and total space complexity.

1.1 Time Complexity

It takes time to get used to figuring out the time complexity. There are multiple ways to represent the time
complexity: Big-O notation, Big-Theta notation and Big-Omega notation.
Big-O: The upper bound of an algorithm’s growth rate
Big-Theta: The tight bound of an algorithm’s growth rate (lower and upper bound)
Big-Omega: The lower bound of an algorithm’s growth rate
Big-O is highlighted because we will often use it. Just as a revision, we will start with some easy ones first, then
we will move on to other techniques like telescoping and master theorem.

1.1.1 Example 1

for i in range(n):
print("Hello")

In this example, we have a for loop that will loop for n times, print ”Hello” for n times and halts. So the time
complexity is O(n).

1.1.2 Example 2

for i in range(n):
for j in range(n/2):
print("Hello")

n
In this example, we have a for loop that will loop for n times, and we have another inner loop that loops for 2
2
times. n ∗ ( n2 ) is n2 so the complexity is still O(n2 )

1.1.3 Example 3

def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
 1.2 Recurrence Relation

In this example, we have a function to compute the factorial of an input n. The base case is 0, and it will
recursively call factorial until it reaches the base case. Observe that this function will call itself for n times
recursively because of factorial(n-1). So the complexity is O(n)

1.1.4 Example 4

def power(x, n):

if n == 0:
return 1
elif n == 1:
return x
elif n % 2 == 0:
return power(x*x, n//2)
elif n % 2 == 1:
return power(x*x, n//2) * x

Observe that only n will determine how many times the function will call itself, we can see that n is divided by
two every time, so this function will be O(logN )

1.2 Recurrence Relation

Recurrence relations are often used to describe the time complexity in terms of the time required for smaller
subproblem. For example, the recurrence relation for Example 4 will be
T(0) = a
T(1) = b
T(N) = T(N//2) + c

a, b and c all means constant operations. As we can see, return a constant number or perform multiplications are
constant. With recurrence relationship, we can analyse the time complexity easily. The two ways of analysing
complexity are telescoping and master theorem.

1.3 Telescoping

1.3.1 Example 1
Given recurrence relationship of
T(0) = a
T(1) = b
T(N) = T(N-1) + c

We know that T(N-1) will move towards the base case, now we will move on to next step. If we want to find
T(N-1), just sub N-1 into the function. Then it will be T(N-1) = T(N-2) + c, we can then substitute T(N-1) into
T(N)
T(N-1) = T(N-2) + c
T(N) = T(N-1) + c
T(N) = [T(N-2) + c] + c

2
 1.3 Telescoping

If we go on
T(0) = a
T(1) = b
T(N) = [[T(N-3) + c] + c] + c

We can observe a pattern here, there are 3 c’s and it is N-3. If we go on to the next level, it will be 4 c’s and N-4,
so we can change the formula to
T(0) = a
T(1) = b
T(N) = T(N-k) + kc

Now, we just need to make T(N-k) the base case. For it to reach the base case, it must be either T(0) or T(1), let’s
choose 0
N-k = 0
k = N

T(N) = T(N-N) + Nc
= a + Nc

We know that a and c are both constant, so it is essentially O(N )

1.3.2 Example 2

T(0) = a
T(1) = b
T(N) = T(N//2) + c

T(N//2) = T(N//4) + c
T(N) = [T(N//4) + c] + c

T(N//4) = T(N//8) + c
T(N) = [[ T(N//8) + c] + c] + c

T(N) = T(N//(2^k)) + kc

N//2^k = 1
N = 2^k
log_2(N) = log_2(2^k)
k = log_2(N)

T(N) = T(N//(2^(log_2(N))) + log_2(N)c

T(N) = T(1) + log_2(N)c
T(N) = b + log_2(N)c

N
The difference here is that we need to use base case 1 instead of 0, because we can’t find an answer for 2k
= 0.
So the complexity will be O(logN )

3
 1.4 Master Theorem

1.3.3 Example 3

T(0) = a
T(N) = T(N-1) + cN^3

T(N) = T(N-1) + cN^3

= [T(N-2) + c(N-1)^3] + cN^3
= [[T(N-3) + c(N-2)^3] + c(N-1)^3] + cN^3
= T(N-3) + c(N-2)^3 + c(N-1)^3 + cN^3
= T(N-3) + c[(N-2)^3 + (N-1)^3 + N^3]
= T(N-k) + c[N^4]

N-k = 0
N = k

T(N) = T(N-N) + c[N^4]

= a + cN^4

If your confused on how it became N 4 , just see it as we have N 3 , and we are adding N of them together, so
N ∗ N 3 = N 4 . So the complexity will be O(N 4 )

1.3.4 Tips
Sometimes you don’t have to work everything out, we can figure out the complexity half way through
when we know that some will definitely dominate the other

1.4 Master Theorem

Note that this is only applicable for T ( Nk ). For T (N − k) you must use telescoping. For this one just
memorize the formula:

( )
T (N ) = a T Nb + f (N )
f (N ) = O(N k · logp N )
logb a > k: O(N logb a )
logb a = k
p > −1: O(N k · logp+1 N )
p = −1: O(N k · log log N )
p < −1: O(N k · 1)
logb a < k
p > −1: O(N k · logp N )
p = −1: O(N k · 1)
p < −1: O(N k · 1)
After memorizing/used to it, we can figure out the complexity in 5 seconds.

4
 1.5 Space Complexity

1.4.1 How to memorize

Let x be logb a
If x > k, it means x dominates so it will just be N x
If x = k, it means need to consider both, so N k log p+1 N . The +1 is because we need to consider x
If x < k, it means f (N ) dominates so it will just be O(N k log p N )
The rest mostly N k , only different is N k · loglogN . However, these cases are very rare, so just memorize
the above three

1.4.2 Example 1

T(0) = a
T(1) = b
T(N) = T(N//2) + c

k = 0
p = 0
a = 1
b = 2

log_2(1) = 0
0 = 0
--> Go to second case
p > -1
--> Go to first case
= O(N^0 log^(0+1)N)

So the complexity will be O(logN )

1.4.3 Example 2

T(0) = a
T(1) = b
T(N) = 2T(N//2) + n^2c

k = 2
p = 0
a = 2
b = 2

log_2(2) = 1
1 < 2
--> Go to third case
p > -1
--> Go to first case
= O(N^2 log^(0)N)

So the complexity will be O(N 2 )

5
 1.5 Space Complexity

1.5 Space Complexity

For space complexity, we need to figure out three parts: input space complexity, auxiliary space complexity
and total space complexity (input + auxiliary). Space is actually more important that time because we can wait,
but the space is limited.

1.5.1 Input Space Complexity

The input space complexity is determined by what is being passed to the current function. It could be a
number, a list of numbers or a string. Note that we have to always specify what N is while analyzing.
A number O(1)
A list of numbers O(N ), where N is the number of items in the list
A string O(N ), where N is the number of characters in the string
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)

In our previous factorial function, the input space is O(1) because n is essentially a positive number.

1.5.2 Auxiliary Space Complexity

Auxiliary space is the extra space that we need to use while running the algorithm. If the input space is
O(N ) and the total space is O(N ), the auxiliary space can be O(1), O(logN ) or O(N ) and it still will not affect
the total space complexity. However, we definitely want to choose O(1) because it saves memory. Hence, this
is why we want to analyze the auxiliary space complexity.

[Link] Example 1

for i in range(n):
for j in range(n/2):
print("Hello")

This example has O(1) auxiliary space, because we are simply creating two new variables i and j

[Link] Example 2

lst = [None] for _ in range(n)

for i in range(n):
for j in range(n/2):
print("Hello")

This example has O(N ) auxiliary space, because we have created a list of N None.

6
 1.5 Space Complexity

[Link] In-place
An in-place algorithm means that we have O(1) auxiliary space. It doesn’t guarantee that we are not using
extra space, but it guarantees that we are only using constant, O(1) space. For example, when we are running
selection sort, we have two loops, and we will have a min variable to figure out the minimum element in every
iteration. min is using extra space but it is constant, so selection sort is a in-place algorithm.
Let’s look back at the factorial example. Is this an in-place algorithm?
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)

The answer is No! When we perform recursion, each call is stored in the recursion stack, so we are using extra
spaces. In this case, the function will have O(logN ) auxiliary space because we will have logN calls until we
have reached the base case. So anything involving recursion is not in-place.

1.5.3 Total Space Complexity

Total space complexity is input space + auxiliary space, and we will only choose the dominating one.
Input = O(N ), aux = O(1), total = O(N )
Input = O(N ), aux = O(N ), total = O(N )
Input = O(N ), aux = O(N 2 ), total = O(N 2 )

1.5.4 Time and Space

Is this possible?
Time complexity: O(N)
Total space complexity: O(N^2)

The answer is No! Time complexity can never be lower than space complexity, because we need more or equal
time to create the extra spaces/process the input items. So time complexity must ≥ space complexity

7
 Chapter 2 Correctness

When we write an algorithm, how do we determine if it is correct or not? There are two proofs of correct-
ness: loop invariant and termination. Recall that an algorithm must halt for any input.

2.1 Loop Invariant & Termination

Loop invariant is what doesn’t change but help you reach the output. Termination can determine whether
the function can reach the base case and ensure the loop will be exited. When we analyze loop invariant, we
have to analyze the loop entry invariant, start invariant, maintenance invariant and end invariant (termination).
def func(my_list):
...
# Loop entry Invariant
for i in range(len(my_list)):
# Start Invariant
...
...
# Maintenance Invariant
# End Invariant

2.1.1 Example 1

def selection_sort(my_list):
# Loop entry Invariant
for i in range(len(my_list)):
# Start Invariant
smallest = i
for j in range(i+1, len(my_list)):
if lst[j] < smallest:
smallest = lst[j]
my_list[i], my_list[smallest] = my_list[smallest], my_list[i]
# Maintenance Invariant
# End Invariant

Loop entry invariant: my_list[0..-1] is sorted. Since [0..-1] is just an empty list, it is indeed sorted
Start invariant: my_list[0..i-1] is sorted
Maintenance invariant: my_list[0..i] is sorted
End invariant: my_list[0..n-1] is sorted

2.1.2 Example 2

def palindrome(word):
left = 1
right = len(word)
# Loop entry Invariant
 2.2 Tips

while left < right:

# Start Invariant
if word[left] != word[right]:
return False
left += 1
right -= 1
# Maintenance Invariant
# End Invariant
return True

Loop entry invariant: word[0..left-1] is the same as word[right+1..n-1]. True because they are both empty
list
Start invariant: word[0..left-1] is the same as word[right+1..n-1]
Maintenance invariant: word[0..left] is the same as word[right..n-1]
End invariant: word is a palindrome

2.2 Tips
Loop entry invariant is usually [0..-1] or [1..-1]
Start invariant usually involves [0..i-1] or [1..i-1] or [i+1..n], because we haven’t processed the i-th one
Maintenance invariant usually involves [0..i] or [1..i] or [i..n] because we have processed the i-th one
End invariant is usually [0..n] or [1..n]
It doesn’t matter if it starts from 0 or 1, because we are not writing code, anything reasonable should be
fine

9
 Chapter 3 Sorting Algorithms

Some of the sorting algorithms we have learned: selection sort, bubble sort, insertion sort and heap sort.
All of these are comparison based sorting algorithms, and we do have some non-comparison based sorting
algorithms which are counting sort and radix sort.

3.1 Comparison Based Sorting Algorithms

Just to summarize:
Bubble sort: loop through the list and swap with the next one if current item is bigger than the next item.
After one iteration, the biggest unsorted item will be at its final position
Selection sort: loop through the list and find the smallest item in the unsorted part, then swap it with the
previous element so it will be at its final position
Insertion sort: compare with previous element, if current element is smaller than previous, swap. Keep
swapping until it reaches its final position
Heap sort: construct a min-heap and sort item by taking the smallest element We will have best case and
worst case for all of them. For bubble sort and selection sort, their complexity is N 2 no matter what. For
insertion sort, its best case is O(N ) when the list is already sorted. For heap sort, its best case is O(N ) if
it is a list of same item because we don’t have to sink or rise.

Name Best Case (Time) Worst Case (Time) Auxiliary Space Is Stable
Bubble Sort O(N ) O(N 2 ) O(1) Yes
Selection Sort O(N 2 ) O(N 2 ) O(1) No
Insertion Sort O(N ) O(N 2 ) O(1) Yes
Heap Sort O(N ) O(N log N ) O(1) No
Table 3.1: Comparison Based Complexity Table

3.2 Unstable Counting Sort

The idea of counting sort is simple, if we want to sort a list of numbers:
1. Loop through the list and find the biggest number
2. Create a list count_array of M + 1 size where M is the biggest number in the list (we need zero too)
3. Loop through the list again, add count list[number] += 1
4. Loop through count_array and add numbers
Demonstration

numbers = [9, 3, 7, 2, 4, 2, 1]
# Step 1
biggest_num = 9

# Step 2
count_array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 3.3 Stable Counting Sort

# Step 3
count_array = [0, 1, 1, 1, 1, 0, 0, 1, 0, 1]

# Step 4
numbers = [1, 2, 3, 4, 7, 9]

Code

def counting_sort(numbers):
# Step 1: O(N)
biggest_num = max(numbers)
# Step 2: O(M)
count_array = [0 for _ in range(biggest_num+1)]
# Step 3: O(N)
for i in range(len(numbers)):
count_array[numbers[i]] += 1
# Step 4: O(N+M)
sorted_numbers = []
for i in range(len(count_array)):
for j in range(len(count_array[i])):
sorted_numbers.append(i)
return sorted_numbers

3.2.1 Time Complexity

The time complexity of unstable counting sort is O(N + M )
1. Loop through a list of N items to find the biggest number M = O(N )
2. Create a list of M 0’s = O(M )
3. Count the occurrences of numbers in numbers = O(N )
4. Build back the sorted numbers. We need to loop through count_array which has size M and we will add
numbers based on the occurrences in that position = O(N + M )

3.2.2 Space Complexity

The space complexity of this counting sort is O(M ).
Input space: O(N ), where N is the number of items in numbers
Auxiliary space: O(M ), where M is the biggest number. This is due to the count_array
Total space: O(N ) + O(M ) = O(N + M )
Notice that this is an unstable version, because we are simply counting the number of occurrences. We can
always make an unstable algorithm stable using extra spaces. It is a trade off so we need to balance it out.

3.3 Stable Counting Sort

Everything is the same, but instead of counting the number of occurrences, we will insert it to the corre-
sponding position. Think of it as the idea of separate chaining.

11
 3.3 Stable Counting Sort

Figure 3.1: Stable Counting Sort

a and b are just to distinguish which comes first. Using this approach, we can make counting sort stable.
Code

def counting_sort(numbers):
...
count_array = [[] for _ in range(biggest_num+1)]
...
for i in range(len(numbers)):
# Only difference
count_array[numbers[i]].append(numbers[i])
...

Everything is the same, we will only change two lines

.append(numbers[i])
[] for _ in range

The time complexity is also the same. But for space complexity, the auxiliary space becomes O(N +M ) because
now we are storing a list of item, not number of occurrences.

Name Best Case (Time) Worst Case (Time) Auxiliary Space

Unstable Counting Sort O(N + M ) O(N + M ) O(N )
Stable Counting Sort O(N + M ) O(N + M ) O(N + M )
Table 3.2: Counting Sort Complexity Table

12
 3.4 Radix Sort

3.3.1 Extra Notes

The time complexity of counting sort is O(N + M ), and we know that M is the biggest number in the
list. However, if M = N 2 , the complexity will become O(N + N 2 ) = O(N 2 ), or O(N c ) where M = N c .
Therefore, counting sort is only linear if M ≤ N

3.4 Radix Sort

Radix sort is based on counting sort, and it must use the stable version of counting sort. Imagine if we have
to sort a list of numbers with very big range, we know that simply using counting sort will give us non-linear
complexity. So for radix sort, we will split it into k columns, and sort them accordingly.

Figure 3.2: Radix Sort

Let’s say we want to sort with base 10. As shown in Figure 3.2, we have 5 items and the biggest number is
892. We will figure out k using the formula:
k = logb M + 1
So log10 892 ≈ 2.92, by adding 1 and rounding down we get k = 3. This means that we have 3 columns, and we
will perform three counting sort on each column. Our base is 10 which is essentially the M we need in counting
sort, so the count_array in each counting sort has only size 10.

13
 3.5 Complexity Summary

Figure 3.3: Radix Sort Steps

We can also use radix sort to sort strings, we just need to make the base 26 and use ASCII to update.

3.4.1 Time Complexity

The time complexity of radix sort is O(k(N + b)) or O(kN + kb). After figuring out k, we will run
counting sort for k times. The time complexity for counting sort is O(N + M ), but M is essentially our base
so it is O(N + b). After running counting sort for k times, it is O(kN + Kb).

3.4.2 Time Always Linear?

Now the question is, is it always linear? We have a few conditions for it to be linear:
1. k < N : if k ≥ N , multiplying it here O(k(N + b)) will make it quadratic or more. For example. if
k = N , O(N (N + b)) = O(N 2 )
2. b ≤ N : assume k < N and b = N 2 , O(k(N + N 2 )) = O(N 2 )
3. M < N c : recall our formula k = logb M . Since our b ≤ N , and we will usually choose b = N , the
formula becomes k = logN M . The reason why we say radix sort is always linear is because, even if we
have M = N 10 , k = logN N 10 = 10. BUT, if M = N N , k = logN N N = N , and we know that k
should be less than N
But most of the time, radix sort is linear.

3.4.3 Space Complexity

For radix sort, we have to always use the stable version of counting sort. So auxiliary space is O(N + b),
because we know M = b. Input space is just O(N ) where N is the number of items in the list.

14
 3.5 Complexity Summary

3.5 Complexity Summary

Name Best Case (Time) Worst Case (Time) Auxiliary Space Is Stable
Bubble Sort O(N ) O(N 2 ) O(1) Yes
Selection Sort O(N 2 ) O(N 2 ) O(1) No
Insertion Sort O(N ) O(N 2 ) O(1) Yes
Heap Sort O(N ) O(N log N ) O(1) No
Unstable Counting Sort O(N + M ) O(N + M ) O(N ) No
Stable Counting Sort O(N + M ) O(N + M ) O(N + M ) Yes
Radix Sort O(N ) O(k(N + b)) O(N + b) Yes
Table 3.3: Sorting Algorithm Complexity Table

15
 Chapter 4 Divide and Conquer

Divide and conquer means splitting the original problem into subproblems, solve each subproblem inde-
pendently and combine their solutions to yield the final solution. One of the most well known divide and conquer
algorithms is quick sort. General idea of quick sort:
1. Choose a pivot
2. Partition the list based on the pivot. The pivot will be at its final position after partitioning
3. Recursively call the function to partition the two sides and eventually sort the list

There are different types of partition:

Out-of-place partitioning
Lomuto partitioning
Hoare’s partitioning
Dutch national flag

4.1 Hoare’s Partitioning

Select a pivot, let’s say the first item
Initialise left and right pointer
Move the left pointer until we find an element > pivot
Move the right pointer until we find an element ≤ pivot
Swap the element that left and right pointers are pointing at
Stop when the two pointers crossed
If left and right pointers are not the same, swap right pointer with pivot

Figure 4.1: Hoare’s Partitioning

After partitioning, the pivot 3 will get to its final place. All items to its left will be ≤ than the pivot, all
 4.2 Quick Select

items to the right will be > than the pivot. For quick sort, we will recursively call left side and right side to
further partition and sort. Observe that if we have always chosen the median to be the pivot, we can partition the
list evenly, and the number of recursive calls will be only O(logN ). However, if we have chosen the smallest or
largest item, either left or right side will be empty and we will need to call the function recursively for N times,
and the number of recursive calls will be O(N ). Now the question is, is there a way for us to always choose the
median?

4.2 Quick Select

Quick select is used to find k-th smallest numbers. It is very similar to quick sort, but instead of partitioning
both side, we will only go one side. For example, in Figure 4.1, if we choose k = 3, we will stop after the first
partitioning because the pivot 3 is at position 3. Therefore, we have gotten the three smallest numbers in the list,
which are [1, 2, 3]. But if k = 5, since 3 < 5, we will need to perform quick select on the right side. If we want
to find the median of a list to choose as a pivot, we can simply call quick select and pass in k = len(lst) // 2!

4.2.1 Application

Assume we have 100 students, and we want to scale their grades. For the top 10 students, we
will deduct 2 marks from each of their grades. For the bottom 20 students, if their
grades are below the median, we will add 3 marks to their grades. Otherwise, we will add
2 marks.

To solve this, we will use the quick select algorithm to find the median by selecting the element at position
0.5 × N , where N is the number of students (100). This will allow us to split the students into left and right
sides based on the median. For the top 10 students, we can obtain them by calling quick select on the left side
for 0.8 × 0.5 × N , which gives us the top 10 students. Then, we deduct 2 marks from each of their grades. Note
that we can’t use 0.2 × 0.5 because it would give us the bottom 10 students on the right side. For the bottom
20 students, we call quick select on the left side for 0.4 × 0.5 × N , which gives us the bottom 20 students. We
then compare each of their grades to the median. If a grade is below the median, we add 3 marks. Otherwise,
we add 2 marks.

4.2.2 Online Algorithm

Online algorithms are those that can process new information without re-processing the old one. For ex-
ample, insertion sort because we can simply insert the new item at the end, compare and so on. We don’t have
to re-process everything. However, quick select is offline, if we need an online algorithm to find smallest k
elements, use heap.

4.2.3 Time Complexity

We wanted to use quick select to find the median, so that our quick sort will ensure logN recursive calls.
However, while we are performing quick select, we still need to choose a pivot. But we can’t guarantee that the
pivot our quick select chooses is also the median! It could still be the smallest or biggest item, resulting in N
recursive calls, which is still the same, and it doesn’t improve our complexity. Is there another way?

17
 4.3 Median of Medians

4.3 Median of Medians

The idea of median of medians is like its name, find median of medians! It does not guarantee the one we
got is the exact median, it will call quick select and it will return the pivot in the middle 40%, which is considered
as a good pivot.
1. Split the input list into sub-lists of k items (k is usually 5)
2. Call quick select to find median of each sub-list
3. Median of each sub-list is the medians, we then repeat step 1 and 2, and find the median of these medians

Figure 4.2: Median of Medians

As you can see in Figure 4.2, the median (orange) will definitely be greater than the left bottom red part,
and less than the right upper green part. The green and red part are 30% each and 60% in total, the the median is
in the middle 40%. Therefore, if we use MoM to find the pivot for quick select, we can guarantee logN recursive
calls.
Now we can guarantee the number of recursive calls for quick sort is logN with quick select and median of
medians. So the best and worst case of quick sort are now both O(N logN ), but can we improve the best case?

4.4 Dutch National Flag Partitioning (DNF)

Instead of two pointers, DNF uses three pointers. Below is the idea
List[1...i] < pivot
List[i+1…j-1] = pivot
List[j...r] > pivot

Figure 4.3: Dutch National Flag

Observe that if we have a list of same item, other partition algorithms will still need N recursive calls, because
they have the property of ≤ p on the left side. But for DNF, we only need one partition and we will exit the
quick sort. Why? Because we will be left with the white part (=p). So DNF can reduce the complexity of quick
sort to O(N )!

18
 4.5 Complexity Summary

4.4.1 Challenge
Code everything out
Write down different combinations and analyze their complexity
If the pivot is ≥ 10% of the items, what is the quick sort complexity?
I am gonna reveal it, it is O(N logN ), because of log 10 N recursions
9

4.5 Complexity Summary

Name Best Case (Time) Worst Case (Time) Auxiliary Space

Quick Sort O(N log N ) O(N 2 ) O(log N )/O(N )
Quick Sort with DNF O(N ) O(N 2 ) O(1)/O(log N )
Quick Sort with Quick Select O(N log N ) O(N 2 ) O(log N )/O(N )
Quick Sort with Quick Select and MoM O(N log N ) O(N log N ) O(log N )
Quick Sort with Quick Select, MoM, and DNF O(N ) O(N log N ) O(1)/O(log N )
Table 4.1: Comparison-Based Complexity Table

19
 Chapter 5 Graphs and Shortest Distance

Graph can be used to solve so many real world problems. For example, GPS navigation, network routing,
job scheduling, task/resource allocation and so much more! Therefore, it is important for us to learn about
graphs!

5.1 Graph
Graph is essentially a set of vertices/nodes and a set of edges/links
G = (V, E)
This means that in a graph G, we have a set of vertices V and a set of edges E. A graph can be weighted
or unweighted. For example, if we want to compute the shortest distance from one location to another, there
must be different stations in between, some are nearer, and we will use the weight to represent the distance. For
unweighted graph’s example, if we want to build a social network graph, the weights are not important because
we just want to know whether two persons know each other. A weighted graph can be represented as
G = (V, E, W )
where W represents weight. Think of it from an OOP point of view. In this case, we need to create a class for
vertex, edge and graph.

5.1.1 Edge
An edge is just a link between two vertices, which can be represented by
E = (U, V )
or
E = (U, V, W )

One with weight and one without. This is a directed edge, it is an edge from vertex u to vertex v. To create an
undirected edge (no direction, just a link), we can simply do something like this in the code
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w

edge1 = Edge(u, v, w)
edge2 = Edge(v, u, w)
u.add_edge(edge1)
v.add_edge(edge2)

By adding a directed edge in both directions, it is an undirected edge.

 5.1 Graph

5.1.2 Vertex
In a Vertex class, we usually store an id to represent which vertex it is, and a edges list to know its outgoing
edges. Note that edges in this example are stored in an adjacency list, we will go through what this is later, but
adjacency list / adjacency matrix have different implementation.
class Vertex:
def __init__(self, id, edges=[]):
[Link] = id
[Link] = edges

5.1.3 Graph
In the Graph class, it will just store a set of vertices because the edges are included in the vertices already.
Of course, different implementations could be different.
class Graph:
def __init__(self, vertices):
[Link] = vertices

...

5.1.4 More Properties

There is a few important properties to know. We know that the maximum number of edges in a graph is
(V ) 2
2 , or V because each edge requires two vertices. So a graph is called
Sparse if E << V 2
Dense if E ≈ V 2
More about maximum number of edges:
Directed graph: V (V − 1) = O(V 2 )/O(E)
Undirected graph: V (V2−1) = O(V 2 )/O(E)
In a connected simple graph, its edges is at most V 2 and at least V − 1, because we need V − 1 edges to make
the graph connected. Same goes for a disconnected simple graph, it is just that a disconnected one can have no
edges.

Figure 5.1: Directed and Undirected Graph

21
 5.2 How to Represent Graphs

5.1.5 Tree
Just to recap, a tree is a graph that is acyclic (no cycle) and connected. The directed graph in Figure 5.1
shows an example of a cycle, from 2 -> 3 -> 4 -> 2. There are many types of tree, the one we use most often is
binary tree, and a binary has at most two outgoing edges (left and right child) for every vertex.

5.2 How to Represent Graphs

There are two ways to present a graph. Adjacency list or Adjacency matrix. They are useful in different
cases, but we usually use adjacency list more.

5.2.1 Adjacency Matrix

An adjacency matrix is a n x n matrix where n is the number of vertices. If we want to see if there is an
edge from vertex u to vertex v, we can know it in O(1) time. For example, matrix[2][1] has an edge because it is
1. We often use adjacency matrix when the graph is dense. If the graph is sparse, we will waste a lot of spaces,
as shown in Figure 5.2.

Figure 5.2: Adjacency Matrix

[Link] Time Complexity

Traverse all edges: O(V 2 )
Get all outgoing of one vertex: O(V )
Get all incoming of one vertex: O(V )
Check if an edge exists between u and v: O(1)

[Link] Space Complexity

Auxiliary Space: O(V 2 ) for both best and worst case

5.2.2 Adjacency List

An adjacency list is an array that stores all vertices, each vertex will store a list of edges. You can refer to
the example under 5.1.2 Vertex. We often use adjacency list more because we often need to traverse the edges

22
 5.3 BFS and DFS

in the graph. It doesn’t matter if it is sparse or dense, because we will only use the space whenever necessary as
shown in Figure 5.3.

Figure 5.3: Adjacency List

[Link] Time Complexity

Traverse all edges: O(V + E)
Get all outgoing of one vertex: O(V )/O(X), where X is the number of outgoing edges of that vertex
Get all incoming of one vertex: O(V + E)
Check if an edge exists between u and v: O(V + E)

[Link] Space Complexity

Auxiliary Space: O(V + E) for both best and worst case

5.3 BFS and DFS

Breadth first search (BFS) and depth first search (DFS) can be represented by a queue and a stack corre-
spondingly. BFS goes wide, dfs goes deep. Due to this, BFS can find the shortest distance from one vertex to
another if the graph is unweighted. If the graph is weighted, we need to use other shortest distance algorithms.

5.3.1 Breadth First Search

We use a queue for BFS because it follows the First-In-First-Out (FIFO) method. Figure 5.4 is a demon-
stration of BFS progress. The order of visiting will be 1 -> 2 -> 5 -> 3 -> 4. Note that we will only each vertex
once. With this, we have found the shortest distance from vertex 1 to all the other vertices in this unweighted
graph.

23
 5.3 BFS and DFS

Figure 5.4: Breadth First Search

[Link] Time Complexity

Using adjacency list: O(V + E)
Using adjacency matrix: O(V 2 ), because we need to traverse even though that edge does not exist in a
matrix

[Link] Space Complexity

Using adjacency list: O(V + E)
Using adjacency matrix: O(V 2 )
Queue: O(V )

5.3.2 Depth First Search

We use a stack for DFS because it follows the Last-In-First-Out (LIFO) method. Figure 5.5 is a demon-
stration of DFS progress. We will keep going in-depth, until we have nothing to visit, and we will go back to
the previous level. The order of visiting will be 1 -> 2 -> 3 -> 4 -> 5.

24
 5.4 Dijkstra

Figure 5.5: Depth First Search

[Link] Time Complexity

Using adjacency list: O(V + E)
Using adjacency matrix: O(V 2 ), because we need to traverse even though that edge does not exist in a
matrix

[Link] Space Complexity

Using adjacency list: O(V + E)
Using adjacency matrix: O(V 2 )
Stack: O(V )

25
 5.4 Dijkstra

5.4 Dijkstra
Dijkstra is a well known shortest distance algorithm, it is actually just BFS + priority queue. As we want
to find the shortest distance, we will use a min heap. Dijkstra helps us to find the shortest distance from one
vertex to all the other vertices. The idea:
1. Set the distance of all vertices to infinity, and set the distance of the source vertex to be 0
2. Push the source vertex onto the min heap
3. Pop the vertex u on top of the heap
4. Traverse through the edges of vertex u, update distance if v has not been visited and [Link] + w <
[Link]. If updated, either push it onto the heap / update if the vertex is already in the heap.
5. Repeat step 3 and 4 until the min heap becomes empty
After running the algorithm, we should get the shortest distance from the source vertex to all the other vertices.
We can also get back the path by including a pre variable and perform backtracking to get back the path
Pseudocode

# Set all vertices' distance to inf

# visited to False and prev to None
reset()

pq = MinHeap()
[Link](source)
while not pq.is_empty():
vertex = [Link]()
[Link] = True
for edge in [Link]:
u, v, w = edge
if not [Link] and [Link] + w < [Link]:
[Link] = [Link] + w
[Link] = u
if v in pq:
[Link](v)
else:
[Link](v)

# Backtracking
path = []
[Link](destination)
current = destination
while [Link] != None:
current = [Link]
[Link](current)
[Link]()

26
 5.5 Directed Acyclic Graph

Figure 5.6: Dijkstra

5.4.1 Time Complexity

We have heap operation like sink and rise, which are O(logV ), and we will traverse through all edges, so
O(E)
Using adjacency list: O(ElogV )
Using adjacency matrix: O(V 2 logV )

5.4.2 Space Complexity

Using adjacency list: O(V + E)
Using adjacency matrix: O(V 2 )
Heap: O(V )

5.4.3 Extra Notes

Dijkstra is a greedy algorithm so it doesn’t work with negative edges
Edges in Dijkstra must be positive, and we can never have a negative cycle in the graph because it will
just loop forever. A negative cycle means a cycle that will go back to its source with smaller distance
One example where Dijkstra will work with negative edge is when it has only one negative directed edge
from source to another vertex, because in this case we will only proceed the negative edge once. But this
is very rare, so Dijkstra does not work with negative edges

27
 5.5 Directed Acyclic Graph

5.5 Directed Acyclic Graph

Directed acyclic graph is a graph that is directed and acyclic (of course...). It must be unweighted and
directed, and its application examples are like prerequisite, course map and skill tree, etc. We can use topological
sort or a modified DFS. Remember that the solutions for both algorithms are not unique, unless we always have
one item in the queue only. Not too much to cover, but just remember its application.

5.6 Complexity Summary

Name Best Case (Time) Worst Case (Time) Auxiliary Space

BFS with Adjacency List O(V + E) O(V + E) O(V + E) / O(V )
BFS with Adjacency Matrix O(V 2 ) O(V 2 ) O(V 2 ) / O(V )
DFS with Adjacency List O(V + E) O(V + E) O(V + E) / O(V )
DFS with Adjacency Matrix O(V 2 ) O(V 2 ) O(V 2 ) / O(V )
Dijkstra with Adjacency List O(ElogV ) O(ElogV ) O(V + E) / O(V )
Dijkstra with Adjacency Matrix O(V 2 logV ) O(V 2 logV ) O(V 2 ) / O(V )
Topological Sort O(V + E) O(V + E) O(V + E) / O(V )
Table 5.1: Graphs Complexity Table

28
 Chapter 6 Minimum Spanning Tree

Minimum spanning tree (MST) is a tree that spans every vertex but with the minimum total edges and
weights to connect all vertices. It is the minimum number of edges to connect all edges and maximum number
of edges in graph without cycle. We usually use MST to find the sub-graph in a graph, and it only work with
undirected and weighted graph.
MST in the same graph may not be unique, because we could have one vertex with multiple edges and
the same weight. So Prim and Kruskal might not get the same MST everytime. MST can work with both
negative edges and negative cycles, because MST is a tree and we know that a tree is acyclic. We have two
MST algorithms which are Prim and Kruskal.

6.1 Prim’s Algorithm

Prim is almost the same as Dijkstra, the only difference is just two lines. Instead of updating the distance,
we will just add the weight.
Pseudocode
...
for edge in [Link]:
u, v, w = edge
if not [Link] and w < [Link]:
[Link] = w
...
 6.2 Kruskal’s Algorithm

Figure 6.1: Prim’s Algorithm

6.1.1 Maximum Spanning Tree

If we want to find a maximum spanning tree instead of minimum, we can either
Make the edges negative
Use max heap instead of min heap

6.1.2 Time Complexity

Same complexity as Dijkstra, O(ElogV ), refer to the Dijkstra section if you forgot why

6.1.3 Space Complexity

Same complexity as Dijkstra, O(V + E)/O(V ), refer to the Dijkstra section if you forgot why

6.2 Kruskal’s Algorithm

Kruskal’s algorithm is basically sort all edges first, then start from the smallest, add edges until we have
obtained a MST. Before we go into what this algorithm is, we have to understand the idea of disjoint set and
union find.

6.2.1 Disjoint Set and Union Find

For a disjoint set, we have a parent array. At first, all vertices in the array have value of -1. Negative value is
the size and it indicates that the vertex is the root, -1 means the sub-tree has only one vertex. If it is not negative

30
 6.2 Kruskal’s Algorithm

numbers, the positive number will be the parent of that vertex.

Figure 6.2: Disjoint Set

For instance, in Figure 6.2, vertex 1 has 3 vertices in the tree, and vertex 1 is the root. For vertices 2 and 3,
their parents are vertex 1. Vertex 4 is the root and has two vertices in the tree, vertex 5 is its child.
If we want to merge vertex 2 and vertex 5. We will perform the find operation, it will keep going up until
it reaches the root (vertex with negative value). After we get the root of both vertices, we will compare the size.
The tree with less children will merge with the one with more children. So
find(2) = 1
find(5) = 4
disjoint_set[1] = -3
disjoint_set[4] = -2

So vertex 4 will become child of vertex 1

disjoint_set[1] += disjoint_set[4] # Add the tree size
disjoint_set[4] = 1

6.2.2 How it Works

1. Sort all edges with their weight using quick sort
2. Start from the edge with smallest weight, and start merging
3. Stop when we have obtained a MST

Figure 6.3: Kruskal’s Algorithm

31
 6.3 Complexity Summary

6.2.3 Maximum Spanning Tree

If we want to find a maximum spanning tree instead of minimum, we can either
Make the edges negative
Add edges in decreasing order

6.2.4 Time Complexity

Sort edges using quick sort: O(ElogE)
Find: O(logV )
Union: O(1)
Total: O(ElogE + E(logV + 1) = O(ElogE)
But it can be amortized into O(ElogV ) because we will have at most V 2 edges and O(ElogV 2 ) =
O(2ElogV ) = O(ElogV )

6.2.5 Space Complexity

O(V + E) because of the adjacency list

6.3 Complexity Summary

Name Best Case (Time) Worst Case (Time) Auxiliary Space

Prim O(ElogV ) O(ElogV ) O(V + E)
Kruskal O(ElogV ) O(ElogV ) O(V + E)
Table 6.1: Graphs Complexity Table

32
 Chapter 7 Dynamic Programming

Dynamic programming (DP) has always been the most popular competitive programming (CP) questions,
and it is hard to get it at first, it requires a lot of practices. DP is somewhat similar to divide and conquer because
1. Take a big problem
2. Divide into smaller problems
3. Combine solutions
Their differences are that DP will reuse the optimal solutions due to overlapping sub-problems. For example,
when we compute Fibonacci numbers, the i-th Fibonacci number will be fib(i-1) + fib(i-2), or the total of its
previous two numbers. A common solution:
fib_nums = [1, 1, 2, 3, 5, 8, 13, ...]

def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)

But there is actually a lot of overlapping problems. The 4th Fibonacci number is 3 and the 5th Fibonacci number
is 5. The 4th one is fib[2] + fib[3], and the 5th one is fib[3] + fib[4]. The fib[3] is overlapping, but if we use
the previous recursion approach, we will reach fib[4] twice because we are not reusing it. So we can actually
memorize fib[4] to avoid recomputing the problems we have seen before.
fib_nums = [1, 1, 2, 3, 5, 8, 13, ...]

# Bottom up
memo = [-1] * n
memo[1] = 1
memo[2] = 1
for i in range(2, n):
memo[i] = memo[i-2] + memo[i-1]

# Top down
memo = [-1] * n
memo[1] = 1
memo[2] = 1
def fib(n):
if memo[n] != -1:
return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]

With memo, we can memorize the previous solution and reuse it. The only downside of it is that we need to use
extra spaces to store the solutions. However, it is definitely faster.
As shown in the above example, I have created two approaches: bottom up and top down. Bottom up means
start from the base case, solve it and use it to solve bigger cases until we have reached the final one. Top down
means start from the final one, divide it to a smaller one until we have reached the base case.
 7.1 LeetCode 198: House Robber

7.1 LeetCode 198: House Robber

Figure 7.1: LeetCode 198: House Robber

7.1.1 Solution

Figure 7.2: Recurrence Relation

We will use the bottom up approach. At first, we create a memo list with all infinity. Make the base case, 0
be nums[0] and we can run the loop. To rob the maximum amount of money, we will either rob the i-1 one, or
the i-2 one plus the current one. At the end, memo[n-1] will store the maximum amount of money the robber
can rob.

7.1.2 Time Complexity

O(N ), we are only traversing through the list once

7.1.3 Space Complexity

O(N ) auxiliary, because we have created a memo array

34
 7.2 LeetCode 62: Unique Path

7.2 LeetCode 62: Unique Path

Figure 7.3: LeetCode 62: Unique Path

7.2.1 Solution

Figure 7.4: Recurrence Relation

There are many ways to solve this. But I will choose to start from the future. Assume we start from the
destination, it will be one because we only have one way to stay at the destination. To the left of the destination,
we can only go right to reach the destination. Same goes for to the top of the destination. But for top left, we
have two options: move right then go down, or move down then go right. This is two ways, so we will be adding
the total ways on the right and the total ways at the bottom. Same goes for everything as shown in Figure 7.3.

35
 7.3 LeetCode 300: Longest Increasing Subsequence

Figure 7.5: LeetCode 62: Unique Path Solution

7.2.2 Time Complexity

O(N M ), we are traversing through the matrix

7.2.3 Space Complexity

O(N M ) auxiliary, because we have created a NxM memo array

7.2.4 Challenge
If we have walls in the matrix, how many ways can we walk to the destination? Tips: If array[i][j] is a wall,
make memo[i][j] = 0

36
 7.3 LeetCode 300: Longest Increasing Subsequence

7.3 LeetCode 300: Longest Increasing Subsequence

Figure 7.6: LeetCode 300: Longest Increasing Subsequence

7.3.1 Solution

Figure 7.7: Recurrence Relation

At first, we will set all values in the memo array to be 1, which means that the longest increasing subse-
quence for that num is 1 (itself). Then we will loop through the array, find its previous longest subsequence x,
and nums[x] must be the current number, or else it won’t be increasing. If nums[x] the current number, we
know that all of the previous ones before x will also be less than the current one. So we just need two loops.

7.3.2 Time Complexity

O(N 2 ), we need two loops. First one is to find the LIS of each number, the second one is to find the max
LIS of the previous numbers

7.3.3 Space Complexity

O(N ) auxiliary, because we only have one memo array

37
 7.4 LeetCode 1143: Longest Common Subsequence

7.4 LeetCode 1143: Longest Common Subsequence

Figure 7.8: Longest Common Subsequence

7.4.1 Solution

Figure 7.9: Recurrence Relation

This solution uses a 2D dp array where memo[i][j] represents the length of the longest common subse-
quence between the first i characters of text1 and the first j characters of text2. If text1[i-1] == text2[j-1], it
means that the last character of two characters are the same, so we increment the length from memo[i-1][j-1].
Otherwise, we take the maximum of removing last character of text1 or last character of text2. See the i as the
number of prefixes in text1 and j as the number of prefixes in text2.

38
 7.5 LeetCode 72: Edit Distance

7.4.2 Time Complexity

O(N M ), we are traversing through the matrix

7.4.3 Space Complexity

O(N M ) auxiliary, because we have created a NxM memo array

7.5 LeetCode 72: Edit Distance

Figure 7.10: LeetCode 72: Edit Distance

7.5.1 Solution

Figure 7.11: Recurrence Relation

This solution for Edit Distance uses a 2D memo array where memo[i][j] represents the minimum edit
distance to convert the first i characters of word1 into the first j characters of word2. For memo[i-1][j-1], we are

39
 7.6 LeetCode 53: Maximum Subarray

comparing the i-1/j-1 character of both strings. For memo[i-1][j], we delete the i-th character of first string. For
memo[i][j-1], we insert the j-th character of second string to the first string. For example
s1: ababa
s2: abecd
i = 3, j = 2 -> s1 = abab, s2 = abe

For memo[i-1][j-1], we have s1 = aba and s2 = ab, just compare and since b != e we need to replace
For memo[i-1][j], we have s1 = aba and s2 = abe, this means we have deleted b from s1
For memo[i][j-1], we have s1 = abab and s2 = ab, this means we need to insert e to s1

7.5.2 Time Complexity

O(N M ), we are traversing through the matrix

7.5.3 Space Complexity

O(N M ) auxiliary, because we have created a NxM memo array

7.6 LeetCode 53: Maximum Subarray

Figure 7.12: LeetCode 53: Maximum Subarray

40
 7.6 LeetCode 53: Maximum Subarray

7.6.1 Solution

Figure 7.13: Recurrence Relation

In the Maximum Subarray problem, memo[i] represents the largest sum of any subarray that ends at position
i. If adding the previous maximum sum (from memo[i-1]) to array[i] gives a positive result, we add them
together in memo[i]. If not, we start a new subarray at array[i]. The largest value in the memo array at the end
will be the maximum subarray sum.

7.6.2 Time Complexity

O(N ), we are traversing through the word once only

7.6.3 Space Complexity

O(N ), we only need 1D memo array

41
 Chapter 8 DP Graph Algorithm

As we said, Dijkstra can’t work with negative edges due to its greediness. For example

Figure 8.1: Dijkstra with Negative Edges

In Figure 8.1, we know that 1->3->4 will be the shortest path from vertex 1 to vertex 4. However, Dijkstra
will give us the 1->2->4 instead, because 7 is greater than both 3 and 5, so it will not be proceeded first. Therefore,
we need dynamic programming graph algorithms like Bellman Ford and Floyd Warshall.

8.1 Bellman Ford

There are two implementations of Bellman Ford, the 2D array implementation and 1D array implementa-
tion. We usually prefer the latter one, but we will go through the 2D array one first for easier understanding.

8.1.1 2D Array Implementation

At first, the distance of the source vertex will be set to 0, and the rest will be set to infinity. Infinity simply
means not reeachable. We will have an edge list, and we will proceed the edge according to the list order. As
shown in Figure 8.1, when i=1, we have our first iteration, and i=1 means the shortest path we can get from
source to the other vertices with one edge. i=2 will mean the shortest path we can get from source to the other
vertices with 2 edges, and so on. In every iteration, if we have an edge from a to b, we will take a’s distance
in the previous column, plus the distance between a and b, if it is shorter than what b currently have, we will
update the new shortest distance.
 8.1 Bellman Ford

Figure 8.2: Bellman Ford Without Negative Cycles

For example, during our first iteration i=1 in Figure 8.2, a is the only one without infinity, so we can only
update ab and ac. For the rest, infinity plus anything is still infinity. During our second iteration i=2, we will
still use the distance in the previous column, now we can update bd and ce too. So the code will look something
like
for edge in edges:
u, v, w = edge
bf_arr[i][v] = min(bf_arr[i-1][u] + w, bf_arr[i-1][v])

We will loop for v-1 iterations, and the v-th iteration is used to check if there exists a negative cycle. Figure
8.2 has no negative cycles, so it has the exactly same values for i=4 and i=5. But if there exists a negative cycle
in the graph, i=4 and i=5 will be different, so this is how we can check if a negative cycle exists. We can also
terminate early if we noticed two consecutive columns stop changing values, because this means all cases after
it will not update too.

43
 8.1 Bellman Ford

Figure 8.3: Bellman Ford With Negative Cycles

For example, in Figure 8.3, there exists a negative cycle, so in the v-th iteration, i=4 and i=5 are not the
same. The reason for this is because, the shortest number of paths in a graph with v vertices must be v-1. If
doesn’t make sense to have a shortest path with more than v-1 vertices, unless there exists a negative cycle.

[Link] Time Complexity

Best case: O(E), when i=1 and i=2 have the same distance for all vertices, so we can exit early
Worst case: O(V E), we will loop through v iterations and check every edge in every iteration

[Link] Space Complexity

Auxiliary space: O(V 2 ), we will create a V x V 2D array

8.1.2 1D Array Implementation

The previous 2D array implementation can tell us the shortest distance according to the number of edges.
But most of the time, we might just want to know the shortest distance, and we can use a pre variable to store
its previous vertex, and backtrack to get the path. Therefore, we can use 1D array to save spaces. The only
difference in the code is
for edge in edges:
u, v, w = edge
bf_arr[v] = min(bf_arr[u] + w, bf_arr[v])

Instead of using the value in the previous column, we will just use the value in the existing column. We start
from source being 0, and all the others are infinity.

44
 8.2 Floyd Warshall Algorithm

Figure 8.4: Bellman Ford With 1D Array

As shown in Figure 8.4, we can reuse the existing one and finish in two iterations, which is faster and
more space efficient than the 2D array implementation. If we want to check negative cycle using 1D array
implementation, we will still check whether (v-1)-th iteration and v-th iteration are the same.

[Link] Time Complexity

Best case: O(E), when i=1 and i=2 have the same distance for all vertices, so we can exit early
Worst case: O(V E), we will loop through v iterations and check every edge in every iteration

[Link] Space Complexity

Auxiliary space: O(V ), we will create a 1D array

8.2 Floyd Warshall Algorithm

Before we talk about this algorithm, we have to understand the idea of transitivity. Transitivity means if
we can go from a -> b and b -> c, we can go from a -> c because we have a path of a -> b -> c. Floyd Warshall
is based on this concept.
At first, we will make all diagonal 0, because every vertex to itself will have a distance of 0. Then we will
loop through each edge, add the weight in the matrix. For example, if there exists an edge from a to b with a
weight of 5, we will set matrix[a][b] = 5.

45
 8.2 Floyd Warshall Algorithm

Figure 8.5: Floyd Warshall

Figure 8.5 is an example of the initial setup, the rest of the column will be infinity. But for simplicity, I just
made it empty for better visualization.
The code for Floyd Warshall is very simple
for k in range(len(vertices)):
for i in range(len(vertices)):
for j in range(len(vertices)):
matrix[i][j] = min(matrix[i][k] + matrix[k][j], matrix[i][j])

k is the intermediate vertex

i is the source vertex
j is the destination vertex
So we will go through every possible combinations of i -> k and k -> j which is essentially i -> j. Then we will
take the minimum distance. If we want to know what the matrix looks like after k iterations, we can use a
trick:
1. We know that k represents the intermediate node. If k = 1, it means we want to find the path from i ->
a -> j (note that a is the first row), we only need to check the first column because the first column keep
track of the incoming vertices of a. Observe that first column has no incoming edges as all of the values
are infinity. As shown in the graph, no vertex has a directed edge to a too.
2. When k = 2, we will look at the second column. This time, a has a path to b with distance 3. Then we
can look at the second row, we will see what outgoing edges b has. b has only one outgoing edge to d, so
we simply need to update the distance from a -> b -> d. And we are done with updating values for the
second iteration
3. When k = 3, we will look at the third column. This time, c has two incoming edges a and d, and c has an
outgoing edge to e. Therefore, we just need to update a -> c -> e and d -> c -> e.

46
 8.2 Floyd Warshall Algorithm

Figure 8.6: Floyd Warshall

The final result after all iterations is shown in Figure 8.6.

8.2.1 How to Detect Negative Cycles

If the diagonal becomes negative, it means that there exists a negative cycle in the graph, because every
vertex to itself can’t be negative.

8.2.2 Time Complexity

Best case: O(V 2 ) when we detect a negative cycle after second iteration. It is O(V 2 ) not O(V ) because
we need time to build the matrix
Worst case: O(V 3 ) because we need to run all-pair

8.2.3 Space Complexity

O(V 2 ) for the matrix

8.2.4 All-Pair
Floyd Warshall is an all-pair shortest path algorithm because it computes the shortest path from each
node to every other node in the graph, rather than just from a single source. It is useful in application like
network routing and transportation system. For example, when we use Waze or Google Map, we want to find
the shortest path from one location to the other. Others might want to find it too. With Floyd Warshall, this can
be done in O(V 3 ) time. If we used previous algorithms like Dijkstra or Bellman Ford, it requires complexity
of O(V 3 logV ) and O(V 4 ) correspondingly in the worst case (If you don’t get it, it is basically V times the
complexity, because we want to know the shortest path from every source to the other vertices, so we need to
run the algorithm from every source). However, if the graph is unweighted, we will prefer BFS because all-pair

47
 8.3 Complexity Summary

in BFS is O(V 2 ) in the best case and O(V 3 ) in the worst case. The best case is better than Floyd Warshall and
worst case is same as Floyd Warshall. But only use BFS if the graph is unweighted.
Note: E can be V or V 2 depending whether the graph is sparse or dense.
BFS: O(V ) × O(V + E) = O(V (V + E)) = O(V 2 )/O(V 3 )
Bellman Ford: O(V ) × O(V E) = O(V (V E)) = O(V 3 )/O(V 4 )
Dijkstra: O(V ) × O(ElogV ) = O(V (ElogV )) = O(V 2 logV )/O(V 3 logV )
Floyd Warshall: O(V 3 )

8.3 Complexity Summary

Name Best Time Worst Time Auxiliary Space Best AP Worst AP

BFS O(V + E) O(V + E) O(V ) O(V 2 ) O(V 3 )
Dijkstra O(ElogV ) O(ElogV ) O(V ) O(V 2 logV ) O(V 3 logV )
Bellman Ford O(E) O(V E) O(V ) O(V 3 ) O(V 4 )
Floyd Warshall O(V 2 ) O(V 3 ) O(V 2 ) O(V 3 ) O(V 3 )
Table 8.1: Graphs Complexity Table

Assume we used adjacency list (not considered in aux space)

Just remember when we see E, we can think of cases when the graph is sparse or dense
Sparse = V , dense = V 2 , just sub it in and analyse

48
 Chapter 9 Flow Network

A flow network is a directed weighted graph. It has a source (a vertex without incoming edges) and a sink
(a vertex without outgoing edges). On every edge, we will have flow and capacity, and the flow must be ≤
capacity. According to the flow conservation property, the total flow out of the source equals the total flow into
the sink. For every vertex, the incoming flow must equal the outgoing flow as well.

Figure 9.1: Flow Network

As you can see in Figure 9.1, the flow of the network is 5, which we can observe through the outgoing
flow from the source and the incoming flow to the sink. Often, we want to find the max flow in the network to
solve real-world problems. To do this, we have to build a residual network, perform Ford-Fulkerson, and find
the min-cut max-flow.

9.1 Residual Network

It is simple to build a residual network. The forward edge will represent the remaining flow, and the reverse
edge will represent the flow the vertex has given out. Remember we have to always implement both forward and
reverse edges. IT WON’T WORK without both directions.
 9.2 Ford-Fulkerson

Figure 9.2: Residual Network

From Figure 9.1, we can build a residual network similar to Figure 9.2.

9.2 Ford-Fulkerson
After we have built the residual network, we can perform Ford-Fulkerson. An augmenting path is a valid
path from the source to the sink. We can use BFS to find the path and stop when there are no more augmenting
paths. After finding an augmenting path, we will take the minimum capacity - flow for each edge, then we can
flow through that path and update the residual network. For instance, the forward edge should subtract that flow
and the reverse edge should add that flow.

Figure 9.3: Ford Fulkerson

50
 9.3 Min-Cut Max-Flow

Figure 9.3 is an example of the process of Ford-Fulkerson. We have two augmenting paths and we update
the flow correspondingly. Since we can no longer find an augmenting path in the last iteration, we will stop.
The max flow is then 7 derived from 4+4-1 from the source or 5+3-1 to the sink.

9.3 Min-Cut Max-Flow

After obtaining the max flow, we can find a min-cut. A min-cut is a partition of the nodes into two disjoint
subsets, one consisting of the source (S) and the other consisting of the sink (T). We usually use min-cut max-
flow to prove that the algorithm has found a max flow. If we can find a min-cut, it means the flow of this
network is maximized.
The flow of a cut = flow of outgoing - flow of incoming.
Capacity of a cut = capacity of outgoing edges
Flow of a cut ≤ capacity of a cut
Flow of a cut == flow of network
Min-cut is not unique
There is a trick to find the set. Starting from the source, we identify all reachable nodes from the source, and
they will belong to the source set; the rest will belong to the sink set.

Figure 9.4: Min-cut

For the previous example, the min-cut is shown in Figure 9.4. The two sets are {S, A, B, C} and {D, T}.

9.3.1 Time Complexity

The time complexity for Ford-Fulkerson is O(F E), where F is the max flow and E is the number of edges.
In the worst case, the flow in the augmenting path will increase by one every time until the maximum flow is
reached. We then need to run BFS F times. It should technically be O(F ) × O(V + E) = O(F (V + E)).
However, we know that a flow network must be a connected graph, so E will dominate V , and we can ignore
V . Therefore, the time complexity is O(F E).

51
 9.4 Feasibility

9.4 Feasibility
Circulation with demands is a feasibility problem. In this case, we will not have a source or sink, and every
node can store some demands. There are two types of feasibility problems, one with a lower bound and one
without. But there is also a quick way to determine feasibility before running the algorithm: If the sum of the
demands is 0, it may be feasible. If not 0, it is directly not feasible.

9.4.1 How to Determine Feasibility

1. Eliminate demand (connect the source to all nodes with negative demand, and connect all nodes with
positive demand to the sink)
2. Run Ford-Fulkerson
3. Retrieve the flow in the graph

Figure 9.5: Feasibility

To retrieve the flow, we look at the final graph after running Ford-Fulkerson. If the original graph has an
edge from x -> y, and in the residual network it has y -> x with a flow of 1, then we will add it to the original
graph, as shown in Figure 9.5. In Figure 9.5, since the flow of both the source and sink are maximized, this
circulation is indeed feasible. But if one of them is not maximized, the circulation will not be feasible.

52
 9.5 Application

9.4.2 Feasibility with Lower Bound

All the steps are essentially the same, but before we eliminate demand, we need to separate out the lower
bound.
1. Separate out the lower bound (for every node, -incoming flow, + outgoing flow. Then for every edge,
subtract the lower bound)
2. Eliminate demand (connect the source to all nodes with negative demand, and connect all nodes with
positive demand to the sink)
3. Run Ford-Fulkerson
4. Retrieve the flow in the graph

Figure 9.6: Feasibility with Lower Bound

To retrieve the flow, we need to include lower_bound/flow/capacity. The first one just indicates the lower bound,
and the second flow will include the lower bound. The rest are the same as the previous example.

9.5 Application
There are various applications for network flow, we will discuss the bipartite matching problem.

9.5.1 Problem
Assume we have 100 students and 4 different time slots. Each student can choose 3 preferred time slots,
but they will only be allocated one. Each time slot can have at most 25 students. How can we assign students to
their classes to ensure that they get one of their preferred time slots?

53
 9.5 Application

9.5.2 Solution
We will create a source vertex connected to all students, with each student represented by a node. From
the source to each student node, we will set a capacity of 1, which means that each student can only be allocated
one slot. Then, we will create 4 extra nodes to represent the time slots. Each time slot node will connect to a
sink node with a capacity of 25, because each time slot can have at most 25 students. Finally, since each student
has three preferences, we will create an edge from each student node to the corresponding time slot nodes to
indicate their preferences. Once the network is set up, we can run the Ford-Fulkerson algorithm to find the
optimal assignment.

Figure 9.7: Bipartite Matching

54
 Chapter 10 String Retrieval Data Structures

A trie is a data structure used to store strings. Some of the key properties are:
Each node in the trie represents a character
We need a terminal node to indicate this path is a word
The path from root to the terminal node represents a word
For each node, we will have an array of N is the number of characters. For example, if I only allow a-b,
then N = 26
Treat each edge as a character (I didn’t include it the figure because it might look messy)

Figure 10.1: Trie

Note that Figure 10 is something we will draw in practice, the actual one will have N characters for each
node. The $ symbol represents the terminal node. So in this example, we have four words: TICKQ, HAHA,
HELLO and HELL. It is very fast to retrieve, but it wastes a lot of spaces

10.0.1 Insertion
When we insert a new word, we will just start from the root and proceed character by character. If current
char doesn’t exist, we will create a new node.
Pseudocode

class Node:
def __init__(self, character):
[Link] = character
[Link] = [None] * 26

class Trie:
...
def insert(self, word):
 10.1 Prefix Tree

current = [Link]
self.insert_aux(current, word, 0)

def insert_aux(self, root, word, level):

if last node:
# Terminal can store frequency
[Link] += 1

character = word[level]
if [Link][character] == None:
[Link][character] = Node(character)
root = [Link][level]
self.insert_aux(root, word, level+1)

You can store a lot of information in the node, like the current char’s frequency or child character with the highest
frequency etc.

[Link] Time Complexity

O(M ), where M is the number of characters in the word
O(T ), where T is the total number of characters if we want to insert a word list

10.0.2 Searching
When you want to search if a word exists in the trie, just follow character by character. If we see a None
halfway, it means the word doesn’t exist. But if we reached the terminal, it means the word exists and we can
return the result.

[Link] Time Complexity

Best case: O(1), if the first character doesn’t exist
Worst case: O(M ), where M is the number of characters in the word if the word exists

10.1 Prefix Tree

A tree is a compressed trie, it means that we can compress the word if there is no extra branches. For
example, Figure 10.1 can be compressed to

56
 10.2 Suffix Tree

Figure 10.2: Prefix Tree

Only the one that have extra branches can’t be compressed.

10.2 Suffix Tree

A suffix tree stores all substrings of a word. For example, for TATAT, the substrings are
TATAT$
ATAT$
TAT$
AT$
T$
Note: for formal proofs we will include $ as the leaf, but general we don’t

57
 10.2 Suffix Tree

T A T A T $
1 2 3 4 5 6
Table 10.1: Suffix Table

Figure 10.3: Suffix Tree

The naive approach will require O(N 2 ) space, but we can improve it with a table.

58
 10.3 Suffix Array and Prefix Doubling

Figure 10.4: Suffix Tree

It will store the [start, end] index in the array. So the space complexity will be reduced to O(N ).

10.2.1 Time Complexity

O(N 2 )/O(N 2 M ), where M is the number of unique characters. Usually we assume it is constant, but if
it is stated in the question we have to include it

10.2.2 Space Complexity

O(N )/O(N M ), where M is the number of unique characters

10.3 Suffix Array and Prefix Doubling

If we want to sort suffixes, we can use algorithm like merge sort that will end up in O(N 2 logN ), O(N 2 ) to
generate the suffixes and O(N 2 logN ) to sort it, because we have O(N ) for string comparison. Or we can even
reduce it to O(N 2 ) using radix sort. However, we can make it quicker by using prefix doubling. The idea is:
1. Generate suffixes
2. Sort the suffixes based on its 1st, 2nd, ..., 2k characters
We can use the rank table to get O(1) comparison, and the sorting time complexity can be reduced to O(N log 2 N ).
If we don’t use the rank table, our complexity is still O(N 2 logN ) because the comparison is O(N ). In the exam,
you will most likely get a rank table: ”Here is the rank table, we have sorted their first 2(k-1) characters. We are
now sorting on the first 2k characters, compare the suffixes”.

59
 10.3 Suffix Array and Prefix Doubling

ID 1 2 3 4 5 6
Rank 3 2 3 4 2 1
Table 10.2: Rank Table

1. We have sorted their first 1 characters. We are now sorting on the first 2 characters, compare the suffixes.
(a). Compare ID1 and ID6
(b). Compare ID2 and ID5
2. We have sorted their first 2 characters. We are now sorting on the first 4 characters, compare the suffixes.
(a). Compare ID1 and ID4
(b). Compare ID1 and ID3

1. Answer
(a). ID1 and ID6 have different rank, and rank[6] < rank[1], so ID6 has lower rank than ID1.
(b). ID2 and ID5 have same rank, as it is 2k = 2 (first 2 characters), k = 1 and we will add 1. ID2 + 1 =
ID3, ID5 + 1 = ID6. ID3 has higher rank than ID6, so ID2 has higher rank than ID5
2. Answer
(a). ID1 and ID4 have different rank, and rank[3] < rank[4], so ID3 has lower rank than ID4.
(b). ID1 and ID3 have same rank, as it is 2k = 4 (first 2 characters), k = 2 and we will add 2. ID1 + 2 =
ID3, ID3 + 2 = ID5. ID3 has higher rank than ID5, so ID1 has higher rank than ID3

Name Best Time Worst Time Auxiliary Space

Trie Construct O(T ) O(T ) O(T )
Trie Retrieval O(M ) O(M ) O(M )
Suffix Trie O(N 2 )/O(N 2 M ) O(N 2 )/O(N 2 M ) O(N )/O(N M )
Suffix Tree O(N 2 )/O(N 2 M ) O(N 2 )/O(N 2 M ) O(N )/O(N M )
Prefix Doubling O(N log 2 N ) O(N log 2 N ) O(N )
Table 10.3: String Retrieval Complexity Table

60
 Chapter 11 Hashing

A hash table is a data structure that stores data with a pair of key and value. Each key will have its own
index obtained through a hash function and its operations like insert, search and delete are O(1). However, the
array size is limited, and we can have more keys than the array size which will lead to collision because multiple
keys might be mapped to the same index by the hash function.

11.1 Collision Resolution

We have two ways to handle collision: open addressing and separate chaining

11.1.1 Open Addressing

In this method, if a collision occurs, we probe the array for the next available slot. There are several probing
strategies like:
Linear Probing: Starting from the initial hash position, check slots sequentially by adding +1, +2, ...,
+n until an empty slot is found. If no empty slot is found, the table is full
Will lead to primary clustering: cluster between different hash values
Quadratic Probing: Starting from the initial hash position, check slots quadratically by adding +12 ,
+22 , ..., +n2 ) to find the next available slot
Will lead to secondary clustering: cluster between same hash value
Might not find a slot even if there is empty slot in the array
Double Hashing: Uses a second hash function to calculate the probe step size
Cuckoo Hashing: Uses two hash tables and two hash functions. If a collision occurs, the existing element
is ”kicked out” and reinserted using the alternate hash function until an empty slot is found

11.1.2 Separate Chaining

In this method, each slot in the hash table contains a linked list/array/BST/AVL Tree. When a collision
occurs, the new key-value pair is simply added to the container at that index. During lookup, we search through
the container at the hashed index to find the desired key. The complexity of different data structures vary:
Linked List
Insert: O(1)
Search: O(1)/O(N )
Delete: O(1)
Array
Insert: O(N )
Search: O(1)/O(N )
Delete: O(N )
Remember we need to shuffle
Binary Search Tree
Insert: O(logN )/O(N )
Search: O(logN )/O(N )
 11.2 Perfect Hash Function

Delete: O(logN )/O(N )

Remember the tree can be imbalanced/balanced
AVL Tree
Insert: O(logN )
Search: O(logN )
Delete: O(logN )
AVL tree is always balanced
Therefore, only AVL tree can ensure O(logN ) complexity, the rest are linear.

11.2 Perfect Hash Function

A perfect hash function is a hash function that can map every key to a unique position. It is doable if
The array size is way bigger than the number of keys
We know all the keys in advance
But it will waste a lot of spaces and it is unrealistic. Nevertheless, we can achieve no collision with a perfect
hash function.

62
 Chapter 12 AVL Tree

We know that for a binary search tree (BST), its operations are not guaranteed to be O(logN ) because
three can be imbalanced and result in O(N ). Therefore, we have AVL tree, which is a self balancing binary
search tree. Since it is always balanced, the search and insert complexity is always O(logN ) because the tree is
balanced.

12.1 Balance Factor

A tree is only balanced if the difference between the height of its left sub-tree and right sub-tree is 1. So for
every node in the tree, we will have a balance factor to calculate whether the tree is balanced or not. The balance
factor will be height(left) - height(right), and the value can only be -1, 0 and 1. In terms of how to balance the
tree, I only know how to use the Ian’s way!

12.2 Examples

12.2.1 Example 1

Figure 12.1: AVL Tree Example 1

 12.2 Examples

Figure 12.1 is an example of a simple imbalanced case. The number below each node means the height
of its left sub-tree and right sub-tree. While calculating it, we will take the max_height(left, right) + 1. For
example, node 15’s left child node, 8 has height of 0 and 1, we will take 1, +1, so the height of node 15’s left
sub-tree is 2. W can see that the difference between the two numbers of node 15 is 2 (2 - 0), so it is imbalanced
and we need to handle this. We will see which side has greater height and move to that direction. As shown in
the figure, it is node 15, node 8 and node 9. We will take the three nodes, take the middle node to be the root
and so on as shown in the bottom example. Then, we simply insert it to the original graph. Now it is balanced.

12.2.2 Example 2
Now the question might be, where should we go if both children have the same height? The answer is: just
follow which direction u went.

Figure 12.2: AVL Tree Example 2.1

In Figure 12.2, node 9 has same height for its children (both 1). So previously node 15 moved left to
node 9, now node 9 will also move left to node 8. You might wonder where you should insert 10, just follow
the property of BST and insert it (left sub-tree smaller than root, right sub-tree greater than root). Since 10 is

64
 12.3 Tips

> 7& > 9& < 15, it should belong to the left child of node 15.
But wait, after balancing it, the root (node 7) still has an imbalanced factor -2 (1-3). So we need to balance
again.

Figure 12.3: AVL Tree Example 2.2

Same goes for this one, after rotating, we know node 2 is left child of node 7, so we just don’t remove it.
Moving on, we know 10 is left child of node 15, don’t remove it too! But node 8 is left child of 9 and 9 became
a root, so we will follow the BST property..

12.3 Tips
Practice inserting and deleting and balancing
Always write the height and balance factor so you don’t mess up or made careless mistakes

65
 Chapter 13 Revision

Complexity
Know to analyze time complexity
What is the best/worst/average/space/output-sensitive
Variants
What if I used linear queue instead of min heap
What if my graph is undirected/directed
What if my graph is sparse/dense
What happened if my edge is negative
What if I changed min heap to max heap
What if I used adjacency list/adjacency matrix
Time complexity must ≤ space complexity
Recurrence Relation
Given an algorithm, can you write the recurrence relation
2*func(n-1) and func(n-1)*func(n-1) are different. One called once, one called twice
Recursion uses aux space, it is not in-place
Do you know how to use Telescoping (for both T(N-1) and T(N//2) cases)
Do you remember Master Theorem (only T(N//2) cases)
Correctness
Loop invariant (before loop/start of loop/after loop/end of loop/termination)
Can you choose the correct invariant
Sorting Algorithm
Do you know what is comparison based and what is non-comparison based
Complexity of counting sort and radix sort
When should we use counting sort
If biggest range is O(N 3 ), should we use counting sort and why
Why is radix sort always linear (most of the time)
What are the application
Can we sort with strings or just number
Divide and Conquer
Quick select application, how to use it in application
Different partitioning (In-place Hoares, DNF), what are their complexity
How to improve quick sort’s best case and worst case time complexity
What is stability? What is stable and what is not
Graphs and Shortest Distance
What are their complexities
Do you understand the code well
How does Dijkstra works
Minimum Spanning Tree
Trees don’t have cycle so it will work with negative edges + negative cycle
What are their applications
 How to convert it to maximum spanning tree (negate the edges? decreasing order? min heap to max
heap?)
What are their complexities?
Is MST unique?
Can Prim and Kruskal obtain the same MST every time?
Dynamic Programming
Do you remember the recurrence relation?
How does each of them work
How to calculate the total ways
What are the complexities
Top down and bottom up
DP Graph Algorithm
Which algorithms work with negative edges which don’t
What does the Floyd Warshall matrix look like after 3 iterations
k is intermediate
What does the Bellman-Ford array look like after running 2 iterations
What is all-pair
Bellman-Ford and Floyd Warshall are DP not greedy
When can it terminate earlier
What to use if the graph is unweighted
What to use if the graph is weighted
Flow Network
What are the complexities? Why O(F E)
What are the applications? What is bipartite matching
How to find min-cut max-flow
How to run Ford-Fulkerson
How to eliminate demand
What if there is lower bound
String Retrieval
Prefix doubling questions (Remember, 2K)
What are their complexities
Why do we use trie? Fast time but waste space?
Hashing
What is a perfect hash function
What are the collision resolution techniques?
Linear Probe
Quadratic Probe
Double Hashing
Cuckoo Hashing
What is primary clustering and secondary clustering
AVL Tree
What is a balance factor
How to balance when you insert/delete

67
 Why it is always O(logN )

Thank you and good luck!

Don’t click on this link

68