# Largest Local Values in a Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-local-values-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/largest-local-values-in-a-matrix
**Data structures:** Array, Matrix
**Companies:** [OpenAI](https://scaleengineer.com/companies/openai)
---
## 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_.

**Example 1:**

![](https://assets.glich.co/dsa/largest-local-values-in-a-matrix/image0.png) 

**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:**

![](https://assets.glich.co/dsa/largest-local-values-in-a-matrix/image1.png) 

**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
## Brute-Force Iteration
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.
**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)`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Sliding Window Optimization
This approach optimizes the process by breaking down the 2D problem into two 1D passes. First, it computes the maximums of all `1x3` horizontal sliding windows. Then, it uses these results to find the maximums of `3x1` vertical windows of these horizontal maximums, which corresponds to the `3x3` maximums in the original grid. This avoids redundant comparisons.
**Time:** `O(n^2)`. The horizontal pass involves `n * (n-2)` iterations, each with 2 comparisons, totaling `O(n^2)`. The vertical pass involves `(n-2) * (n-2)` iterations, each with 2 comparisons, also `O(n^2)`. The overall complexity is `O(n^2)`, but with a smaller constant factor than the brute-force approach, making it faster in practice. · **Space:** `O(n^2)`. This approach requires an auxiliary matrix `horizontalMax` of size `n x (n-2)`, which contributes `O(n^2)` to the space complexity. This is in addition to the `O(n^2)` space for the output matrix.
**Pros:** More efficient in practice due to fewer comparisons per output cell.; Effectively reuses computations by breaking the problem down.
**Cons:** Requires extra `O(n^2)` space for the intermediate matrix.; The implementation is slightly more complex with two separate passes.
### Explanation
This method reduces the number of comparisons by pre-calculating intermediate results. It consists of two main passes:

**1. Horizontal Pass:**
*   Create an intermediate matrix, `horizontalMax`, of size `n x (n - 2)`.
*   Iterate through each row `i` of the `grid`.
*   For each row, slide a window of size 3 across the columns. For each position `j`, calculate the maximum of `grid[i][j]`, `grid[i][j+1]`, and `grid[i][j+2]`, and store it in `horizontalMax[i][j]`.

**2. Vertical Pass:**
*   Create the final `maxLocal` matrix of size `(n - 2) x (n - 2)`.
*   Now, iterate through the `horizontalMax` matrix. For each cell `(i, j)` in the final `maxLocal` matrix, the value is the maximum of `horizontalMax[i][j]`, `horizontalMax[i+1][j]`, and `horizontalMax[i+2][j]`. This gives the maximum value in the original `3x3` subgrid.
*   Store this final maximum value in `maxLocal[i][j]`.

This two-pass approach effectively computes the maximum of a `3x3` area by first finding the max of each of its three rows and then finding the max of those three values.

```java
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        
        // Step 1: Pre-calculate max in each 1x3 horizontal window
        int[][] horizontalMax = new int[n][n - 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 2; j++) {
                int maxVal = Math.max(grid[i][j], grid[i][j + 1]);
                maxVal = Math.max(maxVal, grid[i][j + 2]);
                horizontalMax[i][j] = maxVal;
            }
        }
        
        // Step 2: Use horizontal maxes to find max in each 3x3 window
        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 maxVal = Math.max(horizontalMax[i][j], horizontalMax[i + 1][j]);
                maxVal = Math.max(maxVal, horizontalMax[i + 2][j]);
                maxLocal[i][j] = maxVal;
            }
        }
        
        return maxLocal;
    }
}
```
### Algorithm
*   Get the size `n` of the input `grid`.
*   Create an intermediate matrix `horizontalMax` of size `n x (n - 2)`.
*   **Horizontal Pass:**
    *   Loop for `i` from `0` to `n - 1`:
        *   Loop for `j` from `0` to `n - 3`:
            *   `horizontalMax[i][j] = max(grid[i][j], grid[i][j+1], grid[i][j+2])`.
*   Create the result matrix `maxLocal` of size `(n - 2) x (n - 2)`.
*   **Vertical Pass:**
    *   Loop for `i` from `0` to `n - 3`:
        *   Loop for `j` from `0` to `n - 3`:
            *   `maxLocal[i][j] = max(horizontalMax[i][j], horizontalMax[i+1][j], horizontalMax[i+2][j])`.
*   Return `maxLocal`.

# Solutions
### Java

```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 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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> largestLocal(vector<vector<int>> &grid) {
    int n = grid.size();
    vector<vector<int>> ans(n - 2, vector<int>(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] = max(ans[i][j], grid[x][y]);
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]: n = len(grid) ans = [[0] * (n - 2) for _ in range(n - 2)] for i in range(n - 2): for j in range(n - 2): ans[i][j] = max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3)) return ans

```