LeetCode 2373: Largest Local Values in a Matrix

Explanation:

To solve this problem, we iterate over the matrix and for each 3x3 submatrix, we find the maximum value and store it in the result matrix. We start from the top-left corner of the grid and move right and down, updating the result matrix accordingly.

• Algorithm:

  1. Initialize an empty result matrix maxLocal of size (n-2) x (n-2).
  2. Iterate over the grid matrix up to (n-2) x (n-2) submatrices.
  3. For each 3x3 submatrix, find the maximum value and store it in the maxLocal matrix.
  4. Return the maxLocal matrix as the output.

• Time Complexity: O(n^2) where n is the size of the input matrix.

• Space Complexity: O(1) excluding the space required for the output matrix.

class Solution {
    public int[][] maxLocalValues(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++) {
                int max = Integer.MIN_VALUE;
                for (int k = i; k < i + 3; k++) {
                    for (int l = j; l < j + 3; l++) {
                        max = Math.max(max, grid[k][l]);
                    }
                }
                maxLocal[i][j] = max;
            }
        }

        return maxLocal;
    }
}