Local Maximums - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Matrix Manipulation, Sliding Window

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is an n x n integer matrix grid.

• Q: What is the expected output of the function?

  • A: The function should return an (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?

  • A: 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?

  • A: The function assumes that 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?

  • A: For a 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]
]

P-lan

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

• Incorrectly indexing the 3 x 3 sub-matrix.
• Forgetting that the resulting matrix is of size (n-2) x (n-2).

I-mplement

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