This is the main file that contains all the problems and their solutions. Each problem is organised as follows:
- Problem number Problem name :problem_tag:
- 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
Here we start to finish our problems 😈.
from typing import List, Tuple, SetWe 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:
- 2 <= nums.length <= 100
- nums.length % 2 == 0
- 1 <= nums[i] <= 100
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]
Just an array problem.
We can usefor i in range(len(nums), 2) and create a sublist for all nums[i-1], nums[i].
Finally we concatenate these sublists.
<<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]))$O(M)\text{, where } M=∑i=0,2,4…len(nums)-2nums[i]$, the summation corresponds to the outer
for loop, we simply sum up the time it takes to build each sub list.
$O(M)\text{, where } M=∑i=0,2,4…len(nums)-2nums[i]$
Not available.
To concatenate lists in Python.
lst1=[1,2,3]
lst2=[3,3,3]
print(lst1+lst2)Given an array
nums of integers, return how many of them contain an even number of digits.
Constraints:
- 1 <= nums.length <= 500
- 1 <= nums[i] <= 10^5
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.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)).
<<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]))
Not available.
Pretty straightforward.
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:
- 2 <= nums.length <= 500
- 0 <= nums[i] <= 100
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]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.
<<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]))
Not available.
The best time complexity we can do is
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:
- in the beginning, you have the permutation
P=[1,2,3,...,m]. - For the current
i, find the position ofqueries[i]in the permutationP(indexing from 0) and then move this at the begining of the permutationP. Notice that the position ofqueries[i]inPis the result forqueries[i].
Return an array containing the result for the given queries.
Constraints:
- 1 <= m <= 10^3
- 1 <= queries.length <= m
- 1 <= queries[i] <= m
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]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).
<<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))
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))
This is based on an incorrect understanding of the problem description. See *1329 Sort the matrix diagonally 2 for a correct understanding and solution.
Given am*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:
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 100
- 1 <= mat[i][j] <= 100
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]]We first concatenate all lists in the matrix, then sort it to get
sorted_lst.
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.
<<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]]
))
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:
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 100
- 1 <= mat[i][j] <= 100
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]]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.
<<imports for typing>>
def diagonal_sort(mat: List[List[int]]) -> List[List[int]]:
n = len(mat)
m = len(mat[0])
def sort_list(head: Tuple[int]) -> None:
res = []
x, y = head
while x < n and y < m:
res.append(mat[x][y])
x+=1
y+=1
res.sort()
res = iter(res)
x, y = head
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)]
for head in diagonal_heads:
sort_list(head)
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]]
))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× (m-1)$ or $2× (n-1)$.
Therefore, our formula to calculate the total time required by the algorithm is as follows:
$O(2× (∑i=1min(n,m)-1 ilog i)+|n-m+1|× min(m,n)× log{min(m,n)})$.
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]]
))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:
- Choose 3 soldiers with index(i, j, k) with rating
(rating[i], rating[j], rating[k]). - A team is valid if:
(rating[i]<rating[j]<rating[k])orrating[i]>rating[j]>rating[k], where0<=i<j<k<n.
Soldiers can be part of multiple teams.
Return the number of teams you can form given the conditions.
Constraints:
- n == rating.length
- 1 <= n <= 200
- 1 <= rating[i] <= 10^5
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: 4We return
False for all n<3.
This is a combination problem. We need to try all combinations of the list.
<<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]))$O(Cn3)$, i.e. $O(n^3)$.
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]))
#1395 Count number of teams Leetcode 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]))Given an array of integers, $1≤ a[i] ≤ 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
Input: [4,3,2,7,8,2,3,1] Output: [2,3]
See Discussion.
We also know that, a number in the array either occurs just once or twice.
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).
<<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]))
res.
Not available.
Most interesting idea has been provided in the previous section.
<<imports for typing>>Given a set of distinct integers, nums, return all possible subsets (the power set).
Constraints: The solution set must not contain duplicate subsets.
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
We can use Python’s itertools.combinations.
<<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]))
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
bitmask = bin(i | nth_bit)[3:]
# 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]))
See *Bitmask
You are given ann*n 2D matrix representing an image.
Rotate the image 90 degrees (clockwise).
Constraints:
You have to rotate the image in-place.
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] ]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).
<<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]])
Not available.
<<imports for typing>>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]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:
- Insert a character
- Delete a character
- Replace a character
Constraints:
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')
This is a typical dynamic programming problem.
<<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]Not available.
<<imports for typing>>See *Edit distance.
Say you have an array for which theith 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.
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.
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.
<<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_buy in prices:
d_buy = price_map[p_buy]
for p_sell in reversed(prices):
d_sell = price_map[p_sell]
if p_buy<p_sell and d_buy < d_sell:
max_p = max(max_p, p_sell-p_buy)
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]))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]))
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:
- optimal substructure
- overlaping sub-problems
In this problem, sub-problems
f[i]is defined as “the minimum stock price from day 0 to dayi”, which is dependant onf[i-1]andprices[i], whichever is lower. The overlapping sub-problem here is very obvious - there’s no need to calculatef[i]by comparing stock prices from day 0 to dayi-1, which is the brute force solution, but just reuse the pre-calculated resultf[i-1].
maxprofitvariable 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 bymaxprofit=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]))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
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.Use dynamic programming. The sub-problem is “the maximum sum of previous arrays”.
<<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]))
dp array.
Not available.
<<imports for typing>>In this problem,
<<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]))
*121 Best time to buy and sell stock
The minprice in *121 Best time to buy and sell stock is the cur_sum in this question, and maxprofit in *121 Best time to buy and sell stock is the best_sum in this question.
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.
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 stepThis is basically a Fibonacci series.
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.
<<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))
- Approach 1 is brute force.
- Approaches 2 to 4 are essentially the same as my solution.
- Approach 5 uses Binets Method, which uses matrix multiplication to obtain the $nth$ Fibonacci number. Its time complexity is
$log(n)$ . Space complexity is$O(1)$ . - Approach 6 just uses the Fibonacci Formula to calculate the $nth$ Fibonacci number. It is asymptotically the same as approach 5. However, precision of calculation is lost when
nis 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))It is amazing how we can optimise this seemingly daunting problem such dramatically from $O(2^n)$ to $log(n)$!. On a staircase, the $ith$ 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:
costwill have a length in the range [2, 1000]- Every
cost[i]will be an integer in the range [0, 999].
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].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_costn-1, min_costn-2)$, and that $min_costn-1$ and $min_costn-2$ have overlapping subsubproblems. Therefore, we can use dynamic programming to solve this problem.
<<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]))
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]))
Based on the Leetcode solution, we can improve our code to get
<<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]))
- It asks for an optimal solution
- It can be divided into finding the optimal solution to subproblems
- The subproblems have overlapping subsubproblems
- DP’s goal is to only solve these overlapping problems once to save time
- A recursive definition of the optimal solution can be found
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.
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8See *Medians and order statistics.
Brute-force algorithm:
- constructing the object
- simply sort the
numsarray and store it inself.nums
- simply sort the
- running the
KthLargest.add(val)method- insert the
valin to the sortedself.nums, then getself.nums[2]
- insert the
<<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)
print(obj.add(3))
print(obj.add(5))
print(obj.add(10))
print(obj.add(9))
print(obj.add(4))
Initial sorting: add method:
*Priority queue 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
param_1 = obj.add(val)
print(param_1)
Initial sorting: add() method:
heapq provided by Python follows min-heap properties.
arr[0]is the smallest elementarr[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)See *Heapsort and *Priority queue.
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.
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: 4We can use quicksort.
See *Medians and order statistics for theory discussion and linear time algorithm (randomized quickselect).
<<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))
Quickselect implementation (a replica of *Selection in expected linear time (Quickselect)).
<<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))
Not available.
<<imports for typing>>*703 Kth largest element in a stream
We have a list ofpoints on the plane. Find the K closest points to the origin (0, 0).
Constraints:
- The distance between two points is the Euclidean distance
- The answer is unique, but its elements can be in any order.
$1≤ K ≤ points.length ≤ 10000$ $-10000<points[i][0]<10000$ $-10000<points[i][1]<10000$
Input: points = [[1,3], [-2,2]], k=1 Output: [[-2,2]]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.
<<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))$O(Klg n)$, the last line takes the most time asymptotically.
<<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]Any problem that asks for “Closest”, “Smallest”, “Largest”, K elements.
Given a non-empty array of integers, return the $k$ most frequent elements.Constraints:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
- It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
- You can return the answer in any order.
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Input: nums = [1], k = 1 Output: [1]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
<<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))
<<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))
Another quick hack to this is to use Counter object.
When heapq.nlargest() internally, which gives us sorted internally, which also gives us
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))
Seems we can also use bucket sort.
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:postTweet(userId, tweetId): compose a new tweet.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.follow(followerId, followeeId): follower follows a followee.- unfollow(followerId, followeeId): Follower unfollows a followee.
Constraints: None.
Twitter twitter = new Twitter(); // User 1 posts a new tweet (id = 5). twitter.postTweet(1, 5); // User 1's news feed should return a list with 1 tweet id -> [5]. twitter.getNewsFeed(1); // User 1 follows user 2. twitter.follow(1, 2); // User 2 posts a new tweet (id = 6). twitter.postTweet(2, 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. twitter.getNewsFeed(1); // User 1 unfollows user 2. twitter.unfollow(1, 2); // User 1's news feed should return a list with 1 tweet id -> [5], // since user 1 is no longer following user 2. twitter.getNewsFeed(1);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.
<<imports for typing>>
import collections
from datetime import datetime
import heapq
class Twitter:
def __init__(self):
"""
Initialize your data structure here.
"""
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
# ta must follow taself
self.users_followees[userId].add(userId)
self.users_followers[userId].add(userId)
# 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]:
self.users_followees[followerId].add(followeeId)
self.users_followers[followeeId].add(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.
"""
# Do not unfollow oneself
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])
# Your Twitter object will be instantiated and called as such:
obj = Twitter()
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)
-
postTweettakes$O(k)$ , where$k$ is the number of followers$userId$ has. -
getNewsFeedtakes$O(n lg n)$ withheapq.nlargest, where$n$ is the number of tweets in the user’s news feed. -
followtakes$O(n lg k)$ , where$n$ is the number of tweets thefolloweehas and$k$ is the number of tweets in user’s news feed. (this part can be improved significantly). -
unfollowtakes$O(n+m)$ , where$n$ is the number of tweets thefolloweehas,$m$ is the number of tweets in user’s news feed.
-
users_tweets:$O(m× n)$ , where$m$ is the number of users, and$n$ is the number of tweets of each user. -
users_followers:$O(m× n)$ , where$m$ is the number of users, and$n$ is the number of users who choose to follow a user. -
users_followees:$O(m× 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) -
users_newsfeeds:$O(m× 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).
Not available.
<<imports for typing>>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.
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:
- 2 <= N <= 50.
- grid[i][j] is a permutation of [0, …, N*N - 1].
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.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.
<<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)
visited_pos.add(last_pos)
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)
visited_pos.add(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]]))
<<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):
visited_poses.add(pos)
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]]))
Dynamic programming.
<<imports for typing>>
from math import inf
def swim_in_water(grid: List[List[int]]) -> int:
def adjacent_cells(pos: Tuple[int]) -> List[Tuple[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(
[abs(grid[row][col]-grid[adj_row][adj_col]) + min_times[adj_row][adj_col] for adj_row, adj_col in adjacent_cells((row, col))]
)
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]]))
Dijkstra’s algorithm.
<<imports for typing>>
from math import inf
def swim_in_water(grid: List[List[int]]) -> int:
def adjacent_cells(pos: Tuple[int]) -> List[Tuple[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
for row, col in adjacent_cells(pos):
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
unvisited.add((row, col))
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]]))We use *Dijkstra’s Algorithm.
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)
visited.add((x, y))
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]]))$O(n^2lg 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.
visited and heap.
See #778 Leetcode.
Given a binary tree, each node has value0 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:
- The number of nodes in the tree is between 1 and 1000.
- node.val is 0 or 1.
- The answer will not exceed 2^31 - 1.
Input: [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22We try to use generators to solve the calculation part of the problem. For traversing the tree, we use pre-order traversal.
<<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)
return total
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)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))
n is the number of nodes, as this algorithm visits all nodes in the tree.
paths (number of leaves of the tree), each having the length of $log(n)$ (height of the tree).
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.
arr, write a function that returns true iff the number of occurrences of each value in the array is unique.
Constraints:
- 1 <= arr.length <= 1000
- -1000 <= arr[i] <= 1000
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: trueThe problem:
- gives an array of integers that
- could be negative, 0, or positive.
- wants us to count the number of occurrences (
occur) of each value, and - return true if
occurof each integer is different.
occur) map of each value we met.
We then scan the counter map to see if there is more than one unique numbers.
<<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))$O(n)$, where $n$ is the number of elements in the array.
Not available.
<<imports for typing>>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.
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-1if 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:
- All keys and values will be in the range of [0, 1000000].
- The number of operations will be in the range of [1, 10000].
- Please do not use the built-in HashMap library.
MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // returns 1 hashMap.get(3); // returns -1 (not found) hashMap.put(2, 1); // update the existing value hashMap.get(2); // returns 1 hashMap.remove(2); // remove the mapping for 2 hashMap.get(2); // returns -1 (not found)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().
For the hash function, we simply divide the key by 100. We can use doubly linked list for handling collision.
<<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):
"""
Initialize your data structure here.
"""
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))
Not available.
<<imports for typing>>The hard part comes at the actual coding. Basically, I encountered the following issues:
- Properly use reference to inner class
- Properly reference the class itself when setting types for arguments
- Properly use
@propertydecorator andproperty.setteras 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)insert, search and startwith.
Constraints:
- You may assume that all inputs are consist of lowercase letters a-z.
- All inputs are guaranteed to be non-empty strings.
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
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.
TrieNode and a Trie.
<<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:
return self.links[ord(ch)-ord('a')] is not None
def get(self, ch: str) -> 'TrieNode':
return self.links[ord(ch) - ord('a')]
def put(self, ch: str, node: 'TrieNode') -> None:
self.links[ord(ch) - ord('a')] = node
def __init__(self):
"""
Initialize your data structure here.
"""
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)
<<imports for typing>>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
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.
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:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Constraints:
- The number of nodes in the tree is between 1 and 100.
- Each node will have value between 0 and 100.
- The given tree is a binary search tree.
- We have a BST.
- 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.
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.<<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<<imports for typing>>Constraints:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4The 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:
in the same order as ~a~ and ~b~, though this is not mentioned.- either descending or ascending.
- ignorant of the order of elements from
aandbwhen they are equal.
The lists could be empty or only have one node. The lists could have different order.
We assume thata and b are both descending or ascending.
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???
<<imports for typing>>
# Definition for singly-linked list.
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)
<<imports for typing>>This section contains widely used data structures and related problems.
This section contains widely used algorithms and related problems.
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]))
The prerequisites for using DP are:
- optimal substructure
- overlaping sub-problems
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"))
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"))
See #CLRS Dynamic programming.
https://www.youtube.com/watch?v=pVfj6mxhdMw Simple recursive solution.def binary_search(arr, left, right, target):
"""Return position of the target, or -1 if not found."""
# 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 -1This section contains techniques that do not make a full algorithm and related problems.
See #78 Subsets Leetcode Solution.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.
So we can use bitmask.
| 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"
mask = bin(nth_bit | i)[3:]
sub = []
# time complexity: n
for j in range(n):
if mask[j] == "1":
sub.append(arr[j])
res.append(sub)
return res
print(get_power_set([1,2,3]))
k in dict.keys() is $O(1)$ because keys views are set-like since their are unique and hashable.
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.
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.
Notations:
- Domain for all functions of interest:
$\mathbb{N}$ . - Worst-case running-time function
$T(n)$ .
We say that
The time complexity of an algorithm is described in the asymptotical form (big-O).
Let $f(n)$ and $g(n)$ be two functions of $n$. If $g(n)=O(f(n))$, then we define: $f(n)=Ω(g(n))$, to indicate that $f(n)$ grows asymptotically no slower than $g(n)$. Let $f(n)$ and $g(n)$ be two functions of $n$. If $f(n)=O(g(n)) \text{ and } f(n)=Ω(g(n))$, in other words, $f(n)=O(g(n)) \text{ and } g(n)=O(f(n))$, then we define: $f(n)=Θ(g(n))$. This indicates that $f(n)$ grows asymptotically as fast as $g(n)$, no faster (big-$O$), no faster (big-$Ω$). We solve the problem recursively, applying the following 3 steps at each level of the recursion:- Divide the problem into a number of subproblems that are smaller instances of the same problem (recursive case).
- 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).
- Combine the solutions to the subproblems into the solution for the original problem.
The books provides 3 methods for obtaining the asymptotic
- Substitution method - we guess a bound and then use mathematical induction to prove our guess correct.
- 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.
- <<master method>> Master method - provides bounds for recurrences of the form $T(n)=\underbrace{aT(n/b)}a \text{ subproblems}+f(n),a≥ 1, b>1$ and
$f(n)$ is a given function.
To use the master method, 3 cases need to be memorized.
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’≤ a_2’≤ \ldots ≤ 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
| Algorithm | Worst-case runing time | Average-case/expected running time | Comparison? |
|---|---|---|---|
| Insertion sort | yes | ||
| Merge | yes | ||
| Heap | - | yes | |
| Quick |
|
yes | |
| Counting | no | ||
| Radix | no | ||
| Bucket |
|
no |
- Running time:
$O(nlg 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.length$ -
$A.heap-size$ , only$A[1..A.heap-size]$ are valid elements to the heap
For any node
- parent:
$⌊ i/2⌋$ . - left child:
$2i$ - right child:
$2i+1$
There are two kinds of binary heaps: max-heaps and min-heaps.
For every node
- max-heap:
$A[parent(i)]≥ A[i]$ . - min-heap:
$A[parent(i)]≤ A[i]$ .
Max-heaps are used in the heapsort lagorithm; Min-heaps implement *Priority queue.
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)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
This makes sure that all elements
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)
<<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)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 [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.
| Sorting algo | characteristic | cache-friendly☺? |
|---|---|---|
| mergesort | sort subarrays first | cache-friendly ☺ |
| quicksort | partition into subarrays | cache-friendly ☺ |
| heapsort | all over the place | cache-unfriendly 🤕 |
Worst-case:
Three step divide-and-conquer process for a subarray
-
Divide: Partition
$A[p..r]$ into two (possibly empty) subarrays$A[p..q-1]$ and$A[q+1..r]$ such that$a≤ A[q]≤ b, a∈ A[p..q-1], b∈ 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.
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)
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+1We can randomly pick any
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:
| Case | # of elements in segments after each partitioning | Running time |
|---|---|---|
| Worst | n-1 elements and 0 elements | |
| Best |
|
|
| Average | as long as segment not empty (not the worst) |
The
The selection problem:
- Input: A set
$A$ of$n$ (distinct) numbers and an integer$i$ , with$1≤ i ≤ n$ . - Output: The element $x ∈ A,a_1< a_2 < \ldots < ai-1,x < ai+1\ldots a_n$.
randomized_select modeled after the *Quicksort 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))Steps to select:
- Divide the
$n$ elements of the input array into$⌊ n/5 ⌋$ groups and at most one group made up of the remaining$n \mod 5$ elements. - Find the median of each of the
$⌈ n/5 ⌉$ groups by first insertion-sorting the elements of each group. - Use
select()recursively to find the median$x$ of the$⌈ n/5 ⌉$ medians found in step 2. - Partition the input array around the median-of-medians
$x$ using the modified version ofpartition. 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. - If
$i=k$ , then return$x$ , otherwise, useselectrecursively to find the ith smallest element on the low side if$i<k$ , or the$(i-k)$ th smallest element on the high side if$i>k$ .
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))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.
- <<characterize-structure>>Characterize the structure of an optimal solution
- <<recursively-define-value>>Recursively define the value of an optimal solution
- Compute the value of an optimal solution, typically in a bottom-up fashion
- Construct an optimal solution from computed information
- This step is only needed when we want not only the value of the solution, but also the solution itself.
- This step is where DP needs
$O(N)$ space (if input is one dimentional array) as it needs to store the computed information.
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.
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 $2n-1$.
Given the prices table, any revenue n rod can be represented as follows:
$r_n=max(p_n, r_1+rn-1, r_2+rn-2,…,rn-1+r_1)$. (Recursively define the value of an optimal solution)
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
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
The equation $r_n=max(p_n, r_1+rn-1, r_2+rn-2,…,rn-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:
- We cut a first piece of length
ioff the left-hand end - We only further divided the right-hand end remainder of length
n-i. - The revenue is then $r_n=max1≤ i≤ n(p_i+rn-i)$, which removes one recursion (
$r_i$ ) for us.
<<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))
This implementation is slow because it’s time complexity is cut_rod(p, n) and cut_rod(p, n-1), cut_rod(p, n-2) was calculated twice.
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:
- Recursive
- Save the result of each subproblem in an array or hash table
- For every subproblem, first check if we have already solved it
- If so, just return the value
- If not, compute the value for the subproblem
Bottom-up:
- Typically depends on some natural notion of the “size” of a subproblem, s.t. solving any particular subproblem depends only on solving “smaller” subproblems.
- We sort the subproblems by size and solve them in size order, smallest first.
- 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.
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))Here is the bottom-up approach, which is simpler and easier to understand for me. Recall the revenue is $r_n=max1≤ i≤ n(p_i+rn-i)$. We need to prove that $r_n=max(p_n, r_1+rn-1, r_2+rn-2,…,rn-1+r_1)$ is in effect equivalent to $r_n=max1≤ i≤ n(p_i+rn-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,
# which were already calculated.
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))
Relaxation in Dijkstra’s Algorithm: http://web.cs.unlv.edu/larmore/Courses/CSC269/pathing.
In a shortest-paths problem, we are given a weighted, directed graph $G=(V, E)$, with weight function $w: E → \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: \begin{equation} w(p) = ∑i=1^k w(vi-1, v_i) \end{equation}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.
We define the shortest-path weight
min{\{ w(p): u \overset{p}{\leadsto} v\}} &\text{if there is a path from \(u\) to \(v\)}
∞ &\text{else}
\end{cases}
\end{equation}
To put it simply, the shortest-path weight from
- does not exist (
$∞$ ), or - is the minimum weight of all possible weights of different paths (or simply one path) from
$u$ to$v$ .
A shortest path from vertex
Concepts:
- Vertices, that are connected to create
- directed Edges, that are given real-valued
- Weights
- Directed Edges with Weights, that form
- Paths with Weights
Single-source shortest-paths problem (SSSP): Given a directed graph
This seems also like a dynamic programming problem because:
- We are looking fo a minimum value
- This value can be obtained by obtaining the minimum value of subproblems of the same kind
Single-pair shortest-path problem: Find a shortest path from
All-piars shortest-paths problem: Find a shortest path from
-
$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:dest: can be solved by inverting directions of edges and starting from
-
$many:many$ : Every vertex to every vertex.
Dijkstra’s algorithm is a greedy algorithm, and the Floyd-Warshall algorithm, which finds shortest paths in
Non-negative (+6-3)
+----+ 5 +----+ +6 +----+
|src |---->|5 |---->|11 |
| | | |<----| |
+----+ +----+ -3 +----+
Negative (+6-7)
+----+ 5 +----+ +6 +----+
|src |---->|-inf|---->|-inf|
| | | |<----| |
+----+ +----+ -7 +----+
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() |
| 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()
Three types of linked lists:
- singly linked list
- doubly linked list
- circular list
The following content concerns unsorted Doubly Linked List.
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
When U may be immpractical.
In addition, the number of keys actually stored may be so small relative to
Thus we come up with another idea (Hash Table) to save storage and maintain
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
We also say that an element with key
To minimise or even avoid collision, we make
There are two ways to deal with collision: chaining and open addressing.
Chaining: make every slot in the table
In a nutshell:
- We want to store some objects in such a way that it’s fast for us to get to them later via some key.
- 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.
- 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.
- Therefore, there is really no need to store all possible objects.
- Then we decide to use a smaller array to store the objects.
- 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.
- The function is properly named hash function.
- The array is then called a hash table.
- 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.
- To solve this, we have chaining and open addressing
- Chaining links all elements that ended up in the same index so the 1-d array now becomes 2-d.
- 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.
- Open addressing tries to find the next available index if the current index is already taken.
- This means that the table can fill up and no more insertion can be made.
A priority queue is a data structure for maintaining a set
-
$insert(S, x)$ inserts the element$x$ into the set$S$ , i.e.$S=S∪ \{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∪ \{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.
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| Headline | Time |
|---|---|
| Total time | 1d 15:49 |
| Problems | 23:22 |
| Algorithms | 0:54 |
| Techniques | 0:20 |
| CLRS Notes & Yufei Tao lecture notes | 11:47 |
| Exporting | 0:38 |
| Fix up | 2:48 |
ob-ein.el, set KEEP-KEYWORD to t for (org-babel-remove-result).