2D Matrix

Question 1

implement a class for 2D matrix (immutable) which is easy to compute sum of any rectangle region

Answer 1

cache sum of regions from (0, 0) to (i, j) – O(m*n)

get sum of region from (i_1, j_1) to (i_2, j_2) – O(1)

Question 2

sparse matrix implementations

Answer 2

1. Dictionary of keys (row, col) -> value
2. List of Lists of tuple (col, value) – sorted by col index
3. Coordinate List of tuple (row, col, value) – sorted by row, col
4. Compressed Sparse Row (scipy implementation)
   3 matrices
   A – all non-zero values
   IA – IA[0]=0, IA[i] = IA[i-1] + #non-zeros in row i-1
   JA – column indices for non-zero values

Question 3

sparse matrix dot product

Answer 3

List of lists
iterate through (row_A, col_A) in A,
iterate through (row_B = col_A, col_B) in B
add (row_A, col_B) value into M

Question 4

find the largest square with all 1s in a binary matrix

Answer 4

num[i, j] = min(num[i-1, j], num[i, j-1], num[i-1, j-1]) + 1 if val ==1 else 0

Question 5

find the largest rectangle with all 1s in a binary matrix

Answer 5

sum over one row;

find the max area in a histogram

Question 6

find the max area under a histogram

Answer 6

two pointers:
start (the start point with non-zero height in the consecutive area), end
min_height = min(min_height, height[end-1])
area = (end-start) * min_height
max_area = max(max_area, area)