algoadvance

You are given an n x n integer matrix grid. Generate an n-2 x n-2 integer matrix result such that:

• result[i][j] is equal to the largest value in the 3x3 matrix defined as follows:
  • The top-left corner of the 3x3 matrix is at (i, j)

Return the result matrix.

Example:

Input: grid = [
  [9, 9, 8, 1],
  [5, 6, 2, 6],
  [8, 2, 6, 4],
  [6, 2, 2, 2]
]
Output: [
  [9, 9],
  [8, 6]
]

Clarifying Questions

1. Input Constraints:
   • What is the range of values for n? (Minimum and Maximum values of n)
   • What is the range of values for the elements in grid? (Minimum and Maximum values of each element)
2. Edge Cases:
   • What do we return if n is less than 3?

Strategy

1. Validations: First, we will check if n is less than 3 because an n x n grid where n < 3 cannot form even a single 3x3 subgrid. In such a case, output should be an empty list.
2. Result Matrix Initialization: Initialize a matrix result of size n-2 x n-2.
3. Iterate through the Grid:
   • Loop through each possible top-left corner position of the 3x3 subgrids.
   • For each 3x3 subgrid, find the maximum value.
   • Store the maximum value in the corresponding cell of the result matrix.
4. Return Result: Once all the maximum values have been computed, return the result matrix.

Time Complexity

The time complexity of this solution will be O(n^2), where n is the dimension of the original grid. This is because:

• We loop through each possible 3x3 subgrid using two nested loops, each running n-2 times.
• For each subgrid, we find the maximum value by iterating through 9 elements, which is a constant operation.

Code

Here’s the Python code to solve the problem:

def largestLocal(grid):
    n = len(grid)
    if n < 3:
        return []

    result = [[0] * (n - 2) for _ in range(n - 2)]
    
    for i in range(n - 2):
        for j in range(n - 2):
            max_val = -float('inf')
            for k in range(3):
                for l in range(3):
                    max_val = max(max_val, grid[i + k][j + l])
            result[i][j] = max_val
    
    return result

# Example usage:
grid = [
    [9, 9, 8, 1],
    [5, 6, 2, 6],
    [8, 2, 6, 4],
    [6, 2, 2, 2]
]

print(largestLocal(grid))  # Output: [[9, 9], [8, 6]]

This code will correctly compute the largest local values in a matrix as described by the problem statement.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?