Largest Local Values in a Matrix
Problem Statement
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 a grid.
Return the generated matrix.
Examples:
Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation:
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in a grid.
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 a grid.
Constraints:
n == grid.length == grid[i].length
3 <= n <= 100
1 <= grid[i][j] <= 100
Approach
The problem asks you to find the largest number in each 3×3 section of the grid. Once you’ve found the largest number for every 3×3 store it in a smaller grid of size (n−2)×(n−2).
Now the first question should arise in your mind, why do we have to store it in a (n−2)×(n−2) matrix?
For a grid of size n×n, we need to calculate the maximum value for every possible 3×3 submatrix.
To determine where these submatrices can fit, consider their top-left corners.
A 3×3 submatrix requires 3 rows and 3 columns, so the top-left corner of such a submatrix cannot be in the last two rows or columns of the grid.
This restriction leaves only (n−2)×(n−2) positions for the top-left corners.
Now for each of these positions corresponds to one 3×3 submatrix, and we compute one maximum value for each. The resulting matrix is sized to reflect these valid positions, meaning its dimensions are (n−2)×(n−2). This way, the new matrix accurately stores the maximum values for all valid 3×3 submatrices in the original grid.
We can use a variable, maxElement, to iterate through each 3×3 submatrix and store the maximum value at the position corresponding to the top-left corner of that submatrix in the resulting matrix.
Let's understand with an example:
Steps to write code
1. Define the Function
- Write a function largestLocal(grid) that takes a 2D array grid as input and processes it.
- The function is responsible for iterating over all possible top-left corners of 3 x 3 submatrices in the grid and computing the required output.
2. Implement Helper Function
- Write a function findMax(grid, x, y):
- This function extracts the 3 x 3 submatrix from the grid starting at the top-left corner (x, y).
- To traverse this submatrix, use two nested loops (from x to x+3 and y to y+3).
- Calculate the maximum element of the 3*3 matrix and return it.
3. Initialize Result Grid
- The output grid maxLocal will have dimensions (n - 2) x (n - 2), where n is the size of the input grid and filled with zeros.
- This prepares the result grid to store the maximum values from each submatrix.
4. Populate Result Grid
- Use two nested loops to iterate over all valid top-left corners (i, j) of 3 x 3 submatrices in the input grid.
- Valid indices for i and j range from 0 to n - 3.
- For each (i, j), call findMax(grid, i, j) to compute the maximum value in the corresponding 3 x 3 submatrix.
- Store this maximum value in maxLocal[i][j].
5. Return the Result
- Once the loops finish, the maxLocal grid contains the maximum values for all submatrices.
- Return maxLocal as the final output.
Code for All Languages
C++
class Solution {
private:
// Return the maximum values in the 3 x 3 matrix with top-left as (x, y).
int findMax(vector<vector<int>>& grid, int x, int y) {
int maxElement = 0;
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
maxElement = max(maxElement, grid[i][j]);
}
}
return maxElement;
}
public:
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> maxLocal(n - 2, vector<int>(n - 2, 0));
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;
}
};Java
class Solution {
// Return the maximum values in the 3 x 3 matrix with top-left as (x, y).
private int findMax(int[][] grid, int x, int y) {
int maxElement = 0;
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
maxElement = Math.max(maxElement, grid[i][j]);
}
}
return maxElement;
}
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;
}
}Python
class Solution:
# Return the maximum values in the 3 x 3 matrix with top-left as (x, y).
def find_max(self, grid, x, y):
max_element = 0
for i in range(x, x + 3):
for j in range(y, y + 3):
max_element = max(max_element, grid[i][j])
return max_element
def largestLocal(self, grid):
n = len(grid)
max_local = [[0] * (n - 2) for _ in range(n - 2)]
for i in range(n - 2):
for j in range(n - 2):
max_local[i][j] = self.find_max(grid, i, j)
return max_localJavascript
/**
* @param {number[][]} grid
* @return {number[][]}
*/
var largestLocal = function(grid) {
const n = grid.length;
// Helper function to find the maximum in a 3x3 submatrix with top-left at (x, y)
const findMax = (grid, x, y) => {
let maxElement = 0;
for (let i = x; i < x + 3; i++) {
for (let j = y; j < y + 3; j++) {
maxElement = Math.max(maxElement, grid[i][j]);
}
}
return maxElement;
};
const maxLocal = Array.from({ length: n - 2 }, () => Array(n - 2).fill(0));
for (let i = 0; i < n - 2; i++) {
for (let j = 0; j < n - 2; j++) {
maxLocal[i][j] = findMax(grid, i, j);
}
}
return maxLocal;
};
Time Complexity: O(n²)
- Outer Loops:
- The main function iterates over all valid top-left corners of 3×3 submatrices in the grid.
- These top-left corners span a range of (n−2)×(n−2), where N is the size of the input grid.
- Therefore, the outer loops execute (n−2)² iterations.
- Helper Function (findMax):
- For each top-left corner, the findMax function is called.
- Inside findMax, a 3×3 submatrix is traversed to find the maximum value.
- Traversing a 3×3 = 9 constant operations.
- Total Operations:
- The findMax function is called once for each top-left corner, i.e., (n−2)² times.
- For each call, findMax performs 9 operations.
- Total operations: 9×(n−2)²
- Simplifying by ignoring the constant 9, the total time complexity is O((n−2)²).
- Final Time Complexity: When analyzing asymptotic complexity, constants and smaller terms are disregarded, leading to a final time complexity of O(n²).
Space Complexity: O(1)
1. Input Grid
- The input grid is an n×n matrix, but this is part of the input and does not count toward additional memory usage.
- Space used by the input grid: O(1) (no additional memory allocated).
2. Result Grid (maxLocal)
- The output grid maxLocal is of size (n−2)×(n−2) because it stores one value for each 3×3 submatrix in the input grid.
- This grid is explicitly created and occupies additional memory.
- Space used by maxLocal: O((n - 2)²).
3. Helper Function (findMax)
- The helper function findMax uses local variables (like maxElement) to compute the maximum value in a 3×3 submatrix.
- These variables are stored in the stack frame and are constant for each call.
- Space used by findMax: O(1).
4. Loop Variables
- Loop variables in the main function (e.g., i and j) and within the helper function use constant space.
- Space used by loop variables: O(1).
5. Total Space Complexity
- The dominant term in the space usage is the memory allocated for the result grid maxLocal, which is proportional to (n - 2)².
- Therefore, the total space complexity is: O((n - 2)²)
- In asymptotic terms, since n dominates n-2 for large values of n, the space complexity simplifies to: O(n²)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.