TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Q: What is the input to the function?
n x n
integer matrix grid
.Q: What is the expected output of the function?
(n - 2) x (n - 2)
matrix local_maxes
where each element represents the maximum value found in the 3 x 3
submatrix centered around each element (i+1, j+1)
in grid
.Q: How do we determine the size of the output matrix?
local_maxes
will be of size (n - 2) x (n - 2)
because the 3 x 3
submatrix cannot be centered around the outermost rows and columns.Q: What if the input matrix is smaller than 3 x 3
?
n >= 3
, so it does not handle cases where the grid is smaller than 3 x 3
.Q: What should the function return if the input grid has the minimum size of 3 x 3
?
3 x 3
grid, the output will be a 1 x 1
matrix containing the maximum value of the entire grid.The function local_maximums()
should take an n x n integer matrix grid and return an (n-2) x (n-2) integer matrix local_maxes where each element is the largest value in every contiguous 3 x 3 sub-matrix of grid.
HAPPY CASE
Input:
[
[9,9,8,1],
[5,6,2,6],
[8,2,6,4],
[6,2,2,2]
]
Expected Output:
[
[9,9],
[8,6]
]
Input:
[
[1,1,1,1,1],
[1,1,1,1,1],
[1,1,2,1,1],
[1,1,1,1,1],
[1,1,1,1,1]
]
Expected Output:
[
[2,2,2],
[2,2,2],
[2,2,2]
]
EDGE CASE
Input:
[
[0,0,0],
[0,0,0],
[0,0,0]
]
Expected Output:
[
[0]
]
Input:
[
[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]
]
Expected Output:
[
[11,12],
[15,16]
]
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Iterate over each possible center of a 3 x 3 sub-matrix and find the maximum value within that sub-matrix. The resulting matrix will be of size (n-2)
x (n-2)
.
1. Initialize an empty list `local_maxes` to store the result.
2. Iterate through the matrix from row `1` to `n-2` (inclusive).
a. For each row, initialize an empty list `row` to store the maximums of the current row.
b. Iterate through the matrix from column `1` to `n-2` (inclusive).
i. Find the maximum value in the `3 x 3` sub-matrix centered at `(i+1, j+1)`.
ii. Append the maximum value to `row`.
c. Append `row` to `local_maxes`.
3. Return `local_maxes`.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def local_maximums(grid):
n = len(grid)
local_maxes = []
for i in range(1, n - 1):
row = []
for j in range(1, n - 1):
max_value = max(
grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1],
grid[i][j-1], grid[i][j], grid[i][j+1],
grid[i+1][j-1], grid[i+1][j], grid[i+1][j+1]
)
row.append(max_value)
local_maxes.append(row)
return local_maxes