Leetcode 2373: Largest Local Values in a Matrix
You are given a square matrix grid of size n x n. Your task is to generate a new matrix maxLocal of size (n - 2) x (n - 2) where each element maxLocal[i][j] represents the largest value from a 3 x 3 submatrix in grid centered at (i + 1, j + 1). In other words, for each element of the new matrix, find the maximum value from its surrounding 3 x 3 region in the original grid.
Problem
Approach
Steps
Complexity
Input: The input consists of an n x n matrix grid.
Example: grid = [[3, 1, 2, 7], [6, 5, 8, 3], [9, 4, 0, 1], [7, 6, 5, 9]]
Constraints:
• 3 <= n <= 100
• 1 <= grid[i][j] <= 100
Output: Return the generated matrix maxLocal, where each element is the largest value from the corresponding 3x3 region in the original grid.
Example: Output: [[8, 8], [9, 8]]
Constraints:
Goal: The goal is to compute a new matrix where each element is the maximum of a 3x3 submatrix from the original matrix.
Steps:
• 1. Iterate through each possible 3x3 submatrix in the input matrix.
• 2. For each submatrix, find the maximum value within the 3x3 region.
• 3. Store the maximum value in the corresponding position in the new matrix.
Goal: The input matrix grid is guaranteed to have dimensions between 3 and 100, and all elements are between 1 and 100.
Steps:
• The matrix grid has a size between 3x3 and 100x100.
• Each element in the grid is an integer between 1 and 100.
Assumptions:
• The input grid will always have a size of at least 3x3.
• Input: Input: grid = [[9, 9, 8, 1], [5, 6, 2, 6], [8, 2, 6, 4], [6, 2, 2, 2]]
• Explanation: For this input, the largest 3x3 values are: [[9, 9], [8, 6]]. This corresponds to the largest values from every 3x3 region in the original grid.
• Input: 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]]
• Explanation: In this case, every 3x3 region contains a 2, so the output matrix is filled with 2.
Approach: This problem can be efficiently solved by iterating through each 3x3 submatrix and finding the maximum value within that submatrix.
Observations:
• We need to handle the edge of the matrix carefully as the 3x3 submatrix can't extend beyond the grid boundaries.
• A brute-force solution that checks every 3x3 submatrix is feasible, as the matrix size is constrained to be at most 100x100.
Steps:
• 1. Initialize an empty result matrix of size (n-2) x (n-2).
• 2. Loop through the grid, starting from index (1, 1) to (n-2, n-2).
• 3. For each position (i, j), extract the 3x3 submatrix from grid[i-1 to i+1][j-1 to j+1] and compute the maximum value.
• 4. Store the computed maximum in the corresponding position of the result matrix.
Empty Inputs:
• Empty inputs are not possible since n >= 3.
Large Inputs:
• Ensure the solution handles the largest grid size (100x100) within the time limits.
Special Values:
• If all elements of the grid are the same, the output will be a matrix filled with the same value.
Constraints:
• The solution should efficiently handle grids up to size 100x100.
vector<vector<int>> largestLocal(vector<vector<int>>& g) {
int n = g.size();
vector<vector<int>> res(n - 2, vector<int>(n - 2));
for (int i = 0; i < n - 2; ++i)
for (int j = 0; j < n - 2; ++j)
for (int ii = i; ii < i + 3; ++ii)
for (int jj = j; jj < j + 3; ++jj)
res[i][j] = max(res[i][j], g[ii][jj]);
return res;
}
1 : Function Definition
vector<vector<int>> largestLocal(vector<vector<int>>& g) {
Defines a function `largestLocal` that takes a 2D grid `g` and returns a 2D vector with the largest value in each 3x3 subgrid.
2 : Size Calculation
int n = g.size();
Calculates the size of the grid `g` and stores it in `n`.
3 : Result Vector Initialization
vector<vector<int>> res(n - 2, vector<int>(n - 2));
Initializes a result vector `res` of size `(n-2) x (n-2)` to store the maximum values from each 3x3 subgrid.
4 : Outer Loop (i)
for (int i = 0; i < n - 2; ++i)
Outer loop that iterates over the rows of the grid, limiting the index to `n-2` to avoid going out of bounds when considering 3x3 subgrids.
5 : Outer Loop (j)
for (int j = 0; j < n - 2; ++j)
Inner loop that iterates over the columns of the grid, limiting the index to `n-2` to avoid going out of bounds when considering 3x3 subgrids.
6 : Inner Loop (ii)
for (int ii = i; ii < i + 3; ++ii)
Inner loop that iterates through the rows of the 3x3 subgrid, starting from the current `i` position.
7 : Inner Loop (jj)
for (int jj = j; jj < j + 3; ++jj)
Inner loop that iterates through the columns of the 3x3 subgrid, starting from the current `j` position.
8 : Update Result
res[i][j] = max(res[i][j], g[ii][jj]);
Updates the value at `res[i][j]` with the maximum of its current value and the value in the current 3x3 subgrid (`g[ii][jj]`).
9 : Return Statement
return res;
Returns the 2D result vector `res` that contains the largest value for each 3x3 subgrid.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) since we examine each 3x3 submatrix once, and n is the grid's side length.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) as we store the result matrix of size (n-2) x (n-2).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus