{x}
blog image

Largest Local Values in a Matrix

You are given an n x n integer matrix grid.

Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:

  • maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.

In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.

Return the generated matrix.

 

Example 1:

Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation: The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

Example 2:

Input: grid = [[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]]
Output: [[2,2,2],[2,2,2],[2,2,2]]
Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.

 

Constraints:

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100

Solution Explanation

This problem asks us to find the largest value within each 3x3 submatrix of a given n x n matrix. The solution involves iterating through the matrix, extracting each 3x3 submatrix, and finding its maximum value. The result is an (n-2) x (n-2) matrix containing these maximum values.

Approach

The most straightforward approach is to use nested loops to iterate through all possible 3x3 submatrices. For each submatrix, we find the maximum value among its nine elements. This maximum value is then placed in the corresponding position in the resulting matrix.

Time and Space Complexity Analysis

  • Time Complexity: O(n³). The solution iterates through the (n-2) x (n-2) possible positions of the top-left corner of a 3x3 submatrix. For each submatrix, it iterates through 9 elements to find the maximum. Therefore, the overall time complexity is proportional to (n-2) * (n-2) * 9, which simplifies to O(n³).

  • Space Complexity: O(n²). The space complexity is dominated by the size of the output matrix, maxLocal, which has dimensions (n-2) x (n-2). Therefore, the space complexity is O(n²). The additional space used for temporary variables is negligible compared to the size of the output matrix.

Code Explanation (Python3)

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        ans = [[0] * (n - 2) for _ in range(n - 2)] # Initialize the result matrix
        for i in range(n - 2): # Iterate through rows of the result matrix
            for j in range(n - 2): # Iterate through columns of the result matrix
                ans[i][j] = max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3)) #Find max in 3x3 submatrix
        return ans

The Python code directly implements the described approach. It initializes the result matrix ans with zeros. The nested loops iterate through the possible top-left corners of 3x3 submatrices. A generator expression efficiently finds the maximum value within each submatrix using max(). This maximum value is then assigned to the corresponding element in the ans matrix.

Code in other Languages

The provided code snippets in Java, C++, Go and TypeScript follow the same basic approach. They differ only in syntax and specific language features but achieve the same functionality with the same time and space complexity. They all involve nested loops to iterate through submatrices and find the maximum value within each one.