Scale Engineer

Largest Local Values in a Matrix

Easy
#2160Time: `O(n^2)`. The algorithm iterates through `(n-2) * (n-2)` possible top-left corners. For each corner, it scans a `3x3` grid, which is a constant time operation (9 lookups). Thus, the total time is proportional to `(n-2)^2 * 9`, which simplifies to `O(n^2)`.Space: `O((n-2)^2)` or `O(n^2)`. This space is required for the output matrix `maxLocal`. If the output space is not considered, the auxiliary space complexity is `O(1)`.1 company
Data structures
ArrayMatrix
Companies
OpenAI

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly implements the logic described in the problem statement. We iterate through each possible top-left corner of a 3 x 3 subgrid in the input grid. For each of these subgrids, we find the maximum value and store it in the corresponding cell of the resulting maxLocal matrix.

Algorithm

  • Get the size n of the input grid.
  • Create a new result matrix maxLocal of size (n - 2) x (n - 2).
  • Loop for i from 0 to n - 3:
    • Loop for j from 0 to n - 3:
      • Initialize a variable currentMax to 0 (since grid values are positive).
      • Loop for k from i to i + 2:
        • Loop for l from j to j + 2:
          • Update currentMax = max(currentMax, grid[k][l]).
      • Set maxLocal[i][j] = currentMax.
  • Return maxLocal.

Walkthrough

The core idea is to simulate the process of finding the largest local value for every possible 3x3 subgrid. The center of these subgrids will form the new (n-2)x(n-2) matrix.

  1. We first determine the dimensions of the output matrix, which will be (n - 2) x (n - 2) since the 3 x 3 windows cannot be centered on the border elements of the grid.
  2. We create a new matrix maxLocal of this size.
  3. We use a pair of nested loops to iterate from i = 0 to n - 3 and j = 0 to n - 3. These (i, j) coordinates represent the top-left corner of a 3 x 3 subgrid in the original grid and also correspond to the indices of the maxLocal matrix.
  4. For each (i, j), we perform another nested loop to traverse the 3 x 3 subgrid. This inner loop iterates from row k = i to i + 2 and column l = j to j + 2.
  5. Inside the innermost loop, we keep track of the maximum element found within the current 3 x 3 window. We initialize a variable currentMax and update it with grid[k][l] if grid[k][l] is larger.
  6. After scanning the entire 3 x 3 window, the value of currentMax is assigned to maxLocal[i][j].
  7. Once the outer loops are complete, the maxLocal matrix is fully populated and can be returned.
class Solution {    public int[][] largestLocal(int[][] grid) {        int n = grid.length;        int[][] maxLocal = new int[n - 2][n - 2];         for (int i = 0; i < n - 2; i++) {            for (int j = 0; j < n - 2; j++) {                maxLocal[i][j] = findMax(grid, i, j);            }        }        return maxLocal;    }     // Helper function to find the maximum in a 3x3 subgrid    private int findMax(int[][] grid, int r, int c) {        int maxVal = 0;        for (int i = r; i < r + 3; i++) {            for (int j = c; j < c + 3; j++) {                if (grid[i][j] > maxVal) {                    maxVal = grid[i][j];                }            }        }        return maxVal;    }}

Complexity

Time

`O(n^2)`. The algorithm iterates through `(n-2) * (n-2)` possible top-left corners. For each corner, it scans a `3x3` grid, which is a constant time operation (9 lookups). Thus, the total time is proportional to `(n-2)^2 * 9`, which simplifies to `O(n^2)`.

Space

`O((n-2)^2)` or `O(n^2)`. This space is required for the output matrix `maxLocal`. If the output space is not considered, the auxiliary space complexity is `O(1)`.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem definition.

  • It is optimal in terms of auxiliary space (if the output array is not counted).

Cons

  • Performs redundant computations. When sliding the 3x3 window, it re-evaluates the maximum over shared elements instead of reusing previous calculations.

Solutions

class Solution {public  int[][] largestLocal(int[][] grid) {    int n = grid.length;    int[][] ans = new int[n - 2][n - 2];    for (int i = 0; i < n - 2; ++i) {      for (int j = 0; j < n - 2; ++j) {        for (int x = i; x <= i + 2; ++x) {          for (int y = j; y <= j + 2; ++y) {            ans[i][j] = Math.max(ans[i][j], grid[x][y]);          }        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem