Leetcode, Data structure and Algorithm

Leetcode, Data structure and Algorithm

Leetcode, Data structure and Algorithm

1. Introduction

This is the main file that contains all the problems and their solutions. Each problem is organised as follows:

• Problem number Problem name :problemtag:
• Description (Basic info)
• Examples
• Solution (Tackling process)
• Understanding the problem
• Algorithm (written by me)
• Code (written by me)
• Complexity
• Time complexity
• Space complexity
• Leetcode solution
• Time complexity
• Space complexity
• More analysis (Thoughts)
• General thoughts
• Related problems

2. Problems

Here we start to finish our problems 😈.

2.1. Imports for typing

from typing import List, Tuple, Set


2.2.DONE 1313 Decompress Run-length encoded list   array easy

2.2.1. Description

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [freq, val]=[nums[2*i], nums[2*i+1]], i>=0. For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.

Return the decompressed list.

Constraints:

1. 2 <= nums.length <= 100
2. nums.length % 2 == 0
3. 1 <= nums[i] <= 100
2.2.1.1. Examples:
Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2].
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].
At the end the concatenation [2] + [4,4,4] is [2,4,4,4].

Input: nums = [1,1,2,3]
Output: [1,3,3]


2.2.2. Solution

2.2.2.1. Understanding the problem

Just an array problem.

2.2.2.2. Algorithm

We can use for i in range(len(nums), 2) and create a sublist for all nums[i-1], nums[i]. Finally we concatenate these sublists.

2.2.2.3. Code
<<imports for typing>>

def decompress_RLE_list(nums: List[int]) -> List[int]:
res = []
for i in range(0, len(nums), 2):
sub_lst = [nums[i+1] for j in range(nums[i])]
res = res+sub_lst
return res
print(decompress_RLE_list([1,1,2,3]))

[1, 3, 3]

2.2.2.4. Complexity
2.2.2.4.1. Time complexity:

$$O(M)\text{, where } M=\sum_{i=0,2,4...}^{len(nums)-2}nums[i]$$, the summation corresponds to the outer for loop, we simply sum up the time it takes to build each sub list.

2.2.2.4.2. Space complexity:

$$O(M)\text{, where } M=\sum_{i=0,2,4...}^{len(nums)-2}nums[i]$$

Not available.

2.2.3. More analysis

2.2.3.1. General thoughts

To concatenate lists in Python.

lst1=[1,2,3]
lst2=[3,3,3]
print(lst1+lst2)

[1, 2, 3, 3, 3, 3]


2.3.DONE 1295 Find numbers with even number of digits   array easy

2.3.1. Description

Given an array nums of integers, return how many of them contain an even number of digits.

Constraints:

1. 1 <= nums.length <= 500
2. 1 <= nums[i] <= 105
2.3.1.1. Examples:
Input: nums = [12,345,2,6,7896]
Output: 2
Explanation:
12 contains 2 digits (even number of digits).
345 contains 3 digits (odd number of digits).
2 contains 1 digit (odd number of digits).
6 contains 1 digit (odd number of digits).
7896 contains 4 digits (even number of digits).
Therefore only 12 and 7896 contain an even number of digits.

Input: nums = [555,901,482,1771]
Output: 1
Explanation:
Only 1771 contains an even number of digits.


2.3.2. Solution

2.3.2.2. Algorithm

We simply loop the nums and check each number. We can use this to get the number of all digits of a number: len(str(num)).

2.3.2.3. Code
<<imports for typing>>

def find_numbers(nums: List[int]) -> int:
res = 0
for ele in nums:
if len(str(ele)) % 2 == 0:
res += 1
return res
print(find_numbers([1,2,3]))
print(find_numbers([11,2,3]))

0
1

2.3.2.4. Complexity
2.3.2.4.1. Time complexity:

$$O(N)$$.

2.3.2.4.2. Space complexity:

$$O(N)$$.

Not available.

2.3.3. More analysis

2.3.3.1. General thoughts

Pretty straightforward.

2.4.DONE 1365 How many numbers are smaller than the current number   array easy

2.4.1. Description

Given the array nums, for each nums[i], find out how many numbers in the array are smaller than it. That is, for each nums[i], you have to count the number of valid j's, such that j != i and nums[j] < nums[i]>.

Return the answer in an array.

Constraints:

1. 2 <= nums.length <= 500
2. 0 <= nums[i] <= 100
2.4.1.1. Examples:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Input: nums = [7,7,7,7]
Output: [0,0,0,0]


2.4.2. Solution

2.4.2.2. Algorithm

We first sort nums, and get sorted_nums. We loop through sorted_nums, and get smaller_count mapping in the form of {num: smaller_count}. We then loop nums and get smaller_count of each num, store them in res.

2.4.2.3. Code
<<imports for typing>>

def smaller_numbers_than_current(nums: List[int]) -> List[int]:
import math
sorted_nums = sorted(nums)

smaller_counts = {}
for i, e in enumerate(sorted_nums):
smaller_counts[e] = min(smaller_counts.get(e, math.inf), i)

res = []
for num in nums:
res.append(smaller_counts[num])

return res
print(smaller_numbers_than_current([2,2,3,4,1]))

[1, 1, 3, 4, 0]

2.4.2.4. Complexity
2.4.2.4.1. Time complexity:

$$O(N\log{N})$$.

2.4.2.4.2. Space complexity:

$$O(N)$$.

Not available.

2.4.3. More analysis

2.4.3.1. General thoughts

The best time complexity we can do is $$O(N\log N)$$.

2.5.DONE 1409 Queries on a permutation with key   array medium

2.5.1. Description

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

1. in the beginning, you have the permutation P=[1,2,3,...,m].
2. For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the begining of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Constraints:

1. 1 <= m <= 103
2. 1 <= queries.length <= m
3. 1 <= queries[i] <= m
2.5.1.1. Examples:
Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1]
Explanation: The queries are processed as follow:
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5].
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5].
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5].
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5].
Therefore, the array containing the result is [2,1,2,1].

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]


2.5.2. Solution

2.5.2.2. Algorithm

We can use brute force. We loop through queries for i, e in enumerate(queries), then have an inner loop for j, e_p in enumerate(p_copy), when e_p==e, we do P.pop(j), P.insert(0, e_p), and res.append(j).

2.5.2.3. Code
<<imports for typing>>

def process_queries(queries: List[int], m: int) -> List[int]:
res = []

p = list(range(1, m+1))
p_copy = p.copy()
for i, e in enumerate(queries):
p_copy = p.copy()
for j, e_p in enumerate(p_copy):
if e_p == e:
p.pop(j)
p.insert(0, e_p)
res.append(j)

return res

print(process_queries([3,1,2,1],5))

[2, 1, 2, 1]

2.5.2.4. Complexity
2.5.2.4.1. Time complexity:

$$O(N\times M)\text{ , where }N=len(queries), M=m$$.

2.5.2.4.2. Space complexity:

$$O(M)$$.

2.5.2.5. Leetcode solution

Not available.

Here is one interesting solution from the discussion forum.

<<imports for typing>>

def process_queries(queries: List[int], m: int) -> List[int]:
# the original code uses
# def process(arr, idx), which is quite confusing
# as we are trying to find the idx of an element
def process(arr, elem):
ans = arr.index(elem)
arr.insert(0, arr.pop(ans))
return ans

m = [x for x in range(1, m+1)]
return [process(m, i) for i in queries]

print(process_queries([3,1,2,1],5))

[2, 1, 2, 1]

2.5.2.5.1. Time complexity:

$$O(N\times M)\text{ , where }N=len(queries), M=m$$.

2.5.2.5.2. Space complexity:

$$O(M)$$.

2.6. 1329 Sort the matrix diagonally

This is based on an incorrect understanding of the problem description. See 2.7 for a correct understanding and solution.

2.6.1. Description

Given a m*n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Constraints:

1. m == mat.length
2. n == mat[i].length
3. 1 <= m, n <= 100
4. 1 <= mat[i][j] <= 100
2.6.1.1. Examples:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]


2.6.2. Solution

2.6.2.2. Algorithm

We first concatenate all lists in the matrix, then sort it to get sorted_lst. Then we re-construct the resulting matrix and return it. Then we create a new empty m*n matrix res filled with None. We then loop through sorted_lst, and fill the first row of res, then the first column, then second row, second column… Recall that a 2D array can be mapped to a 1D array.

2.6.2.3. Code
<<imports for typing>>

def diagonal_sort(mat: List[List[int]]) -> List[List[int]]:
import itertools

m = len(mat)
n = len(mat[0])
res = [[None for i in range(n)] for j in range(m)]
sorted_lst = sorted(itertools.chain(*mat))

cur_col = 0
cur_row = 0

idx = 0
while cur_col < n or cur_row < m:
if cur_col < n:
for moving_col in range(cur_col, n):
res[cur_row][moving_col] = sorted_lst[idx]
idx += 1

# cur_row+1 so that it does not overwrite
# the first data in the column
if cur_row < m:
for moving_row in range(cur_row+1, m):
res[moving_row][cur_col] = sorted_lst[idx]
idx += 1

cur_col = min(n-1, cur_col+1)
cur_row = min(m-1, cur_row+1)
if cur_col == n-1 and cur_row == m-1 and res[m-1][n-1] is not None:
break
return res
#print(diagonal_sort([[2,1],[3,2],[3,2]]))
#print(diagonal_sort([[1,2,1],[3,2,4],[7,7,4]]))
#print(diagonal_sort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
print(diagonal_sort(
[[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
))

[[1, 4, 5, 7, 8, 11], [11, 22, 23, 25, 25, 27], [14, 28, 36, 44, 45, 50], [15, 31, 52, 58, 66, 68], [17, 33, 55, 69, 75, 84]]


2.7.DONE 1329 Sort the matrix diagonally 2   array medium

2.7.1. Description

Given a m*n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Constraints:

1. m == mat.length
2. n == mat[i].length
3. 1 <= m, n <= 100
4. 1 <= mat[i][j] <= 100
2.7.1.1. Examples:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]


2.7.2. Solution

2.7.2.2. Algorithm

With the existing mat, we want to sort each existing diagonal so that they are ascend from top-left to bottom right. We do not want to sort the entire matrix.

We need to first get all the starting cell of each diagonal list (x, y). With it, we can easily get the diagonal list by adding 1 to both x and y. We then sort each diagonal list and put them back to the mat.

2.7.2.3. Code
<<imports for typing>>

def diagonal_sort(mat: List[List[int]]) -> List[List[int]]:
n = len(mat)
m = len(mat[0])

res = []
while x < n and y < m:
res.append(mat[x][y])
x+=1
y+=1

res.sort()
res = iter(res)
while x < n and y < m:
mat[x][y] = next(res)
x+=1
y+=1

diagonal_heads = [(x, y) for x in range(n) for y in range(m)]

return mat
print(diagonal_sort([[4,2,3],[1,3,4]]))
print(diagonal_sort([[2,1],[3,2],[3,2]]))
print(diagonal_sort([[1,2,1],[3,2,4],[7,7,4]]))
print(diagonal_sort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
print(diagonal_sort(
[[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
))

[[3, 2, 3], [1, 4, 4]]
[[2, 1], [2, 2], [3, 3]]
[[1, 2, 1], [3, 2, 4], [7, 7, 4]]
[[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]
[[5, 17, 4, 1, 52, 7], [11, 11, 25, 45, 8, 69], [14, 23, 25, 44, 58, 15], [22, 27, 31, 36, 50, 66], [84, 28, 75, 33, 55, 68]]

2.7.2.4. Complexity
2.7.2.4.1. Time complexity:

This is a bit hard to analyse, but the basic idea is to add up all the time taken to sort all diagonal lists. The total number of such lists is $$m+n-1$$. By observation, we can get that the number of the longest diagonal list(s) in the matrix is $$|n-m+1|$$. The number of remaining lists would be $$m+n-1-|n-m+1|$$, which gives us either $$2\times (m-1)$$ or $$2\times (n-1)$$.

Therefore, our formula to calculate the total time required by the algorithm is as follows:

$$O(2\times (\sum_{i=1}^{\min(n,m)-1} i\log i)+|n-m+1|\times \min(m,n)\times \log{\min(m,n)})$$.

2.7.2.4.2. Space complexity:

$$O(\sqrt{m\times n})$$.

2.7.2.5. Leetcode solution

Not available.

Interesting one here.

def diagonal_sort(mat):
m, n = len(mat), len(mat[0])

def sort(i, j):
ij = zip(range(i, m), range(j, n))
vals = iter(sorted(mat[i][j] for i, j in ij))
for i, j in ij:
mat[i][j] = next(vals)

for i in range(m): sort(i, 0)
for j in range(m): sort(0, j)

return mat

print(diagonal_sort([[4,2,3],[1,3,4]]))
print(diagonal_sort([[2,1],[3,2],[3,2]]))
print(diagonal_sort([[1,2,1],[3,2,4],[7,7,4]]))
print(diagonal_sort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
print(diagonal_sort(
[[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
))

[[4, 2, 3], [1, 3, 4]]
[[2, 1], [3, 2], [3, 2]]
[[1, 2, 1], [3, 2, 4], [7, 7, 4]]
[[3, 3, 1, 1], [2, 2, 1, 2], [1, 1, 1, 2]]
[[11, 25, 66, 1, 69, 7], [23, 55, 17, 45, 15, 52], [75, 31, 36, 44, 58, 8], [22, 27, 33, 25, 68, 4], [84, 28, 14, 11, 5, 50]]


2.8.DONE 1395 Count number of teams   array medium

2.8.1. Description

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

1. Choose 3 soldiers with index(i, j, k) with rating (rating[i], rating[j], rating[k]).
2. A team is valid if: (rating[i]<rating[j]<rating[k]) or rating[i]>rating[j]>rating[k], where 0<=i<j<k<n.

Soldiers can be part of multiple teams.

Return the number of teams you can form given the conditions.

Constraints:

1. n == rating.length
2. 1 <= n <= 200
3. 1 <= rating[i] <= 105
2.8.1.1. Examples:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Input: rating = [1,2,3,4]
Output: 4


2.8.2. Solution

2.8.2.2. Algorithm

We return False for all n<3.

This is a combination problem. We need to try all combinations of the list.

2.8.2.3. Code
<<imports for typing>>
def num_teams(rating: List[int]) -> int:
if len(rating) < 3:
return 0

from itertools import combinations

count = 0
for comb in combinations(rating, 3):
if comb[0] < comb[1] < comb[2] or comb[0]>comb[1]>comb[2]:
count += 1

return count
print(num_teams([2,5,3,4,1]))
print(num_teams([2,1,3]))
print(num_teams([1,2,3,4]))
print(num_teams([0,1]))

3
0
4
0

2.8.2.4. Complexity
2.8.2.4.1. Time complexity:

$$O(C_{n}^{3})$$, i.e. $$O(n^3)$$.

2.8.2.4.2. Space complexity:

$$O(1)$$.

2.8.2.5. Leetcode solution

Not available.

This following is adapted from this Java solution.

<<imports for typing>>
def num_teams(rating: List[int]) -> int:
ans = 0
n = len(rating)

biggerLeft, biggerRight = {}, {}

for i in range(n-1):
for j in range(i+1, n):
if rating[i] < rating[j]:
biggerRight[i] = biggerRight.get(i, 0) + 1
elif rating[i] > rating[j]:
biggerLeft[j] = biggerLeft.get(j, 0) + 1

for i in range(n-1):
for j in range(i+1, n):
if rating[i] < rating[j]:
ans += biggerRight.get(j, 0)
elif rating[i] > rating[j]:
ans += biggerLeft.get(i, 0)
return ans
print(num_teams([2,5,3,4,1]))
print(num_teams([2,1,3]))
print(num_teams([1,2,3,4]))
print(num_teams([0,1]))

3
0
4
0

2.8.2.5.1. Time complexity:

$$O(N^2)$$.

2.8.2.5.2. Space complexity:

$$O(N)$$.

2.8.3. More analysis

2.8.3.1. General thoughts

Brute-forcing this problem should be prohibited as this is medium level problem. We should try to use some better algorithms to solve it.

2.8.2.5 is a neat solution to the problem and a specia case of a general solution, which is provided here.

<<imports for typing>>

def calc_combinations(n: int, k: int) -> int:
"""
n: total number of items
k: number of items to be drawn
"""
calculated = {}
def factorial(n: int) -> int:
if n == 0 or n == 1:
return 1
if n not in calculated.keys():
calculated[n] = n * factorial(n-1)
return calculated[n]

if n < k :
return 0
return int(factorial(n)/factorial(k)/factorial(n-k))

def num_teams(rating: List[int], team_len: int = 3) -> int:
ans = 0
n = len(rating)

biggerLeft, biggerRight = {}, {}

for i in range(n-1):
for j in range(i+1, n):
if rating[i] < rating[j]:
biggerRight[i] = biggerRight.get(i, 0) + 1
elif rating[i] > rating[j]:
biggerLeft[j] = biggerLeft.get(j, 0) + 1

for i in range(n-1):
for j in range(i+1, n):
if rating[i] < rating[j]:
# team_len-2 gives the remaining numbers that need to be drawn
# from biggerRight.get(j, 0) given rating[i] and rating[j]
ans += calc_combinations(biggerRight.get(j, 0), team_len-2)
elif rating[i] > rating[j]:
ans += calc_combinations(biggerLeft.get(i, 0), team_len-2)
return ans
print(num_teams([2,7,8,9,10], 4))
print(num_teams([2,1,3]))
print(num_teams([1,2,3,4]))
print(num_teams([0,1]))

5
0
4
0


2.9.DONE 442 Find all duplicates in an array   array medium

2.9.1. Description

Given an array of integers, $$1\le a[i] \le n, n=\text{size of array}$$, some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Constraints: Do it without extra space and in $$O(n)$$ runtime.

2.9.1.1. Examples:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]


2.9.2. Solution

2.9.2.2. Algorithm

See Discussion.

$$\because$$: Given the condition $$\max(arr)\le \text{len}(arr)$$, we know that each number element in the array should be able to be mapped to an index of the array.

We also know that, a number in the array either occurs just once or twice.

$$\therefore$$: when iterating the array, we can mark the number at index i negative when we first encounter it. If we never see it again, then we can safely ignore it (once). The second time we see it and it's negative, we add it to the final result (twice).

2.9.2.3. Code
<<imports for typing>>

def find_duplicates(nums: List[int]) -> List[int]:
res = []
for n in nums:
if nums[abs(n)-1] < 0:
res.append(abs(n))
else:
nums[abs(n)-1] *= -1
return res

print(find_duplicates([1,2,3,3]))

[3]

2.9.2.4. Complexity
2.9.2.4.1. Time complexity:

$$O(N)$$.

2.9.2.4.2. Space complexity:

$$O(1)$$, excluding the returning result res.

2.9.2.5. Leetcode solution

Not available.

Most interesting idea has been provided in the previous section.

<<imports for typing>>



2.10.DONE 78 Subsets   array medium

2.10.1. Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Constraints: The solution set must not contain duplicate subsets.

2.10.1.1. Examples:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]


2.10.2. Solution

2.10.2.2. Algorithm

We can use Python's itertools.combinations.

2.10.2.3. Code
<<imports for typing>>

def subsets(nums: List[int]) -> List[List[int]]:
from itertools import combinations, chain

res = [combinations(nums, i) for i in range(1, len(nums) + 1)]
return list(map(list, chain(*res))) + [[]]
print(subsets([1,2,3]))

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3], []]

2.10.2.4. Complexity
2.10.2.4.1. Time complexity:

$$O(\frac{N!}{(N-K)!K!})$$

2.10.2.4.2. Space complexity:

$$O(\frac{N!}{(N-K)!K!})$$

2.10.2.5. Leetcode solution

Bitmask solution. The idea is that we map each subset to a bitmask of length n, where 1 on the ith position in the bitmask meas the presence of nums[i] in the subset, and 0 means its absence.

<<imports for typing>>

def subsets(nums: List[int]) -> List[List[int]]:
n = len(nums)
output = []

# nth_bit = "1000"
nth_bit = 1<<n
for i in range(2**n):
# generate bit mask, from 0..00 to 1..11
# append subset corresponding to that bit mask
output.append([nums[j] for j in range(n) if bitmask[j] == '1'])

return output
print(subsets([1,2,3]))

0b1000
000
0b1001
001
0b1010
010
0b1011
011
0b1100
100
0b1101
101
0b1110
110
0b1111
111
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

2.10.2.5.1. Time complexity:

$$O(\frac{N!}{(N-K)!K!})$$

2.10.2.5.2. Space complexity:

$$O(\frac{N!}{(N-K)!K!})$$

See 5.1.1

2.11.DONE 48 Rotate image   array medium

2.11.1. Description

You are given an n*n 2D matrix representing an image.

Rotate the image 90 degrees (clockwise).

Constraints:

You have to rotate the image in-place.

2.11.1.1. Examples:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]


2.11.2. Solution

2.11.2.2. Algorithm

Given the coordinate of a point (row, col) in the matrix mat (n*n), to rotate a matrix clockwise by 90 degrees is to do the following: map(lambda (row, col): (col, n-1-row), mat).

2.11.2.3. Code
<<imports for typing>>

def rotate(matrix: List[List[int]]) -> None:
import math
n = len(matrix)
def rotate_square(mat: List[List[int]], coor: Tuple[int]) -> None:
row, col = coor
target_val = mat[col][n-1-row]
mat[col][n-1-row] = mat[row][col]

row, col = col, n-1-row
temp = mat[col][n-1-row]
mat[col][n-1-row] = target_val

row, col = col, n-1-row
target_val = mat[col][n-1-row]
mat[col][n-1-row] = temp

row, col = col, n-1-row
mat[col][n-1-row] = target_val

for cur_row in range(math.ceil(n/2)):
for cur_col in range(cur_row, n-cur_row-1):
rotate_square(matrix, (cur_row, cur_col))

print(matrix)

rotate([[1,2],[3,4]])
rotate([[1,2,3],[4,5,6],[7,8,9]])
rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]])

[[3, 1], [4, 2]]
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
[[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

2.11.2.4. Complexity
2.11.2.4.1. Time complexity:

$$O(N^2)$$.

2.11.2.4.2. Space complexity:

$$O(1)$$

2.11.2.5. Leetcode solution

Not available.

<<imports for typing>>



2.11.3. More analysis

2.11.3.1. General thoughts

My solution is very cumbersome, especially the rotate_square() function. As shown in the Leetcode discussion forum, it is easier to flip the matrix instead of actually rotating it because flip the matrix only involves swapping two values. Whereas my rotate_square() involves introducing two temporary variables to finish a rotation.

The other way to mitigate the problem in my solution is to use the following code, which does the rotation of four elements at once.

matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j], matrix[n - 1 - j][i]
= matrix[n - 1 - j][i], matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j]


2.12.DONE 72 Edit distance   dp hard

2.12.1. Description

Given two words, word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

Constraints:

2.12.1.1. Examples:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')


2.12.2. Solution

2.12.2.2. Algorithm

This is a typical dynamic programming problem.

2.12.2.3. Code
<<imports for typing>>

def min_distance(word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)

if m == 0:
return n
if n == 0:
return m

tbl = [[0 for j in range(n+1)] for i in range(m+1)]

for i in range(m+1):
for j in range(n+1):
if i == 0:
tbl[i][j] = j
elif j==0:
tbl[i][j] = i
elif word1[i-1] == word2[j-1]:
tbl[i][j] = tbl[i-1][j-1]
else:
tbl[i][j] = 1 + min(
tbl[i-1][j],
tbl[i][j-1],
tbl[i-1][j-1]
)

return tbl[m][n]

2.12.2.4. Complexity
2.12.2.4.1. Time complexity:

$$O(MN)$$

2.12.2.4.2. Space complexity:

$$O(MN)$$

2.12.2.5. Leetcode solution

Not available.

<<imports for typing>>



See 4.2.1.

2.13.DONE 121 Best time to buy and sell stock   array hard dp

2.13.1. Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Constraints: You cannot sell a stock before you buy one.

2.13.1.1. Examples:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.


2.13.2. Solution

2.13.2.2. Algorithm

We build up a table of all possible combinations from the prices list. Half of the table is not necessary. We first sort the list prices and convert it to a ordered map that {price: day}. Then we start from the lowest price p_low, and check it against the highest price p_hi, if price[p_hi]>price[p_low], we already find one candidate of the result and move p_low to the right, else, we move p_hi to the left.

2.13.2.3. Code
<<imports for typing>>

def max_profit(prices: List[int]) -> int:

max_p = 0

price_map = {}
for i, p in enumerate(prices):
if p not in price_map.keys():
price_map[p] = i

prices.sort()

for p_sell in reversed(prices):
d_sell = price_map[p_sell]
break

return max_p
print(max_profit([7,1,5,3,6,4]))
print(max_profit([7,6,5]))
print(max_profit([1,4,1,4,3,1]))

5
0
3

2.13.2.5. Leetcode solution

If we plot the numbers in the array on a graph, we will have a line graph.

The points of interest are the peaks and valleys in the given graph. We need to find the highest peak, following the lowest valley. We can maintain two variables - minprice and maxprofit corresponding to the lowest valley and maximum profit (max difference between selling price and minprice) obtained so far respectively.

<<imports for typing>>

def max_profit(prices: List[int]) -> int:
from math import inf
minprice = inf
maxprofit = 0

for i in range(len(prices)):
if prices[i] < minprice:
minprice = prices[i]
elif prices[i] - minprice > maxprofit:
maxprofit = prices[i] - minprice

return maxprofit
print(max_profit([1,2,3,4,5]))

4

2.13.2.5.1. Time complexity:

$$O(N)$$

2.13.2.5.2. Space complexity:

$$O(1)$$

2.13.3. More analysis

2.13.3.1. General thoughts

Initially I was trying to use dynamic programming to solve this problem, as is indicated by the problem's DP tag, then it was very hard to start because the problem does not seem to have an obvious subproblems that will be solved multiple times.

The solutions provided by Leetcode did not use DP either, but then other people suggested that it can be categorised as a very simple DP problem and tabulation can be used to solve it.

The prerequisites for using DP are:

1. optimal substructure
2. overlaping sub-problems

In this problem, sub-problems f[i] is defined as "the minimum stock price from day 0 to day i", which is dependant on f[i-1] and prices[i], whichever is lower. The overlapping sub-problem here is very obvious - there's no need to calculate f[i] by comparing stock prices from day 0 to day i-1, which is the brute force solution, but just reuse the pre-calculated result f[i-1].

maxprofit variable may or may not be in the DP table, as it can be viewed as a simple global max, and we can simply get it by maxprofit=max(maxprofit, prices[i-1]-dp[i-1][0]).

Also people mentioned that this is similar to Kadane's Algorithm for Maximum Subarray Sum.

def max_profit(prices) -> int:
from math import inf

n = len(prices)
dp = [[0, 0] for i in range(n+1)]

# starting price
dp[0][0] = inf

for i in range(1, n+1):
dp[i][0] = min(dp[i-1][0], prices[i-1])
dp[i][1] = max(dp[i-1][1], prices[i-1]-dp[i-1][0])

return dp[n][1]
print(max_profit([1,2,3,4,5]))

4


2.14.DONE 53 Maximum subarray   dp easy

2.14.1. Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Constraints: Use $$O(N)$$ time.

2.14.1.1. Examples:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


2.14.2. Solution

2.14.2.2. Algorithm

Use dynamic programming. The sub-problem is "the maximum sum of previous arrays".

2.14.2.3. Code
<<imports for typing>>

def max_subarray(nums: List[int]) -> int:
from math import inf
n = len(nums)
if n == 1:
return nums[0]

# this is actualy not needed
# see General thoughts
dp = [0 for i in range(n+1)]
dp[0] = -inf

for i in range(1, n+1):
dp[i] =max(nums[i-1], nums[i-1] + dp[i-1])

return max(dp)
print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))
print(max_subarray([-2,1]))

6
1

2.14.2.4. Complexity
2.14.2.4.1. Time complexity:

$$O(N)$$.

2.14.2.4.2. Space complexity:

$$O(N)$$ but $$O(1)$$ can be achieved by removing the dp array.

2.14.2.5. Leetcode solution

Not available.

<<imports for typing>>



2.14.3. More analysis

2.14.3.1. General thoughts

Wikipedia introduces the history of this problem as "a simplified model for maximum likelihood estimate of patterns in digitized images".

In this problem, $$O(1)$$ space can be achieved.

<<imports for typing>>

def max_subarray(nums: List[int]) -> int:
from math import inf
n = len(nums)
if n == 1:
return nums[0]

cur_sum = -inf
best_sum = cur_sum

for i in range(1, n+1):
cur_sum =max(nums[i-1], nums[i-1] + cur_sum)
best_sum = max(best_sum, cur_sum)

return best_sum
print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))
#print(max_subarray([-2,1]))

6

2.14.3.2. Related problems

2.13 The minprice in 2.13 is the cur_sum in this question, and maxprofit in 2.13 is the best_sum in this question.

2.15.DONE 70 Climbming stairs   dp easy

2.15.1. Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climbe 1 or 2 steps. In how many distinct ways you can climb to the top?

Constraints: n will be positive integer.

2.15.1.1. Examples:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step


2.15.2. Solution

2.15.2.2. Algorithm

This is basically a Fibonacci series. We need to do a "top-down" calculation of the ways we can take. Starting from the top (n), there are two ways to go back (one step or two steps), and we are at n-1. By the same token, when we are at n-1, for the two different stairs we are at, there are two stairs we can take for each of them. We first calculate one of them, and store the number of ways to go down in a map. This map can be later used for calculating another possibility at n-1.

We continue this until we reach the bottom.

We then do addition: ans[n] = ans[n-1]+ans[n-2]. The code is written in "bottom-up" format. Somehow for me it is easier to think this way. Previously mentioned algorithm still works but is hard for me to implement as I am not sure how to solve the recursive part when we use a map to simplify calculation.

2.15.2.3. Code
<<imports for typing>>

def climb_stairs(n: int) -> int:
dp = [0 for i in range(n+1)]

dp[0], dp[1] = 1, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(climb_stairs(4))

5

2.15.2.4. Complexity
2.15.2.4.1. Time complexity:

$$O(n)$$.

2.15.2.4.2. Space complexity:

$$O(n)$$.

2.15.2.5. Leetcode solution

There are 6 approaches on Leetcode.

1. Approach 1 is brute force.
2. Approaches 2 to 4 are essentially the same as my solution.
3. Approach 5 uses Binets Method, which uses matrix multiplication to obtain the $$n^{th}$$ Fibonacci number. Its time complexity is $$\log(n)$$. Space complexity is $$O(1)$$.
4. Approach 6 just uses the Fibonacci Formula to calculate the $$n^{th}$$ Fibonacci number. It is asymptotically the same as approach 5. However, precision of calculation is lost when n is big and the formula will give an incorrect number.

Here we take the formula solution.

<<imports for typing>>

def climb_stairs(n: int) -> int:
sqrt5=pow(5, 1/2)
fibn = pow((1+sqrt5)/2, n+1)-pow((1-sqrt5)/2,n+1)
return int(fibn/sqrt5)
print(climb_stairs(5))

8


2.15.3. More analysis

2.15.3.1. General thoughts

It is amazing how we can optimise this seemingly daunting problem such dramatically from $$O(2^n)$$ to $$\log(n)$$!.

2.16.DONE 746 Min cost climbing stairs   dp easy

2.16.1. Description

On a staircase, the $$i^{th}$$ step has some 0 indexed non-negative cost cost[i] assigned.

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0 or with index 1.

Constraints:

1. cost will have a length in the range [2, 1000]
2. Every cost[i] will be an integer in the range [0, 999].
2.16.1.1. Examples:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].


2.16.2. Solution

2.16.2.2. Algorithm

This is an optimal problem. The final problem, "minimum cost to reach the top of the floor" can be divided into two subproblems, namely, the minimum cost to reach to the previous two possible stairs. We have $$min_cost_n=min(min_cost_{n-1}, min_cost_{n-2})$$, and that $$min_cost_{n-1}$$ and $$min_cost_{n-2}$$ have overlapping subsubproblems. Therefore, we can use dynamic programming to solve this problem.

2.16.2.3. Code
<<imports for typing>>

def min_cost_climbing_stairs(cost: List[int]) -> int:
from math import inf
n = len(cost)
min_cost = [inf for i in range(n)]

min_cost[0], min_cost[1] = cost[0], cost[1]
for i in range(2, n):
min_cost[i] = min(min_cost[i-1], min_cost[i-2])+cost[i]

return min(min_cost[n-1], min_cost[n-2])
print(min_cost_climbing_stairs([1, 100, 1,1,1,100,1,1,100,1]))

6

2.16.2.4. Complexity
2.16.2.4.1. Time complexity:

$$O(N)$$.

2.16.2.4.2. Space complexity:

$$O(N)$$.

2.16.2.5. Leetcode solution

The explanation from Leetcode is not very intuitive or clear. The concept is the same as mine, but the way it explains things is very twisted.

Basically, they want i in range(n, 1, -1), and then calculate each f[i] which is the total cost of the current floor.

Intuition: There is a clear recursion available: the final cost f[i] to climb the staircase from some step i is f[i] = cost[i] + min(f[i+1], f[i+2]). This motivates dynamic programming.

Algorithm: Let's evaluate f backwards in order. That way, when we are deciding what f[i] will be, we've already figured out f[i+1] and f[i+2].

We can do even better than that. At the i-th step, let f1, f2 be the old value of f[i+1], f[i+2], and update them to be the new values f[i], f[i+1]. We keep these updated as we iterate through i backwards. At the end, we want min(f1, f2).

<<imports for typing>>

def min_cost_climbing_stairs(cost: List[int]):
f1 = f2 = 0
for x in reversed(cost):
f1, f2=x+min(f1, f2), f1

return min(f1, f2)
print(min_cost_climbing_stairs([10,14,10]))

14


Based on the Leetcode solution, we can improve our code to get $$O(1)$$ space complexity.

<<imports for typing>>

def min_cost_climbing_stairs(cost: List[int]) -> int:
from math import inf
n = len(cost)

mc1, mc2 = cost[0], cost[1]

for i in range(2, n):
mc1, mc2 = mc2, min(mc1, mc2)+cost[i]

return min(mc1, mc2)
print(min_cost_climbing_stairs([1, 100, 1,1,1,100,1,1,100,1]))

6

2.16.2.5.1. Time complexity:

$$O(N)$$

2.16.2.5.2. Space complexity:

$$O(1)$$

2.16.3. More analysis

2.16.3.1. General thoughts

Again, to determine if a question fits dynamic programming, we want to determine if:

1. It asks for an optimal solution
2. It can be divided into finding the optimal solution to subproblems
3. The subproblems have overlapping subsubproblems
1. DP's goal is to only solve these overlapping problems once to save time
4. A recursive definition of the optimal solution can be found

2.17.DONE 703 Kth largest element in a stream   heap

2.17.1. Description

Design a class to find the K th largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the modified stream.

Constraints: You may assume that nums.length>=k-1 and k>=1.

2.17.1.1. Examples:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);


2.17.2. Solution

2.17.2.2. Algorithm

See 6.4.

Brute-force algorithm:

• constructing the object
• simply sort the nums array and store it in self.nums
• running the KthLargest.add(val) method
• insert the val in to the sorted self.nums, then get self.nums[2]
2.17.2.3. Code
<<imports for typing>>

class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.nums = sorted(nums, reverse=True)

def add(self, val: int) -> int:
for i in range(len(self.nums)):
if val > self.nums[i]:
self.nums.insert(i, val)
break

else:
self.nums.append(val)

return self.nums[self.k-1]

k=3
arr=[4,5,8,2]
obj = KthLargest(k, arr)

4
5
5
8
8

2.17.2.3.1. Complexity
1. Time complexity:

Initial sorting: $$O(n\lg n)$$. The add method: $$O(n)$$.

2. Space complexity:

$$O(n)$$.

2.17.2.4. Leetcode solution

Not available.

6.7.4 was used by many to solve the problem.

The question was probably asking us to implement the (max) priority queue.

The following solution uses Python's heapq data structure.

<<imports for typing>>

import heapq
class KthLargest:

def __init__(self, k: int, nums: List[int]):
self.arr = []
self.n = k
for i in nums: self._push(i)

def _push(self, val: int):
if len(self.arr) == self.n:
top = heapq.heappop(self.arr)
if top > val:
heapq.heappush(self.arr, top)
else:
heapq.heappush(self.arr, val)

else:
heapq.heappush(self.arr, val)

def add(self, val: int) -> int:
self._push(val)
return self.arr[0] if len(self.arr) else None

nums = [10,9,8,7]
k=3
obj = KthLargest(k, nums)
val=6
print(param_1)

8

2.17.2.4.1. Time complexity:

Initial sorting: $$O(n\lg n)$$. The add() method: $$O(\lg n)$$.

2.17.2.4.2. Space complexity:

$$O(n)$$.

2.17.3. More analysis

2.17.3.1. General thoughts

The heapq provided by Python follows min-heap properties.

• arr[0] is the smallest element
• arr[k]<arr[2k+1], arr[k]<arr[2k+2]

We can modify the Leetcode solution to make it use less memory in theory since we are dealing with a stream and do not care about storing it. Basically, we chop off the list after each add(val) operation, so the list has only k elements.

<<imports for typing>>

class KthLargest:
import heapq

def __init__(self, k: int, nums: List[int]):
self.k = k
self.arr = nums
heapq.heapify(self.arr)
self._chop_off_queue()

def add(self, val: int) -> int:
heap_top = 0

# always keep heap size = k
# Top element = kth largest element
if len(self.arr) < self.k:
heapq.heappush(self.arr, val)
else:
heapq.heappushpop(self.arr, val)

return self.arr[heap_top]

def _chop_off_queue(self):
while len(self.arr) > self.k:
# heappop() pops the smallest element
heapq.heappop(self.arr)

2.17.3.2. Related problems

See 6.3.1 and 6.7.4.

2.18.DONE 215 Kth largest element in an array   heap

2.18.1. Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Constraints: You may assume k is always valid, 1 ≤ k ≤ array's length.

2.18.1.1. Examples:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4


2.18.2. Solution

2.18.2.2. Algorithm

We can use quicksort.

See 6.4 for theory discussion and linear time algorithm (randomized quickselect).

2.18.2.3. Code
<<imports for typing>>

def find_kth_largest(nums: List[int], k: int) -> int:
return sorted(nums)[k-1]
print(find_kth_largest([3,2,1,5,6,4], 2))

2


Quickselect implementation (a replica of 6.4.2).

<<imports for typing>>

import random

def kth_largest(arr: List[int], k: int) -> int:
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo

for j in range(lo, hi):
if arr[j] > pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1

arr[i], arr[hi] = arr[hi], arr[i]
return i

def quickselect(arr: List[int],lo, hi, k) -> int:
rand_pivot_idx = random.randrange(lo, hi+1)
arr[hi], arr[rand_pivot_idx] = arr[rand_pivot_idx], arr[hi]
par = partition(arr, lo, hi)

if par == k - 1:
return arr[par]
elif par > k-1:
return quickselect(arr, lo, par-1, k)
return quickselect(arr, par+1, hi, k)

return quickselect(arr, 0, len(arr)-1, k)

print(kth_largest([3,2,1,5,6,4], 3))

4

2.18.2.3.1. Complexity
1. Time complexity:

$$O(n\lg n)$$.

2. Space complexity:

$$O(1)$$. Quicksort is in-place.

2.18.2.4. Leetcode solution

Not available.

<<imports for typing>>



2.19.DONE 973 K closest points to origin   heap medium

2.19.1. Description

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

Constraints:

1. The distance between two points is the Euclidean distance
2. The answer is unique, but its elements can be in any order.
3. $$1\le K \le points.length \le 10000$$
4. $$-10000 5. \(-10000 2.19.1.1. Examples: Input: points = [[1,3], [-2,2]], k=1 Output: [[-2,2]]  2.19.2. Solution 2.19.2.1. Understanding the problem 2.19.2.2. Algorithm We can treat this input of points as a stream and use a priority queue to store each point as we iterate through points. Once we process all points, we just return the last k elements. 2.19.2.3. Code <<imports for typing>> import heapq def k_closest_points(points: List[List[int]], K: int) -> List[List[int]]: def get_distance(x, y) -> float: return (x**2+y**2) if len(points) == K: return points pq = [] # this takes O(n) # because it is essentially heapify() for point in points: distance = get_distance(*point) heapq.heappush(pq, (distance, point)) return [heapq.heappop(pq)[1] for i in range(K)] print(k_closest_points([[1,3],[2,-2]], 2)) print(k_closest_points([[1,3],[2,-2], [2,-3]], 2)) print(k_closest_points([[3,3],[5,-1], [-2,4], [3,4]], 3))  [[1, 3], [2, -2]] [[2, -2], [1, 3]] [[3, 3], [-2, 4], [3, 4]]  2.19.2.3.1. Complexity 1. Time complexity: \(O(K\lg n)$$, the last line takes the most time asymptotically.

2. Space complexity:

$$O(n)$$

2.19.2.4. Leetcode solution

Uses Quickselect.

<<imports for typing>>
class Solution(object):
def kClosest(self, points, K):
dist = lambda i: points[i][0]**2 + points[i][1]**2

def sort(i, j, K):
# Partially sorts A[i:j+1] so the first K elements are
# the smallest K elements.
if i >= j: return

# Put random element as A[i] - this is the pivot
k = random.randint(i, j)
points[i], points[k] = points[k], points[i]

mid = partition(i, j)
if K < mid - i + 1:
sort(i, mid - 1, K)
elif K > mid - i + 1:
sort(mid + 1, j, K - (mid - i + 1))

def partition(i, j):
# Partition by pivot A[i], returning an index mid
# such that A[i] <= A[mid] <= A[j] for i < mid < j.
oi = i
pivot = dist(i)
i += 1

while True:
while i < j and dist(i) < pivot:
i += 1
while i <= j and dist(j) >= pivot:
j -= 1
if i >= j: break
points[i], points[j] = points[j], points[i]

points[oi], points[j] = points[j], points[oi]
return j

sort(0, len(points) - 1, K)
return points[:K]


2.19.2.4.1. Time complexity:

$$O(n^2)$$ worst case, average case $$O(n)$$.

2.19.2.4.2. Space complexity:

$$O(n)$$.

2.19.3. More analysis

2.19.3.2. Related problems

Any problem that asks for "Closest", "Smallest", "Largest", K elements.

2.20.DONE 347 Top K frequent elements   heap medium

2.20.1. Description

Given a non-empty array of integers, return the $$k$$ most frequent elements.

Constraints:

1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
2. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
3. It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
4. You can return the answer in any order.
2.20.1.1. Examples:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]


2.20.2. Solution

2.20.2.2. Algorithm

It's obvious that we have to use quickselect to achieve $$O(n)$$ time complexity on average.

We first scan the array and build a cound of elements ($$O(n)$$). We then quick-select the counts and get the $$k$$ elements ($$O(n)$$).

2.20.2.3. Code
<<imports for typing>>

def top_k_frequent(nums: List[int], k: int) -> List[int]:
def partition(arr, low, high):
pivot = arr[high]
i = low
for j in range(low, high):
if arr[j][1] >= pivot[1]:
arr[j], arr[i] = arr[i], arr[j]
i += 1

arr[i], arr[high] = arr[high], arr[i]
return i

def quickselect(arr, low, high, k: int) -> List[int]:

par = partition(arr, low, high)

if par == k-1:
return arr[:k]
elif par < k-1:
return quickselect(arr, par+1, high, k)
else:
return quickselect(arr, low, par-1, k)

temp = {}
for i in nums:
temp[i] = temp.get(i, 0) + 1
arr = [(k, v) for k, v in temp.items()]
return [i[0] for i in quickselect(arr, 0, len(arr)-1, k)]

print(top_k_frequent([1,1,1,2,2,3], 2))
print(top_k_frequent([1,1,1,2,2,3,3,3], 2))

[1, 2]
[1, 3]

2.20.2.3.1. Complexity
1. Time complexity:

$$O(n)$$ on average, $$O(n^2)$$ worst case.

2. Space complexity:

$$O(n)$$.

2.20.2.4. Leetcode solution
<<imports for typing>>

def top_k_frequent(nums, k):
from collections import Counter
import heapq

count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)

print(top_k_frequent([1,1,1,2,3,2], 2))

[1, 2]

2.20.2.4.1. Time complexity:

$$O(n \lg k)$$

2.20.2.4.2. Space complexity:

$$O(n)$$

2.20.3. More analysis

2.20.3.1. General thoughts

My solution uses Quickselect without randomization, which means that some particular array setup could hit it hard and run at $$O(n^2)$$, but in general, it works at $$O(n)$$.

Another quick hack to this is to use Counter object. When $$kheapq.nlargest() internally, which gives us \(O(n\lg k)$$ time complexity. When $$k==n$$, this uses sorted internally, which also gives us $$O(n\lg k)$$ time complexity.

from collections import Counter

def top_k_frequent(nums, k):
count = Counter(nums)
return [i[0] for i in count.most_common(k)]
print(top_k_frequent([1,2,1,1,24,2], 2))

[1, 2]


Seems we can also use bucket sort.

2.21.DONE 355 Design twitter   medium heap

2.21.1. Description

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

1. postTweet(userId, tweetId): compose a new tweet.
2. geNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Constraints: None.

2.21.1.1. Examples:
Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).

// User 1's news feed should return a list with 1 tweet id -> [5].

// User 1 follows user 2.

// User 2 posts a new tweet (id = 6).

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.

// User 1 unfollows user 2.

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.


2.21.2. Solution

2.21.2.2. Algorithm

We would have a set of users that stores all the users. They have tweets ordrerd by time.

We also have a newsfeed for every user. This newsfeed is a priority queue built on timestamp and selects feeds from followees of current user.

We have followers and followees for any user.

We then map the userId to tade newsfeed.

We update users in postTweet for user A. We update newsfeed in follow of user A. We update newsfeed in unfollow of user A. We update newsfeed in postTweet of user A's followees.

newsfeed has to maintain a length of 10 unless total number of tweets from followees is less than 10.

2.21.2.3. Code
<<imports for typing>>

import collections
from datetime import datetime
import heapq

def __init__(self):
"""
"""
self.users_tweets = collections.defaultdict(list)
self.users_followers = collections.defaultdict(set)
self.users_followees = collections.defaultdict(set)
self.users_newsfeeds = collections.defaultdict(list)

def postTweet(self, userId: int, tweetId: int) -> None:
"""
Compose a new tweet.
"""
# if this userId is new
# add tweet to the userId
tweet = datetime.now(tz=None), tweetId
self.users_tweets[userId].append(tweet)
# update newsfeeds of the followers
for user in self.users_followers[userId]:
heapq.heappush(self.users_newsfeeds[user], tweet)

def getNewsFeed(self, userId: int) -> List[int]:
"""
Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
"""

num_total_tweets = len(self.users_newsfeeds[userId])
num_tweets = 10 if num_total_tweets > 10 else num_total_tweets

res = heapq.nlargest(num_tweets, self.users_newsfeeds[userId])

return [i[1] for i in res]

def follow(self, followerId: int, followeeId: int) -> None:
"""
Follower follows a followee. If the operation is invalid, it should be a no-op.
"""
# Only follow if followee is not followed by us
if followeeId not in self.users_followees[followerId]:

# get the tweets from new followee
for tweet in self.users_tweets[followeeId]:
heapq.heappush(self.users_newsfeeds[followerId], tweet)

def unfollow(self, followerId: int, followeeId: int) -> None:
"""
Follower unfollows a followee. If the operation is invalid, it should be a no-op.
"""
if followeeId == followerId:
return
# Only unfollow if followee is followed by us
if followeeId in self.users_followees[followerId]:

# remove followee (unfollow)
self.users_followees[followerId].remove(followeeId)
# remove follower (unfollow)
self.users_followers[followeeId].remove(followerId)
# remove tweets from folowee
for tweet in self.users_tweets[followeeId]:
self.users_newsfeeds[followerId].remove(tweet)

heapq.heapify(self.users_newsfeeds[followerId])

obj.postTweet(1, 5)
param_2 = obj.getNewsFeed(1)
print(param_2)
obj.follow(1, 2)
param_2 = obj.getNewsFeed(1)
print(param_2)
obj.postTweet(2, 6)
param_2 = obj.getNewsFeed(1)
print(param_2)
obj.unfollow(1, 2)
param_2 = obj.getNewsFeed(1)
print(param_2)


[5]
[5]
[6, 5]
[5]

2.21.2.3.1. Complexity
1. Time complexity:
1. postTweet takes $$O(k)$$, where $$k$$ is the number of followers $$userId$$ has.
2. getNewsFeed takes $$O(n \lg n)$$ with heapq.nlargest, where $$n$$ is the number of tweets in the user's news feed.
3. follow takes $$O(n \lg k)$$, where $$n$$ is the number of tweets the followee has and $$k$$ is the number of tweets in user's news feed. (this part can be improved significantly).
4. unfollow takes $$O(n+m)$$, where $$n$$ is the number of tweets the followee has, $$m$$ is the number of tweets in user's news feed.
2. Space complexity:
1. users_tweets: $$O(m\times n)$$, where $$m$$ is the number of users, and $$n$$ is the number of tweets of each user.
2. users_followers: $$O(m\times n)$$, where $$m$$ is the number of users, and $$n$$ is the number of users who choose to follow a user.
3. users_followees: $$O(m\times n)$$, where $$m$$ is the number of users, and $$n$$ is the number of users who choose to follow a user. (this is not necessary)
4. users_newsfeeds: $$O(m\times n)$$, where $$m$$ is the number of users and $$n$$ is the number of tweets in their news feed. (We can also just keep 10 news feeds).
2.21.2.4. Leetcode solution

Not available.

<<imports for typing>>



2.21.3. More analysis

2.21.3.1. General thoughts

Design, design, design!

From this question, we need to again emphasise the importance of thinking ahead and design our program before we write any code. Jumping into writing code after reading the description can be attracting because that gives us a false feeling of us doing something and make our hands dirty, but when we are doing Leetcode or serious programming, it is paramount that we do more paperwork, more design.

The most important thing here is to actually define the question, as medium/hard questions, or easy questions, can contain a lot of information, and we need to process that information and make sure that we understand it by clearly defining it in our own words. The same not only applies to real world programming as well, but it takes an even more significance in the real world since problems are more vague and complex out there.

If we do not think ahead and design well, it is likely that we will write some code, and it will pass some tests and fail some. Then we go back to the code trying to find out what happened, then run it again, then it maybe fail another test, then we fix it again. Essentially we will become a bug ourselves that tries to hit the lightbulb blindly over and over again. We reduce ourselves to a patch that can only fix one case and that may cause another part of the program to fail. Best case, our program becomes a heavy if else monster that does not have clear logic but still runs fine. Worst case, we give up and do not even have the courage to check the solution and try to fix our program, because this is human nature - we do not want to humiliate ourselves, even if the only one that knows we failed is ourselves.

2.22.DONE 778 Swim in rising water   heap hard

2.22.1. Description

On an $$N\times N$$ grid, each square grid[i][j] represents the elevation at that point (i, j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Constraints:

1. 2 <= N <= 50.
2. grid[i][j] is a permutation of [0, …, N*N - 1].
2.22.1.1. Examples:
Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

We need to wait until time 16 so that (0, 0) and (4, 4) are connected.


2.22.2. Solution

2.22.2.2. Algorithm

We have a loop that controls the time t, which is also the depth of rain. Then in each iteration, we swim from the last_pos we are at, swim(last_pos). last_pos=(0,0) when we are at time 0. In the swim() function, we choose the direction that is equal or less than t, but that we did not swim before in visited_pos. Each swim() gives a new last_pos, we check if it is (N-1, N-1), if so, we just return t.

2.22.2.3. Code
<<imports for typing>>

def swim_in_water(grid: List[List[int]]) -> int:
n = len(grid)
visited_pos : Set[Tuple[int]] = set()

# row, col
last_pos = (0, 0)
def avail_poses(last_pos: Tuple[int]) -> List[Tuple[int]]:
res = []
for row_offset in [-1, 0, 1]:
for col_offset in [-1, 0, 1]:
row = last_pos[0] + row_offset
col = last_pos[1] + col_offset
if 0 <= row < n and 0 <= col < n and (row, col) not in visited_pos and grid[row][col] <= t:
res.append((row, col))

return res

def swim(last_pos: Tuple[int]) -> Tuple[int]:
ele = n+1
return_pos = last_pos
for pos in avail_poses(last_pos):
if grid[pos[0]][pos[1]] <= ele:
ele = grid[pos[0]][pos[1]]
return_pos = pos

return return_pos

for t in range(0, n**2):
print(t)
last_pos = swim(last_pos)
print(last_pos)
if last_pos == (n-1, n-1):
return t

#print(swim_in_water([[0,2],[1,3]]))
print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

0
(0, 0)
1
(0, 1)
(0, 1)
2
(0, 2)
(0, 2)
3
(0, 3)
(0, 3)
4
(0, 4)
(0, 4)
5
(1, 4)
(1, 4)
6
(1, 4)
7
(1, 4)
8
(1, 4)
9
(1, 4)
10
(1, 4)
11
(1, 4)
12
(1, 4)
13
(1, 4)
14
(1, 4)
15
(2, 3)
(1, 4)
16
(2, 3)
(2, 4)
(1, 4)
17
(2, 3)
(2, 4)
(1, 4)
18
(2, 3)
(2, 4)
(1, 4)
19
(2, 3)
(2, 4)
(1, 4)
20
(2, 3)
(2, 4)
(1, 4)
21
(1, 3)
(2, 3)
(2, 4)
(1, 4)
22
(1, 3)
(2, 3)
(2, 4)
(1, 4)
23
(1, 3)
(2, 3)
(2, 4)
(1, 4)
24
(1, 3)
(2, 3)
(2, 4)
(1, 4)
None

<<imports for typing>>

def swim_in_water(grid: List[List[int]]) -> int:
n = len(grid)

# row, col
last_pos = (0, 0)
visited_poses = set()
def avail_poses(last_pos: Tuple[int], cur_t: int) -> List[Tuple[int]]:
offsets = (
(-1, 0),
(0, 1),
(1, 0),
(0, -1)
)
res = []

for row_offset, col_offset in offsets:
row = last_pos[0] + row_offset
col = last_pos[1] + col_offset
if 0 <= row < n and 0 <= col < n and (row, col) not in visited_poses and grid[row][col] <= cur_t:
res.append((row, col))

return res

def swim(cur_pos: Tuple[int], cur_t: int) -> int:
if cur_pos == (n-1, n-1):
return cur_t

while len(avail_poses(cur_pos, cur_t)) == 0:
cur_t += 1

print(cur_pos)
print(cur_t)
for pos in avail_poses(cur_pos, cur_t):
return swim(pos, cur_t)

return swim(last_pos, 0)

print(swim_in_water([[0,2],[1,3]]))
#print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

(0, 0)
1
(1, 0)
1
(0, 0)
2
(0, 1)
3
3


Dynamic programming.

<<imports for typing>>

from math import inf

def swim_in_water(grid: List[List[int]]) -> int:
offsets = (
(-1, 0),
(0, 1),
(1, 0),
(0, -1)
)
res = []

for row_offset, col_offset in offsets:
row = pos[0] + row_offset
col = pos[1] + col_offset
if 0 <= row < n and 0 <= col < n:
res.append((row, col))
return res

n = len(grid)
min_times = [[inf for i in range(n)] for j in range(n)]
min_times[0][0] = 0

for row in range(n):
for col in range(n):
if (row, col) != (0, 0):
min_times[row][col] = min(
)

return min_times[n-1][n-1]

#print(swim_in_water([[0,2],[1,3]]))
print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

[[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [36, 33, 30, 27, 16], [37, 37, 34, 31, 20], [38, 39, 40, 41, 34]]


Dijkstra's algorithm.

<<imports for typing>>

from math import inf

def swim_in_water(grid: List[List[int]]) -> int:
offsets = (
(-1, 0),
(0, 1),
(1, 0),
(0, -1)
)
res = []

for row_offset, col_offset in offsets:
row = pos[0] + row_offset
col = pos[1] + col_offset
if 0 <= row < n and 0 <= col < n:
res.append((row, col))
return res

def min_distance(pos, dist):
min_dist = inf
min_index = None
dist = abs(grid[row][col] - grid[pos[0]][pos[1]])
if  (row, col) not in dist and dist < min_dist:
min_dist = dist
min_index = (row, col)

return min_index

n = len(grid)
dist = dict()

# The set of visited vertices
visited = set()
# The set of unvisited vertices
unvisited = set()

# set all other distances to infinity
for row in range(n):
for col in range(n):
dist[(row, col)] = inf

dist = {(0, 0): 0}

while len(unvisited) != 0:

return dist[(n-1, n-1)]

#print(swim_in_water([[0,2],[1,3]]))
print(swim_in_water([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]))

2.22.2.3.1. Complexity
1. Time complexity:
2. Space complexity:
2.22.2.4. Leetcode solution

We use 4.3.

Given a grid like below:

 1 2 5 3 7 6 8 4 0

Starting from grid[0][0], we have two adjacent cells, we add them to the heap because we can naively reach them starting from grid[0][0].

By definition, we want to choose the cell with the minimum elevation in a list of possible choices, so we pop from the heap, and get grid[0][1], 2.

Then we get its adjacent cells, grid[0][2], 5 and grid[1][1], 7. We add these two to the heap.

Now, it is obvious to the naked eye that 3<5<7, so at this moment we have to choose the grid[1][0], 3, path. Again, we simply pop from the heap to do this. After this operation, our heap now has two elements left, grid[0][2], 5, and grid[1][1], 7.

We then again check the adjacent cells of grid[1][0], 3, and add them to the heap. Now in the heap we have four elements, grid[0][2], 5, grid[1][1], 7, grid[1][1], 7, grid[2][0], 8

We continue this loop until we reach grid[n-1][n-1].

Intuitively speaking, all elements in the heap have been discovered by us before, meaning that there is a valid path from the start to it. For example, when we are at grid[0][1], 2, and we find that 5 and 7 are larger than another option 3, then there must be a way from grid[0][0] for us to swim to grid[1][0], 3, in no time. When we are at grid[1][0], 3, and find that 7 and 8 are larger than another option 5, we can swim to grid[0][2], 5, in no time.

The process of finding and getting (swimming to) the smallest option/heading/cell/elevation is done by the priority queue automatically.

<<imports for typing>>

import heapq

def swim_in_water(grid: List[List[int]]) -> int:
visited, heap = set(), [(grid[0][0], 0, 0)]
time, n = 0, len(grid)

# The idea to use heap is that:
# 1. It keeps a list of possible cells to take, and
# 2. The cell with the minimum cost/elevation is stored at the top
# 3. At the start of every iteration, every cell in the heap has been seen before,
#    meaning that there is at least one path from (0, 0) to that cell

# Intuitively, we always want to choose the cell with the minimum elevation.
#
while heap:
cur, x, y = heapq.heappop(heap)
time = max(time, cur)

if x == y == n-1:
return time
for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
if 0<=i<=n-1 and 0<=j<=n-1 and (i, j) not in visited:
heapq.heappush(heap, (grid[i][j], i, j))

print(cur)
print(heap)

return -1
print(swim_in_water([[8,2, 7], [3,4, 6], [1, 5, 0]]))

8
[(2, 0, 1), (3, 1, 0)]
2
[(3, 1, 0), (4, 1, 1), (7, 0, 2)]
3
[(1, 2, 0), (4, 1, 1), (4, 1, 1), (7, 0, 2)]
1
[(4, 1, 1), (4, 1, 1), (7, 0, 2), (5, 2, 1)]
4
[(4, 1, 1), (5, 2, 1), (7, 0, 2), (5, 2, 1), (6, 1, 2)]
4
[(5, 2, 1), (5, 2, 1), (6, 1, 2), (6, 1, 2), (5, 2, 1), (7, 0, 2)]
5
[(0, 2, 2), (5, 2, 1), (5, 2, 1), (6, 1, 2), (7, 0, 2), (6, 1, 2)]
8

2.22.2.4.1. Time complexity:

$$O(n^2\lg n)$$, $$n$$ is the number of rows of the grid. The while loop takes $$O(n^2)$$ time. Inside it, the heapq.heappush takes $$O(\lg n)$$ time.

2.22.2.4.2. Space complexity:

$$O(n)$$, visited and heap.

See 2.22.2.4.

2.23.DONE 1022 Sum of root to leaf binary numbers   tree easy

2.23.1. Description

Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0->1->1->0->1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers.

Constraints:

1. The number of nodes in the tree is between 1 and 1000.
2. node.val is 0 or 1.
3. The answer will not exceed 231 - 1.
2.23.1.1. Examples:
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22


2.23.2. Solution

2.23.2.2. Algorithm

We try to use generators to solve the calculation part of the problem. For traversing the tree, we use pre-order traversal.

2.23.2.3. Code
<<imports for typing>>

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def calculator():
total = 0
bit = None
num = "" # every path uses the same num in the calculator generator, so this is messed up

while True:
bit = yield

if bit is None:
# We must terminate the coroutine normally
# to return a value.
# If we do try...except GeneratorExit, we will not be able to return a value later
break
elif bit == "leaf":
total += int(num, 2)
num = num[:-1]
else:
num = num + str(bit)

def dele_gen():
global results
while True:
results = yield from calculator()

results = 0
calc = dele_gen()
next(calc)
def traverse(node, calc):
if node:
calc.send(node.val)
if node.left is None or node.right is None:
calc.send("leaf")
else:
traverse(node.left, calc)
traverse(node.right, calc)
else:
calc.send("")

l_1 = TreeNode(0)
r_0 = TreeNode(1)
l = TreeNode(0, l_1, r_0)
r = TreeNode(1)
root = TreeNode(1, l, r)
traverse(root, calc)
calc.send(None)
print(results)

11

2.23.2.3.1. Complexity
1. Time complexity:
2. Space complexity:
2.23.2.4. Leetcode solution

Not available.

<<imports for typing>>

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def sum_root_to_leaf(root) -> int:
if not root:
return 0

res = []

def helper(node, path):
if node.left is None and node.right is None:
res.append(path + str(node.val))
return

if node.left:
helper(node.left, path + str(node.val))

if node.right:
helper(node.right, path+str(node.val))

helper(root, "0b")
return sum([int(p, 2) for p in res])
l_1 = TreeNode(0)
r_0 = TreeNode(1)
l = TreeNode(0, l_1, r_0)
r = TreeNode(1)
root = TreeNode(1, l, r)
print(sum_root_to_leaf(root))

12

2.23.2.4.1. Time complexity:

$$O(n)$$, where n is the number of nodes, as this algorithm visits all nodes in the tree.

2.23.2.4.2. Space complexity:

Assuming full binary tree, $$O(n\log(n))$$, we need to have $$O(n)$$ paths (number of leaves of the tree), each having the length of $$\log(n)$$ (height of the tree).

2.23.3. More analysis

2.23.3.1. General thoughts

A key problem in my solution is that I have no way of creating path copies easily.

Initially I thought that it was a good idea to use a generator responsible for calculating the total as this is somewhat similar to calculating a running average problem. Then the problem came when the variable num could only hold one path and the generator had no easy way to keep track of the paths that corresponds to nodes. Therefore, when it added the num for the left most leaf to the total, it could not determine which path to take next.

The only way to do it is to backtrack num by removing the bits that correspond to the leaf that has been visited and its parent, grandparent, great-grandparent… that has no other children. This causes a lot of trouble as every node references this single variable num, and there are many states to check.

The code from Leetcode discussion solves this problem by copying the current path at each node, though this is done implicitly, as strings are copied implicitly. Therefore, every node has their own copy the the current path, and they can safely modify the path (path+str(node.val)) without affecting other nodes.

2.24.DONE 1207 Unique number of occurrences   hash_table easy

2.24.1. Description

Given an array of integers arr, write a function that returns true iff the number of occurrences of each value in the array is unique.

Constraints:

1. 1 <= arr.length <= 1000
2. -1000 <= arr[i] <= 1000
2.24.1.1. Examples:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Input: arr = [1,2]
Output: false

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true


2.24.2. Solution

2.24.2.1. Understanding the problem

The problem:

1. gives an array of integers that
2. could be negative, 0, or positive.
3. wants us to count the number of occurrences (occur) of each value, and
4. return true if occur of each integer is different.
2.24.2.2. Algorithm

We scan the integer array, and add one to the counter (occur) map of each value we met. We then scan the counter map to see if there is more than one unique numbers.

2.24.2.3. Code
<<imports for typing>>

def unique_occurrences(arr: List[int]) -> bool:
occurs = {}
for i in arr:
occurs[i] = occurs.get(i, 0) + 1

uniques = set(occurs.values())
return len(uniques) == len(occurs.values())

arr = [1,2,2,1,1,3]
arr = [2,2,1,1,3]
print(unique_occurrences(arr))

False

2.24.2.3.1. Complexity
1. Time complexity:

$$O(n)$$, where $$n$$ is the number of elements in the array.

2. Space complexity:

$$O(n)$$.

2.24.2.4. Leetcode solution

Not available.

<<imports for typing>>



2.24.3. More analysis

2.24.3.1. General thoughts

This is an easy question. The hard part of this question is actually understanding the description clearly and quickly. This is why I suddenly decided to add a Understanding the problem heading.

It's actually amazing that after so many questions and problems that I have solved, I put this heading in so late. Yes the importance of understanding the question, or figuring out the definition of the terms used in the question, has been known to me for quite some time, but somehow I just did not give credits where it's due. It's almost like I'm unconsciously supressing the known idea that understanding the problem clearly and quickly is crucial to solving the problem.

I want to take this opportunity to write it down explicitly that the first thing we need to do in any coding (or anything really) is to come to terms with the author (How to read a book). We must first understand what the words mean before we understand what the author of the problem is saying by giving us those words. Again, this is an extremly simple and important but often ignored rule.

2.25.TODO 706 Design HashMap   hash_table easy

2.25.1. Description

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

• put(key, value): insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
• get(key): returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• remove(key): remove the mapping for the value key if this map contains the mapping for the key.

Constraints:

1. All keys and values will be in the range of [0, 1000000].
2. The number of operations will be in the range of [1, 10000].
3. Please do not use the built-in HashMap library.
2.25.1.1. Examples:
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1);            // returns 1
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1
hashMap.remove(2);          // remove the mapping for 2


2.25.2. Solution

2.25.2.1. Understanding the problem

The remove() method, though not mentioned, should be idempotent.

The code template also gives more information on requirements. The key is an integer and value will always be non-negative.

Because the number of operations will be in the range less than 10000, this can be used as the length of our array backing up the map, assuming that all the operations were put().

2.25.2.2. Algorithm

We need to find a proper hash function.

For the hash function, we simply divide the key by 100. We can use doubly linked list for handling collision.

2.25.2.3. Code
<<imports for typing>>
class MyHashMap:
class Node:

def __init__(self, val: int, key: int, parent: 'Node'=None, child: 'Node'=None):
self._val = val
self._key = key
self._parent = parent
self._child = child

@property
def val(self):
return self._val
@val.setter
def val(self, val):
self._val = val

@property
def key(self):
return self._key

@key.setter
def key(self, key):
self._key = key

@property
def child(self):
return self._child

@child.setter
def child(self, child: 'Node'):
self._child = child

@property
def parent(self):
return self._parent

@parent.setter
def parent(self, parent: 'Node'):
self._parent = parent

@staticmethod
def gen_nodes(root: 'Node'):
node = root
while node:
yield node
node = node.child

def __init__(self):
"""
"""
self.arr = [self.Node(-1, -1) for i in range(10000)]

def _get_nodes(self, key: int):

hash_value = self._hash_func(key)
return self.gen_nodes(self.arr[hash_value])

def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""

nodes = self._get_nodes(key)
for node in nodes:
if node.key == key:
node.val = value
break
else:
node.child = self.Node(value, key, node)

def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
"""
nodes = self._get_nodes(key)
for node in nodes:
if node.key == key:
return node.val

return -1

def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""

nodes = self._get_nodes(key)
for node in nodes:
if node.key == key:
if node.child:
node.child.parent = node.parent

node.parent.child = node.child

@staticmethod
def _hash_func(key: int) -> int:
"""
Hashes key
"""
return key // 100

obj = MyHashMap()
obj.put(100, 123)
print(obj.get(100))
obj.put(101, 124)
obj.put(101, 1024)
print(obj.get(101))
obj.put(102, 125)
print(obj.get(102))
obj.remove(102)
print(obj.get(102))
print(obj.get(101))
print(obj.get(103))

123
1024
125
-1
1024
-1

2.25.2.3.1. Complexity
1. Time complexity:

$$O(1)$$ average.

2. Space complexity:

$$O(1)$$ given at maximum 10000 operations.

2.25.2.4. Leetcode solution

Not available.

<<imports for typing>>



2.25.3. More analysis

2.25.3.1. General thoughts

Coming up with the solution algorithm conceptually is not hard as this is well-documented in CLRS.

The hard part comes at the actual coding. Basically, I encountered the following issues:

1. Properly use reference to inner class
2. Properly reference the class itself when setting types for arguments
3. Properly use @property decorator and property.setter as I did not use them often.

Besides those issues, I was also sceptical if the following code would work. That is to say, if I still have reference to the last node when I break out of the loop.

The answer is yes, since node is shadowed in the for loop. Therefore, if we break out of the loop or the loop finishes, node still points to the last object it got in the loop.

node = None
for node in nodes:
if node.key == key:
node.val = value
break

# this is a slight modification of my solution
node.child = self.Node(value, key, node)


2.26.TODO 208 Implementing Trie

2.26.1. Description

Implement a Trie with insert, search and startwith.

Constraints:

1. You may assume that all inputs are consist of lowercase letters a-z.
2. All inputs are guaranteed to be non-empty strings.
2.26.1.1. Examples:
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true


2.26.2. Solution

2.26.2.1. Understanding the problem

A Trie is based on a tree structure. insert(word) inserts a word into the trie. search(word) tries to find a word in the trie, and returns True if it can find the word, else return False. startswith(prefix) tries to find prefix in the trie, and returns True if it can find the prefix, else return False.

The difference between search() and startswith() is that the last character of the word for search() must be the last character in the trie as well, i.e. its is_end property must be True.

2.26.2.2. Algorithm

We use standard Trie structure with a TrieNode and a Trie.

2.26.2.3. Code
<<imports for typing>>

class Trie:
class TrieNode:

def __init__(self, is_end=False, num_children=26):
self.is_end = is_end
self.num_children = num_children
self.links = [None for i in range(self.num_children)]

@property
def is_end(self):
return self._is_end

@is_end.setter
def is_end(self, val):
self._is_end = val

def contains_key(self, ch: str) -> bool:

def get(self, ch: str) -> 'TrieNode':

def put(self, ch: str, node: 'TrieNode') -> None:

def __init__(self):
"""
"""
self.root = self.TrieNode()

def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for ch in word:
if not node.contains_key(ch):
node.put(ch, self.TrieNode())

node = node.get(ch)

# set the last node.is_end to True
node.is_end = True

def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.search_prefix(word)
return (node is not None) and node.is_end

def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.search_prefix(prefix)
return node is not None

def search_prefix(self, prefix: str) -> TrieNode:
node = self.root
for ch in prefix:
if node.contains_key(ch):
node = node.get(ch)
else:
return None

return node

# Your Trie object will be instantiated and called as such:
obj = Trie()
word="apple"
obj.insert(word)
param_2 = obj.search(word)
print(param_2)
word="app"
obj.insert(word)
param_2 = obj.search(word)
print(param_2)
prefix="apt"
param_3 = obj.startsWith(prefix)
print(param_3)
param_2 = obj.search("aa")
print(param_2)

True
True
False
False

2.26.2.3.1. Complexity
1. Time complexity:
2. Space complexity:
2.26.2.4. Leetcode solution
<<imports for typing>>



2.26.3. More analysis

2.26.3.1. General thoughts

A Trie is built with two parts: a TrieNode and a Trie.

The most important thing to check for when building a TrieNode is the number of children it should have when children is an array of fixed length. In cases when we are not certain of the length, we can use HashMap.

The TrieNode should have at least three methods and one property to be functional: put, get, contains_key, and is_end as a property.

The three methods are meant to operate on TrieNode.children, which are basically modifications of array's get, append, in methods. They also have the same time complexity of $$O(1)$$.

The is_end property marks whether the current node is the end of a word.

When we have a TrieNode, we then build a Trie upon it. The most important thing with Trie is the subtle difference between a prefix and a word. A word is also a prefix, but a prefix does not necessarily equal to a word. A prefix is also a word iff prefix.last_node.is_end==True. This tells us that, we can use the method search_prefix(prefix) to find the prefix, and also use it to find if a word is in the Trie, since we only need to check if the last node is also an end.

The Trie also have at least three methods to be functional: insert, search_prefix and search_word. Typically a startswith method will be added, and this is as trivial as search_word.

2.27.TODO 1038 Binary Search Tree to Greater Sum Tree

2.27.1. Description

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

Constraints:

1. The number of nodes in the tree is between 1 and 100.
2. Each node will have value between 0 and 100.
3. The given tree is a binary search tree.
2.27.1.1. Examples:



2.27.2. Solution

2.27.2.1. Understanding the problem

The question is bit hard to understand at first but it is asking us to do the following.

1. We have a BST.
2. Start from the right-most leaf, we replace every node with,

the sum of, all values that are greater than the node, i.e, all values that are to the right of the node.

2.27.2.2. Algorithm

Like what is said in Understanding the problem, we start from the right-most leaf. In this case, we use DFS and In-order traversal. Every node's value is made of its original value plus the value of the node processed before it.

2.27.2.3. Code
<<imports for typing>>

# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
def helper(node) -> None:
nonlocal running_sum
if node.right:
helper(node.right)

node.val += running_sum
running_sum = node.val

if node.left:
helper(node.left)

running_sum = 0
helper(root)
return root


2.27.2.3.1. Complexity
1. Time complexity:

$$O(n)$$, where $$n$$ is the number of nodes in the BST.

2. Space complexity:

$$O(n)$$, the space needed for the recursive stack.

2.27.2.4. Leetcode solution
<<imports for typing>>



2.28.TODO 21 Merge Two Sorted Lists

2.28.1. Description

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Constraints:

2.28.1.1. Examples:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4


2.28.2. Solution

2.28.2.1. Understanding the problem

The problem gives two sorted linked lists a and b, and asks us to merge these two together to form a new sorted linked list c that is:

1. in the same order as a and b, though this is not mentioned.
2. either descending or ascending.
3. ignorant of the order of elements from a and b when they are equal.

The lists could be empty or only have one node. The lists could have different order.

2.28.2.2. Algorithm

We assume that a and b are both descending or ascending. We need to know whether a and b are descending or ascending. Actually, we can't know that ahead of time as the whole list could have a list of equal values.

Once we know that, we pop each of the node of the lists and always use the smallest/largest node. We simply pop nodes from each list and compare the new nodes with the one we have to form the next node of the new list.

Or maybe we just quick sort them, considering a and b can have different orders???

2.28.2.3. Code
<<imports for typing>>

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
def gen_node(lst: ListNode):
yield lst
node = lst
while node.next:
node = node.next
yield node

if l1 == None:
return l2

if l2 == None:
return l1

gen_l1 = gen_node(l1)
gen_l2 = gen_node(l2)

res = []

for node in gen_l1:
res.append(node)

for node in gen_l2:
res.append(node)

res = sorted(res, key=lambda node: node.val)
for i, node in enumerate(res):
if i == len(res) - 1:
break
node.next = res[i+1]

res[-1].next = None

return res[0]

l1_1 = ListNode(4)
l1_2 = ListNode(2, l1_1)
l1_3 = ListNode(1, l1_2)
l2_1 = ListNode(4)
l2_2 = ListNode(3, l2_1)
l2_3 = ListNode(1, l2_2)

print(mergeTwoLists(l1_3, l2_3).next.next.next.val)

3

2.28.2.3.1. Complexity
1. Time complexity:
2. Space complexity:
2.28.2.4. Leetcode solution
<<imports for typing>>



2.29.TODO 20 Valid Parentheses

2.29.1. Description

Constraints:

2.29.1.1. Examples:



2.29.2. Solution

2.29.2.3. Code
<<imports for typing>>



2.29.2.3.1. Complexity
1. Time complexity:
2. Space complexity:
2.29.2.4. Leetcode solution
<<imports for typing>>



3. Data structures

This section contains widely used data structures and related problems.

4. Algorithms

This section contains widely used algorithms and related problems.

4.1. Sorting

4.1.1. Insertion sort

In-place sort. Easy to implement.

def insertion_sort(arr):
i = 0
while i < len(arr):
j = i
while j > 0 and arr[j-1] > arr[j]:
temp = arr[j-1]
arr[j-1] = arr[j]
arr[j] = temp
j -= 1

i+=1

return arr
print(insertion_sort([2,1,3,4,2,5]))

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


4.2. Dynamic programming

The prerequisites for using DP are:

1. optimal substructure
2. overlaping sub-problems

4.2.1. Edit distance

def edit(s: str, t: str) -> int:
from math import inf
def get_element(tbl: List[List[int]], i: int, j: int) -> int:

if i>=0 and j>=0:
return tbl[i][j]
else:
return inf

m = len(s)
n = len(t)

tbl = [[0 for j in range(n+1)] for i in range(m+1)]

for i in range(0, m+1):
for j in range(0, n+1):
if i==0 and j==0:
continue
tbl[i][j] = min(1+get_element(tbl,i, j-1), 1+get_element(tbl,i-1, j), get_element(tbl, i-1, j-1)+(0 if s[i-1]==t[j-1] else 1))
return tbl[m][n]
print(edit("cbc", "ac"))

2

def edit(s: str, t: str) -> int:
m = len(s)
n = len(t)

# +1 accounts for the empty string in the table
tbl = [[0 for j in range(n+1)] for i in range(m+1)]

for i in range(m+1):
for j in range(n+1):
if i == 0:
tbl[i][j] = j
elif j==0:
tbl[i][j] = i

# we want to compare the chars s[i-1] and t[j-1]
# not the chars s[i] and t[j]
# because at this point, i is in [1..m], j is in [1..n]
# we need to map them back to [0..m-1] and [0..n-1]
elif s[i-1]==t[j-1]:
tbl[i][j] = tbl[i-1][j-1]
else:
tbl[i][j] = 1+min(tbl[i][j-1], # insert
tbl[i-1][j], # remove
tbl[i-1][j-1] # replace
)
return tbl[m][n]

print(edit("abc", "ac"))

1


See 6.5.

4.4. Binary search

Simple recursive solution.

def binary_search(arr, left, right, target):

# check base case
if left <= right:
mid = left + (right - left) // 2

if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, left, mid - 1, target)
else:
return binary_search(arr, mid + 1, right, target)

return -1


5. Techniques

This section contains techniques that do not make a full algorithm and related problems.

5.1. General

See 2.10.2.5.

We have set of objects that we want to draw from. How do we represent the set's subsets such that we get its power set?

We can easily think of a map to associate with each object a boolean value, indicating whether the object is picked. The problem with this is that it can take a lot of memory and can be slow due to the overhead of creating the map.

 arr 1 2 3 mask 1 0 1
def get_power_set(arr: List[int]) -> List[List[int]]:
n = len(arr)

# helps create left padding zeros
# if n == 4, we have 1000
nth_bit = 1<<n

res = [[]]
# time complexity: 2**n
for i in range(2**n):
# if n==4, we might have 1000 | 010
# 1000 | 110, etc
# [3:] takes out the leading "0b1" in "0b1010"
sub = []
# time complexity: n
for j in range(n):
sub.append(arr[j])

res.append(sub)
return res
print(get_power_set([1,2,3]))

[[], [], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]


5.2. Python

k in dict.keys() is $$O(1)$$ because keys views are set-like since their are unique and hashable.

6. CLRS Notes & Yufei Tao lecture notes

Read chapters 3-4, 6-7, 10-17 and 22 of CLRS, and practice on LeetCode. Also check Yufei Tao's lecture notes for concise introductions.

6.1. Growth of functions

We want to compare which algorithm performs better with respect to input size. We study the asymptotic efficiency of algorithms when we make the input size large enough that only the order of growth of the running time is relevant.

6.1.1. Asymptotic notation

Notations:

1. Domain for all functions of interest: $$\mathbb{N}$$.
2. Worst-case running-time function $$T(n)$$.
6.1.1.1. List of notations from YFT lecture notes:
6.1.1.1.1. Big-$$O$$ (upper bound)

Let $$f(n)$$ and $$g(n)$$ be two functions of $$n$$.

We say that $$f(n)$$ grows asymptotically no faster than $$g(n)$$ if there is a constant $$c_1>0$$ and a constant $$c_2$$ such that $$f(n)\le c_1 g(n)$$ holds for all $$n \ge c_2$$. We denote this by $$f(n)=O(g(n))$$.

The time complexity of an algorithm is described in the asymptotical form (big-O).

6.1.1.1.2. Big-$$\Omega$$ (lower bound)

Let $$f(n)$$ and $$g(n)$$ be two functions of $$n$$. If $$g(n)=O(f(n))$$, then we define: $$f(n)=\Omega(g(n))$$, to indicate that $$f(n)$$ grows asymptotically no slower than $$g(n)$$.

6.1.1.1.3. Big-$$\Theta$$

Let $$f(n)$$ and $$g(n)$$ be two functions of $$n$$. If $$f(n)=O(g(n)) \text{ and } f(n)=\Omega(g(n))$$, in other words, $$f(n)=O(g(n)) \text{ and } g(n)=O(f(n))$$, then we define: $$f(n)=\Theta(g(n))$$. This indicates that $$f(n)$$ grows asymptotically as fast as $$g(n)$$, no faster (big-$$O$$), no faster (big-$$\Omega$$).

6.2. Divide and conquer

We solve the problem recursively, applying the following 3 steps at each level of the recursion:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem (recursive case).
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner (base case).
3. Combine the solutions to the subproblems into the solution for the original problem.

6.2.1. Recurrences

A recurrence is an equation of inequality that describes a function in terms of its value on smaller inputs.

The books provides 3 methods for obtaining the asymptotic $$\Theta$$ or $$O$$ bounds on the recurrence solution:

1. Substitution method - we guess a bound and then use mathematical induction to prove our guess correct.
2. Recursion-tree method - convert the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.
3. Master method - provides bounds for recurrences of the form $$T(n)=\underbrace{aT(n/b)}_{a \text{ subproblems}}+f(n),a\ge 1, b>1$$ and $$f(n)$$ is a given function.

To use the 3, 3 cases need to be memorized.

6.3. Sorting

The sorting problem:

• Input: A sequence of $$n$$ numbers $$\langle a_1, a_2,\ldots,a_n\rangle$$.
• Output: A permutation $$\langle a_1',a_2',\ldots,a_n'\rangle$$ of the input sequence such that $$a_1'\le a_2'\le \ldots \le a_n'$$.

Two kinds of sorting based on time complexity:

• Comparison sort: sorted order is based only on comparison between the input elements
• Non-comparison sort: use operations other than comparisons to determine the sorted order
Table 1: Sorting time complexity
Algorithm Worst-case runing time Average-case/expected running time Comparison?
Insertion sort $$\Theta(n^2)$$ $$\Theta(n^2)$$ yes
Merge $$\Theta(n\lg n)$$ $$\Theta(n\lg n)$$ yes
Heap $$O(n\lg n)$$ - yes
Quick $$\Theta(n^2)$$ $$\Theta(n\lg n)$$ (expected) yes
Counting $$\Theta(k+n)$$ $$\Theta(k+n)$$ no
Radix $$\Theta(d(k+n))$$ $$\Theta(d(k+n))$$ no
Bucket $$\Theta(n^2)$$ $$\Theta(n)$$ (average-case) no

6.3.1. Heapsort   comparison_sort

• Running time: $$O(n\lg n)$$
• In-place: yes

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree (some leaves might be empty). Each node of the tree corresponds to an element of the array.

A heap $$A$$ is an array that has two attributes:

1. $$A.length$$
2. $$A.heap-size$$, only $$A[1..A.heap-size]$$ are valid elements to the heap

$$A.heap-size\le A.length$$.

6.3.1.1. Heap properties

For any node $$i$$, we have:

• parent: $$\lfloor i/2\rfloor$$.
• left child: $$2i$$
• right child: $$2i+1$$

There are two kinds of binary heaps: max-heaps and min-heaps. For every node $$i$$, they satisfy a heap property,

• max-heap: $$A[parent(i)]\ge A[i]$$.
• min-heap: $$A[parent(i)]\le A[i]$$.

Max-heaps are used in the heapsort lagorithm; Min-heaps implement 6.7.4.

6.3.1.2. Max-Heapify (maintaining $$A[parent(i)]\ge A[i]$$)

Here is the Python code for the Max-Heapify pseudo-code. Time complexity: $$O(\lg n), n=A.length$$.

The max_heapify lets the value at A[i] "float down" in the max-heap so that the subtree rooted at index i obeys the max-heap property.

/-------\
| arr(i)|
|       |
\-------/
/         \
/           \
/             \
/-------\               /-------\
| max   |               | max   |
| heap  |               | heap  |
\-------/               \-------/

def max_heapify(A, i, heap_size) -> None:

# A is 0-indexed
l = 2*i+1
r = 2*i+2

largest = i
if l < heap_size and A[l]>A[i]:
largest = l
if r < heap_size and A[r]>A[largest]:
largest = r

if largest != i:
A[i], A[largest] = A[largest], A[i]
# after exchanging A[i] and A[largest]
# the subtree now rooted at A[largest] might violate the max-heap property
# thus we need to heapify it
# at the end, the value of the original A[i] will float down
# as many heights as possible
max_heapify(A, largest, heap_size)

# The children of the root node must be already max-heaps
A = [4,14,13,10,1,12]
max_heapify(A, 0, len(A))
print(A)

[14, 10, 13, 4, 1, 12]

6.3.1.3. Building a heap

Here is the Python code for building the Build-Max-Heap pseudo-code from bottom to top (this is faster than "top-bottom" but the details are not important here). This also makes sense because we start from the direct parent of leave nodes, which matches the prerequisite of max-heapify() of having the child nodes of a 3-node construct to be max-heaps. In this case, those child nodes of a 3-node construct are leaves of the binary tree, which are max-heaps with only one element.

As we go up the tree, all nodes that we have passed by are now roots of max-heaps, which again satisfies the condition of max-heapify() when used as child nodes of an upper node.

This is $$O(n)$$. Although the obvious time complexity is $$O(n\lg n)$$, we can prove that a tighter bound exists and it is $$O(n)$$.

This makes sure that all elements $$A[i]$$ in the heap satisfies: $$A[parent(i)]\ge A[i]$$.

Once again, compared to max-heapify(), this algorithm does not need its argument array to have children of the root as max-heaps already, since this algorithm is going to achieve exactly that.

<<max-heapify>>
def build_max_heap(A, heap_size) -> None:

# we simply skip all leaves
# because they are max-heaps with one element
for i in range((len(A)//2-1), -1, -1):
max_heapify(A, i, heap_size)

#A = [4,14,7]
#build_max_heap(A, len(A))
#print(A)

[14, 4, 7]

6.3.1.4. Heapsort algorithm
<<build-max-heap>>

def heapsort(A):

# As the name suggests,
# build a max-heap out of array A.
# We have the largest number at root
# after this
build_max_heap(A, len(A)-1)

# Keep changing root and the last element
# max_heapify() guarantees that
# the largest element pops to the root
for i in range(len(A)-1, 0, -1):
# heap_size is i
A[0], A[i] = A[i], A[0]
max_heapify(A, 0, i)

A=[3,13,2,123,4,1]
heapsort(A)
print(A)

[14, 10, 7, 4, 1, 12]
[1, 2, 3, 4, 13, 123]

6.3.1.5. Issues with heapsort in real world applications

Notes from Princeton COS 226.

Performance on real computers is heavily impacted by really messy factors like cache performance.

Cache works in a way that when we fetch one memory address, its nearby addresses are fetched as well, since memory access patterns of most programs/algorithms are highly localized. Therefore, in a $$n\times n$$ matrix, [arr[i][j] for j in range(n) for i in range(n)] is faster than [arr[j][i] for j in range(n) for i in range(n)], because when we fetched arr[i][0], the computer already cached arr[i][1], etc, for us.

Table 2: Sort algorithms and cache performance
Sorting algo characteristic cache-friendly☺?
mergesort sort subarrays first cache-friendly ☺
quicksort partition into subarrays cache-friendly ☺
heapsort all over the place cache-unfriendly 🤕

6.3.2. Quicksort   comparison_sort

Worst-case: $$\Theta(n^2)$$. Expected-case: $$O(n\lg n)$$. In-place: true.

Three step divide-and-conquer process for a subarray $$A[p..r]$$:

• Divide: Partition $$A[p..r]$$ into two (possibly empty) subarrays $$A[p..q-1]$$ and $$A[q+1..r]$$ such that $$a\le A[q]\le b, a\in A[p..q-1], b\in A[q+1, r]$$. Compute the index $$q$$ as part of this partition prcedure.
• Conquer: Sort the two subarrays $$A[p..q-1]$$ and $$A[q+1..r]$$ by recursive calls to quicksort.
• Combine: Because the subarrays are already sorted, no work is needed to combine them.
6.3.2.1. Implementation

Implementation of the above steps:

<<imports for typing>>
<<partitioning the array>>

def quicksort(arr, low, high):
if low < high:
par_idx = partition(arr, low, high)
quicksort(arr, low, par_idx-1)
quicksort(arr, par_idx+1, high)

A = [2,1,4,5]
quicksort(A, 0, len(A)-1)
print(A)

[1, 2, 4, 5]


Implementation of partitioning the array:

def partition(arr, low, high):
"""
This function takes last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller elements to the left of
the pivot, and all greater elements to the right of the pivot.

This partitions the arr in-place. Thus the for loop seems hard to understand.
"""
pivot = arr[high]
# arr[low:i+1] is the smaller elements segment
# that are <= pivot

# i is the idx of the last smaller element
i = low - 1
# After each the iteration:
# arr[low:i+1] are smaller elements.
# arr[i+1:j] are larger elements.
# arr[j:high] are unchecked elements.
# arr[high] is the pivot
for j in range(low, high):
# if current element is smaller than
# or equal to pivot
# This means we can add another element
# to the smaller elements segment
if arr[j] <= pivot:
# increment index of smaller element
# because we found one smaller element at arr[j]
# and is going to exchange it with arr[i]
i += 1
# if j>i, that means arr[i] > pivot
# we need to exchange that with arr[j].
# otherwise, there is no need to exchange
# arr[j] and arr[i]
# however, this condition can be ignored,
# as it does not slow down the operation
if j>i:
arr[i], arr[j] = arr[j], arr[i]

# exchange the smallest element in the larger segment
# with the pivot
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1

6.3.2.2. Notes on choosing the pivot and running time

We can randomly pick any $$i$$ in $$A$$ to be our pivot. And this random picking process can be done in $$O(1)$$ time.

Because this is a randomized algorithm, its running time is a random variable depending on the random choices made. Thus we can only get its running time as follows:

Table 3: Quicksort running time
Case # of elements in segments after each partitioning Running time
Worst n-1 elements and 0 elements $$O(n^2)$$
Best $$\lfloor n/2 \rfloor$$, $$\lceil n/2 \rceil -1$$ $$O(n\lg n)$$
Average as long as segment not empty (not the worst) $$O(n\lg n)$$

6.3.3. Sorting in linear time

We assume all input elements are distinct, without loss of generality.

6.3.3.1.TODO Decision-tree

Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.

6.4. Medians and order statistics

6.4.1. Definition

The $$i$$ th order statistic of a set of $$n$$ elements is the $$i$$ th smallest element. For example, the minimum of a set of elements is the first order statistic ($$i=1$$), and the maximum is the $$n$$ th order statistic ($$i=n$$). A median, is the middle of the set.

The selection problem:

• Input: A set $$A$$ of $$n$$ (distinct) numbers and an integer $$i$$, with $$1\le i \le n$$.
• Output: The element $$x \in A,a_1< a_2 < \ldots < a_{i-1},x < a_{i+1}\ldots a_n$$.

6.4.2.DONE Selection in expected linear time (Quickselect)

We use randomized_select modeled after the 6.3.2 algorithm but only works on one side of a partition.

Implementation of Quickselect fromLeetcode.

import random

def partition(arr, l, r):
x = arr[r]
i = l

for j in range(l, r):
# use > to sort the elements in descending order
if arr[j] > x:
arr[i], arr[j] = arr[j], arr[i]
i += 1

arr[i], arr[r] = arr[r], arr[i]
return i

def quick_select(nums, start, n, k):
# get random pivot index
rand_pivot_idx = random.randrange(start, n+1)
nums[n], nums[rand_pivot_idx] = nums[rand_pivot_idx], nums[n]
pos = partition(nums, start, n)
if pos == k-1:
return nums[pos]
elif pos >= k:
return quick_select(nums, start, pos-1, k)
return quick_select(nums, pos+1, n, k)

def find_kth_largest(nums, k):
return quick_select(nums, 0, len(nums)-1, k)

print(find_kth_largest([3,2,1,5,6,4], 1))

6


6.4.3.TODO Selection in worst-case linear time (median-of-medians)

Steps to select:

1. Divide the $$n$$ elements of the input array into $$\lfloor n/5 \rfloor$$ groups and at most one group made up of the remaining $$n \mod 5$$ elements.
2. Find the median of each of the $$\lceil n/5 \rceil$$ groups by first insertion-sorting the elements of each group.
3. Use select() recursively to find the median $$x$$ of the $$\lceil n/5 \rceil$$ medians found in step 2.
4. Partition the input array around the median-of-medians $$x$$ using the modified version of partition. Let $$k$$ be one more than the number of elements on the low side of the partition, so that $$x$$ is the kth smallest element and there are $$n-k$$ elements on the high side of the partition.
5. If $$i=k$$, then return $$x$$, otherwise, use select recursively to find the ith smallest element on the low side if $$ik$$.

Python implementation of the algorithm.

def partition(arr, lo, hi, pivot) -> int:
for i in range(lo, hi):
if arr[i] == pivot:
arr[hi], arr[i] = arr[i], arr[hi]
break

i = lo

for j in range(lo, hi):
if arr[j] >= pivot:
arr[j], arr[i] = arr[i], arr[j]
i += 1

arr[i], arr[hi] = arr[hi], arr[i]
return i

def find_median(arr, lo, n):
lst = []
for i in range(lo, lo+n):
lst.append(arr[i])

lst.sort()

return lst[n//2]

def select(arr, lo, hi, k) -> int:
# number of elements in arr[lo, hi]
n = hi - lo + 1
medians = []

i = 0
while (i<n//5):
medians.append(find_median(arr, lo+i*5, 5))
i += 1

# last group
if i*5 < n:
medians.append(find_median(arr, lo+i*5, n%5))
i+=1

# Find median of all medians using recursive call.
# If medians has only one element, then no need
# of recursive call
if i == 1:
med_of_meds = medians[0]
else:
med_of_meds = select(medians, 0, i-1, i//2)

# Partition the array around a med_of_meds
# element and get position of pivot
# element in sorted array
pos = partition(arr, lo, hi, med_of_meds)

# If position is the same as k
if (pos - lo == k - 1):
return arr[pos]
# If position is more,
# recur for left subarray
if (pos - lo > k-1):
return select(arr, lo, pos-1, k)

# Else recur for right subarray
return select(arr, pos+1, hi, k-pos+lo-1)
print(select([1,2,3,4,5],0, 4, 2))

4


6.5. Dynamic programming

Dynamic programming solves problems by combining the solutions to subproblems. "Programming" in this context refers to a tabular mothod, not to writing computer code.

DP is usually applied to optimization problems that can be divided into subproblems, and these subproblems have overlapping subsubprolems, i.e. they share some common subsubproblems.

Usually, there exist multiple solutions to a problem, and we want a solution that gives an optimal (minimum or maximum) value, since there might also exist multiple solutions that give us the same optimal value.

6.5.1. Four steps to develop a dynamic programming algorithm

1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution, typically in a bottom-up fashion
4. Construct an optimal solution from computed information
1. This step is only needed when we want not only the value of the solution, but also the solution itself.
2. This step is where DP needs $$O(N)$$ space (if input is one dimentional array) as it needs to store the computed information.

6.5.2. Rod cutting example

6.5.2.1. The problem

Given a rod of length n inches and a table of prices[i], i=1,2,...,n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the price prices[n] for a rod of length n is large enough, an optimal solution may require no cutting at all.

6.5.2.2. The solution

To cut a rod of length n into rods of 1 inch, we need to cut n-1 times. By thinking of this as a problem of bitmasking, where we have a binary number of n-1 bits, and 1 represents cut, 0 represents no cut, it is easy to deduce that the number of possible ways to cut the rod is $$2^{n-1}$$.

Given the prices table, any revenue $$r_n$$ of a length n rod can be represented as follows: $$r_n=\max(p_n, r_1+r_{n-1}, r_2+r_{n-2},...,r_{n-1}+r_1)$$. (Recursively define the value of an optimal solution) $$p_n$$ corresponds to making no cuts at all. The remaining n-1 arguments correspond to the maximum revenue obtained by making an initial cut of the rod into two pieces of size i and n-i, for each $$i=1,2,...,n-1$$, and then optimally cutting up those pieces further, obtaining revenues $$r_i$$ and and $$r_{n-i}$$ from those two pieces.

We say the rod-cutting problem exihibits optimal substructure, i.e. optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently. It also has overlapping subsubproblems. For example, one needs to $$r_1$$ twice for $$r_i$$ and $$r_{n-i}$$.

The equation $$r_n=\max(p_n, r_1+r_{n-1}, r_2+r_{n-2},...,r_{n-1}+r_1)$$ has duplicate values since when doing cutting (bitmasking), "100" is the same as "001". Therefore, we can simplify this process of cutting by the following:

1. We cut a first piece of length i off the left-hand end
2. We only further divided the right-hand end remainder of length n-i.
3. The revenue is then $$r_n=\max_{1\le i\le n}(p_i+r_{n-i})$$, which removes one recursion ($$r_i$$) for us.
6.5.2.2.1. Recursive top-down implementation

Here is an implementation of the above formula $$r_n=\max_{1\le i\le n}(p_i+r_{n-i})$$.

<<imports for typing>>
def cut_rod(p: List[int], n: int) -> int:
from math import inf
if n == 0:
return 0
q = -inf
for i in range(1, n+1):
# implementation detail
# the array in the book starts with 1
# here the array starts with 0
q = max(q, p[i-1]+cut_rod(p, n-i))
return q
print(cut_rod([1,2,3,9], 3))

3


This implementation is slow because it's time complexity is $$O(n^2),\text{ where }n=\text{len}(p)$$. Many same operations were done multiple times. For example, when solving cut_rod(p, n) and cut_rod(p, n-1), cut_rod(p, n-2) was calculated twice.

6.5.2.2.2. Dynamic programming solution

We only need to solve one problem in 6.5.2.2.1 to make it significantly faster, namely, we want to solve each subproblem exactly once and save it (extra memory) for future use.

Dynamic programming runs in polynomial time when the number of distinct subproblems involved is polynomial in the input size and we can solve each sub subproblem in polynomial time. There are usually two ways to implement a dynamic programming approach - top-down with memoization and bottom-up.

Top-down with memoization:

1. Recursive
2. Save the result of each subproblem in an array or hash table
3. For every subproblem, first check if we have already solved it
4. If so, just return the value
5. If not, compute the value for the subproblem

Bottom-up:

1. Typically depends on some natural notion of the "size" of a subproblem, s.t. solving any particular subproblem depends only on solving "smaller" subproblems.
2. We sort the subproblems by size and solve them in size order, smallest first.
3. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon beforehand, and we have saved their solutions.

These two methods are asymptotically the same.

1. top-bottom approach code

Here is the Python code for dynamic programming using top-bottom memoization method.

def memoized_cut_rod(p, n):
from math import inf
def memoized_cut_rod_aux(p, n, r):
if r[n] >= 0:
return r[n]
if n == 0:
q = 0
else:
q = -inf
for i in range(1, n+1):
q = max(q, p[i-1]+memoized_cut_rod_aux(p, n-i, r))
r[n] = q
return q

r = [-inf for i in range(n+1)]

return memoized_cut_rod_aux(p, n, r)
print(memoized_cut_rod([1,2,3,9], 3))

3

2. bottom-up approach code

Here is the bottom-up approach, which is simpler and easier to understand for me. Recall the revenue is $$r_n=\max_{1\le i\le n}(p_i+r_{n-i})$$. We need to prove that $$r_n=\max(p_n, r_1+r_{n-1}, r_2+r_{n-2},...,r_{n-1}+r_1)$$ is in effect equivalent to $$r_n=\max_{1\le i\le n}(p_i+r_{n-i})$$, so that we can justify the use of an inner loop in the code below.

def bottom_up_cut_rod(p, n):
from math import inf

r = [0 for i in range(n+1)]
for i in range(1, n+1):
q = -inf
# This inner loop is introduced because
# we cannot know, ahead of time, the best cutting strategy
# that will give us the highest return.
# Therefore we need to check all possible strategies,
for j in range(1, i+1):
# p[j-1] is the price of a length j rod
# r[i-j] is the best return of length i-j rod, which should be already calculated
#q = max(q, p[j-1] + r[i-j])
# q is the possible return from previous operations in this inner loop
q = max(q, r[j] + r[i-j], p[j-1]) # this is easier to understand
r[i] = q
return r[n]
print(bottom_up_cut_rod([1,4,4,4,9], 4))

8

3. Reconstructing a solution

6.6. Single-Source Shortest Paths

Relaxation in Dijkstra's Algorithm: http://web.cs.unlv.edu/larmore/Courses/CSC269/pathing.

The notion of "relaxation" comes from an analogy between the estimate of the shortest path and the length of a helical tension spring, which is not designed for compression. Initially, the cost of the shortest path is an overestimate, likened to a stretched out spring. As shorter paths are found, the estimated cost is lowered, and the spring is relaxed. Eventually, the shortest path, if one exists, is found and the spring has been relaxed to its resting length.

6.6.1. Definition

In a shortest-paths problem, we are given a weighted, directed graph $$G=(V, E)$$, with weight function $$w: E \rightarrow \mathbb{R}$$ mapping edges to real-valued weights. The weight $$w(p)$$ of a path $$p=\langle v_0, v_1,\ldots,v_k\rangle$$ is the sum of the weights of its constituent edges:

$$w(p) = \sum_{i=1}^k w(v_{i-1}, v_i)$$

We define the shortest-path weight $$\delta(u,v)$$ from $$u$$ to $$v$$ by

$$\delta(u,v)= \begin{cases} \min{\{ w(p): u \overset{p}{\leadsto} v\}} &\text{if there is a path from $$u$$ to $$v$$}\\ \infty &\text{else} \end{cases}$$

To put it simply, the shortest-path weight from $$u$$ to $$v$$ either

1. does not exist ($$\infty$$), or
2. is the minimum weight of all possible weights of different paths (or simply one path) from $$u$$ to $$v$$.

A shortest path from vertex $$u$$ to vertex $$v$$ is then defined as any path $$p$$ with weight $$w(p)=\delta (u,v)$$.

Concepts:

1. Vertices, that are connected to create
2. directed Edges, that are given real-valued
3. Weights
4. Directed Edges with Weights, that form
5. Paths with Weights

Single-source shortest-paths problem (SSSP): Given a directed graph $$G=(V, E)$$, we want to find a shortest path from a given source vertex $$s\in V$$ to each vertex $$v\in V$$.

This seems also like a dynamic programming problem because:

1. We are looking fo a minimum value
2. This value can be obtained by obtaining the minimum value of subproblems of the same kind
6.6.1.1. Variants of the SSSP problem

Single-destination shortest-paths problem: Find a shortest path to a given destination vertex $$t$$ from each vertex $$v$$. By reversing the direction of each edge in the graph, we can reduce this problem to SSSP.

Single-pair shortest-path problem: Find a shortest path from $$u$$ to $$v$$ fro given vertices $$u$$ and $$v$$. If we solve the SSSP problem with source vertex $$u$$, then we solve this problem as well. Moreover, all known algorithms for this problem have the same worst-case asymptotic running time as the best SSSP problem algorithms (❓).

All-piars shortest-paths problem: Find a shortest path from $$u$$ to $$v$$ for every pair of vertices $$u$$ and $$v$$. Although we can solve this problem by running a single-source algorithm once from each vertex, we usually can solve it faster (as there are many repeated calculations in this algorithm).

6.6.1.2. Summary of the four problems

Using databse cardinality:

• $$1:1$$: One vertex to one vertex.
• $$1:many$$: One vertex to multiple vertices.
• $src:many: base/example problem the algorithm works with. • $$many:1$$: Multiple vertices to one vertex. •$many:dest: can be solved by inverting directions of edges and starting from $$dest$$ to $$many$$.
• $$many:many$$: Every vertex to every vertex.

6.6.2. Optimal substructure of a shortest path

Shortest paths algorithms typically rely on the property that a shortest path between two vertices contains other shortest paths within it. This property calls for 4.2 and Greedy method.

Dijkstra's algorithm is a greedy algorithm, and the Floyd-Warshall algorithm, which finds shortest paths in $$many:many$$ vertices, is a dynamic-programming algorithm.

6.6.3. Negative-weight edges

A graph $$G=(V, E)$$ can contain negative-weighted edges $$E_{nw}$$ but and be well defined, given that: for any vertex pair $$(u,v)$$, if $$w(u, v)<0, w(v, u) > 0$$, then $$w(u,v)+w(v, u)\ge 0$$. This prevents a negative-weight cycle.

Non-negative (+6-3)
+----+ 5   +----+ +6  +----+
|src |---->|5   |---->|11  |
|    |     |    |<----|    |
+----+     +----+ -3  +----+

Negative (+6-7)
+----+ 5   +----+ +6  +----+
|src |---->|-inf|---->|-inf|
|    |     |    |<----|    |
+----+     +----+ -7  +----+


6.7. Data structure

Dynamic sets: sets that can grow, shrink, or otherwise change over time. Dictionary: a dynamic set that supports insert, delete, and test (membership)

 Category Operation Query search()

6.7.1. Stacks and queues

Table 5: Data structures based on list/array
data structure policy example
Queue first in, first out real life queue
Stack last in, first out recursive call stack
Priority queue whatever in, min/max key out Triage

Stack operations (all $$O(1)$$):

• push(element)
• pop()
• stack_empty()

Queue operations (all $$O(1)$$):

• enqueue(element)
• dequeue()

• circular list

The following content concerns unsorted Doubly Linked List.

6.7.3. Hash tables

Addressing: Putting one item to a place according to some rule.

Direct-address tables: associate keys with indexes in an array of size U, when the number of possible keys $$U$$ is small. $$O(1)$$ for searching in worst-case scenario.

When $$U$$ is large, creating an array/table $$T$$ of size U may be immpractical. In addition, the number of keys actually stored may be so small relative to $$U$$ that most of the space allocated to the table $$T$$ will be wasted.

Thus we come up with another idea (Hash Table) to save storage and maintain $$O(1)$$ search time in average-case scenario.

With hash tables, we now cannot use an element's key to store it because its key might be larger than the length of the hash table. To solve this problem, we use a hash function $$h$$ to compute the slot/position in the table $$T$$ from key $$k$$. $$h$$ maps the universe $$U$$ of keys into the slots of a hash table $$T[0\ldots m-1]$$: $$h:U\rightarrow \{0,1,\ldots,m-1\}$$ and $$m$$ is usually much less than $$|U|$$.

We also say that an element with key $$k$$ hashes to slot $$h(k)$$, and that $$h(k)$$ is the hash value of key $$k$$. If two keys somehow hash to the same slot, this is called a collision.

To minimise or even avoid collision, we make $$h$$ appear to be "random", making its output as dispersed as possible.

There are two ways to deal with collision: chaining and open addressing. Chaining: make every slot in the table $$T$$ a linked list (doubly linked list makes deletion faster).

In a nutshell:

1. We want to store some objects in such a way that it's fast for us to get to them later via some key.
2. We then just use an array to store the objects, each is placed in the array using their key as the index, and one can use a key to find the corresponding object in the array. This is called open addressing.
3. As the number of potential objects grows, it requires more storage. However, most of the time, we only want a subset of the objects to be readily available because those are what we use anyway.
4. Therefore, there is really no need to store all possible objects.
5. Then we decide to use a smaller array to store the objects.
6. Because the key of an object is no longer also an index in the smaller array (the key might be larger than the length of the array), it is logical to develop a function to map the key to an index of the array.
7. The function is properly named hash function.
8. The array is then called a hash table.
9. The story does not end here. Because there are more objects than the number of places available to store them in the array (hash table), it is possible that two elements will be put in the same position (two different keys end up with the same index through the hash function). Pigeon hold theorem.
1. To solve this, we have chaining and open addressing
2. Chaining links all elements that ended up in the same index so the 1-d array now becomes 2-d.
1. Because the linking of the elements at one index can be infinite (as long as the memory is sufficient), the hash table can store infinite objects, but the time spent on retrieving one object also increases until it becomes asymptotically the same as directly searching through all objects.
3. Open addressing tries to find the next available index if the current index is already taken.
1. This means that the table can fill up and no more insertion can be made.

6.7.4. Priority queue

We use Heap to implement it.

A priority queue is a data structure for maintaining a set $$S$$ of elements, each with an associated value called a $$key$$ (priority). A max-priority queue supports the following operations:

• $$insert(S, x)$$ inserts the element $$x$$ into the set $$S$$, i.e. $$S=S\cup \{x\}$$, $$O(\lg n)$$
• $$maximum(S)$$ returns the element of $$S$$ with the largest $$key$$, $$O(1)$$
• $$extract\_max(S)$$ removes and returns the element of $$S$$ with the largest $$key$$, $$O(\lg n)$$
• $$increase\_key(S, x, k)$$ increases the value of element $$x\text{'s}$$ $$key$$ to the new value $$k$$, which is assumed to be at least as large as the current $$key$$, $$O(\lg n)$$

Similarly, a min-priority queue supports:

• $$insert(S, x)$$ inserts the element $$x$$ into the set $$S$$, i.e. $$S=S\cup \{x\}$$
• $$minimum(S)$$ returns the element of $$S$$ with the smallest $$key$$
• $$extract\_min(S)$$ removes and returns the element of $$S$$ with the smallest $$key$$
• $$decrease\_key(S, x, k)$$ decreases the value of element $$x\text{'s}$$ $$key$$ to the new value $$k$$, which is assumed to be at least as small as the current $$key$$

Max-priority queue can be used to schedule jobs on a shared computer. Min-priority queue can be used in an event-driven simulator.

6.7.4.1. Implementation of max-priority queue

Based on the pseudo-code on CLRS.

class max_priority_queue:

def __init__(self, nums: List[int]):
self.q = max_heapify(nums, 0, len(nums)-1)

def heap_max(self):
return self.q[0]

def heap_extract_max(self):
if len(self.q) < 1:
raise Exception
m = self.q[0]
self.q[0] = self.q[len(self.q)-1]
self.max_heapify(self.q, 1, self.q[0]-1)

@staticmethod
def max_heapify(arr, i, heap_size):
pass


7. Clock table

Table 6: Clock summary at [2020-05-07 Thu 09:54]