2373. Largest Local Values in a Matrix

Problem Description

The given problem involves an n x n integer matrix named grid. The objective is to generate a new integer matrix called maxLocal with the dimensions (n - 2) x (n - 2). For each cell in maxLocal, its value should be the largest number found in the corresponding 3 x 3 submatrix of grid. To clarify, the submatrix corresponds to a sliding window centered around the cell (i + 1, j + 1) in the original grid, with i and j denoting row and column indices, respectively, in maxLocal. Essentially, it can be visualized as overlaying a 3 x 3 grid on top of the main grid, moving it one cell at a time, and at each position, recording the maximum value found in this overlay into the new matrix.

Intuition

To solve this challenge, the intuitive approach is to perform a nested loop traversal across the main grid that captures every possible 3 x 3 submatrix. We start this process one row and one column in from the top-left of the grid (since the edge rows and columns don't have enough neighbors for a full 3 x 3 submatrix) and end one row and one column before the bottom-right. At each iteration of the loop, we find the largest value from the current 3 x 3 submatrix and store it in the corresponding cell in the maxLocal matrix.

More specifically, the iteration will have two loops: one for traversing rows i and another for columns j. For each position (i, j), we look at rows i to i + 2 and columns j to j + 2, creating a 3 x 3 region. Making use of a list comprehension and the max() function, we find the largest value in that region and save it as the value of maxLocal[i][j]. This two-step process - finding the 3 x 3 submatrix and then the maximum value within it - is repeated until the entire maxLocal matrix is filled.

Solution Approach

The implementation utilizes a straightforward brute-force algorithm to address the problem. This strategy leverages the capability of nested loops and list comprehension for easy iteration through the matrix.

Here's a step-by-step walkthrough of the algorithm, using Python as the reference language:

1. Determine the size n of the input grid.
2. Initialize the maxLocal matrix filled with zeros, with the size (n - 2) x (n - 2), which will eventually store the largest values.
3. Start with two nested loops, where i iterates through rows from 0 to n - 2, and j iterates through columns from 0 to n - 2. These ranges are chosen to ensure we can always extract a 3 x 3 submatrix centered around grid[i + 1][j + 1].
4. For each position (i, j), extract the contiguous 3 x 3 submatrix. This is done by another nested loop, or in this case, a list comprehension, that iterates through all possible x and y coordinates in this submatrix, with x ranging from i to i + 2 and y ranging from j to j + 2.
5. Calculate the maximum value within this 3 x 3 submatrix using the max() function applied to the list comprehension, which iterates over the range of x and y and accesses the values in grid[x][y].
6. Assign this maximum value to the corresponding cell in maxLocal[i][j].

By using a list comprehension within the nested loops to calculate the maximum, the implementation avoids the need for an explicit inner loop for exploring the 3 x 3 submatrix. This makes the code more concise and readable.

Additionally, the approach does not require any extra data structures aside from the maxLocal matrix which is being filled in, indicating an in-place algorithm with no additional space complexity.

The final result will be the maxLocal matrix, which now contains the largest number from every contiguous 3 x 3 submatrix of the original grid.

1class Solution:
2    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
3        n = len(grid)
4        ans = [[0] * (n - 2) for _ in range(n - 2)]
5        for i in range(n - 2):
6            for j in range(n - 2):
7                ans[i][j] = max(
8                    grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3)
9                )
10        return ans

The above code snippet corresponds to the entire algorithm discussed, simplified into a Python method definition within a Solution class.

Example Walkthrough

Let's assume we have the following 4 x 4 grid:

19 9 8 1
25 7 5 1
37 8 6 2
44 3 2 0

We want to apply the algorithm to create a maxLocal matrix with dimensions (4 - 2) x (4 - 2), which is 2 x 2.

Here are the steps of the algorithm in action:

1. Start with i=0 and j=0. The 3 x 3 submatrix is:

   19 9 8
   25 7 5
   37 8 6

   The maximum value in this submatrix is 9. So, maxLocal[0][0] will be 9.

2. Move to i=0 and j=1. The 3 x 3 submatrix is:

   19 8 1
   27 5 1
   38 6 2

   The maximum value in this submatrix is 9. So, maxLocal[0][1] will be 9.

3. Next, i=1 and j=0. The 3 x 3 submatrix is:

   15 7 5
   27 8 6
   34 3 2

   The maximum value in this submatrix is 8. So, maxLocal[1][0] will be 8.

4. Finally, i=1 and j=1. The 3 x 3 submatrix is:

   17 5 1
   28 6 2
   33 2 0

   The maximum value in this submatrix is 8. So, maxLocal[1][1] will be 8.

After filling all the cells in maxLocal, we get the final matrix:

19 9
28 8

This 2x2 matrix represents the maximum values from each 3 x 3 sliding window within the original 4 x 4 grid.

Solution Implementation

Time and Space Complexity

The provided code snippet is used to find the maximum local element in all 3x3 subgrids of a given 2D grid. Here is an analysis of its time and space complexity:

Time Complexity:

The time complexity of the code is determined by the nested loops and the operations within them. The outer two for loops iterate over (n - 2) * (n - 2) elements since we're examining 3x3 subgrids and thus can't include the last two columns and rows for starting points of our subgrids. For each element in the answer grid, we find the maximum value within the 3x3 subgrid, which involves iterating over 9 elements (3 rows by 3 columns).

Therefore, the time complexity is: O((n-2)*(n-2)*9), which simplifies to O(n^2), assuming that the max operation within a constant-sized subgrid takes constant time.

Space Complexity:

The space complexity is determined by the additional space used by the algorithm, not including the input. In this case, we’re creating an output grid ans of size (n - 2) * (n - 2) to store the maxima of each 3x3 subgrid, which represents the additional space used.

Thus, the space complexity is: O((n-2)*(n-2)) which simplifies to O(n^2) as the size of the ans grid grows quadratically with the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.