Local Maximums

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.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• 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