problemeasyalgorithmsleetcode-2373leetcode 2373leetcode2373

Largest Local Values in a Matrix

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode
Video Solutions:

Problem

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.

Examples

Example 1:

Input=[9981 5626 8264 6222],Output=[99 86]Input = \begin{bmatrix} \color{red} 9 & \color{red} 9 & 8 & 1 \\\ 5 & \color{red} 6 & 2 & \color{red} 6 \\\ \color{red} 8 & 2 & \color{red} 6 & 4 \\\ 6 & 2 & 2 & 2 \end{bmatrix} , Output = \begin{bmatrix} 9 & 9 \\\ 8 & 6 \end{bmatrix}
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=[11111 11111 11211 11111 11111],Output=[222 222 222]Input = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ 1 & 1 & \color{red} 2 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \end{bmatrix} , Output = \begin{bmatrix} 2 & 2 & 2 \\\ 2 & 2 & 2 \\\ 2 & 2 & 2 \end{bmatrix}
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.

Solution

Method 1 - Nested Loops with sliding window of 3x3 matrix

We create the 2 nested loops - 0 to n -2...which will fill the answer array. Now, we can run nested 3x3 loop to find max we have seen so far. These last 2 loops are like a sliding window

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/P2nnzCljkvI" frameborder="0" allowfullscreen></iframe></div>

Code

Java
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 k = 0; k < 3; k++) {
					for (int l = 0; l < 3; l++) {
						ans[i][j] = Math.max(ans[i][j], grid[i + k][j + l]);
					}
				}
			}
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n^2) - We run 2 outer loops with (n-2)x(n-2) complexity and 2 inner loops with 3x3 = 9 times the complexity. Hence O(9n^2) = O(n^2)
  • 🧺 Space complexity: O(1)

Comments