Leetcode problem 114 - 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

/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var largestLocal = function (grid) {
  // Create a new matrix array with dimensions (grid.length - 2) x (grid[0].length - 2)
  const matrix = new Array(grid.length - 2)
    // Fill the matrix with zeros
    .fill(0)
    // For each row in the matrix, create a new array and fill it with zeros
    .map(() => new Array(grid[0].length - 2).fill(0));

  // Loop through each cell in the grid, excluding the last two rows and columns
  for (let i = 0; i < grid[i].length - 2; i++) {
    for (let j = 0; j < grid.length - 2; j++) {
      // Set the value of the current cell in the matrix to the maximum value
      // of the 3x3 subgrid centered at the current cell in the grid
      matrix[i][j] = Math.max(
        grid[i][j],
        grid[i][j + 1],
        grid[i][j + 2],
        grid[i + 1][j],
        grid[i + 1][j + 1],
        grid[i + 1][j + 2],
        grid[i + 2][j],
        grid[i + 2][j + 1],
        grid[i + 2][j + 2]
      );
    }
  }

  // Return the resulting matrix
  return matrix;
};

The time complexity of this code is O(n^2), where n is the length of the grid. This is because there are two nested loops that iterate through the grid, and for each cell, the code performs a constant number of operations (comparisons and assignments).

The space complexity of this code is O(n^2) as well. This is because the code creates a new matrix array with dimensions (grid.length - 2) x (grid[0].length - 2), which has the same number of cells as the original grid. Therefore, the space required for the matrix array is proportional to the size of the grid.