2373. Largest Local Values in a Matrix
Problem Description
The given problem involves an n x n
integer matrix named grid
. The objective is to generate a new integer matrix called maxLocal
with the dimensions (n - 2) x (n - 2)
. For each cell in maxLocal
, its value should be the largest number found in the corresponding 3 x 3
submatrix of grid
. To clarify, the submatrix corresponds to a sliding window centered around the cell (i + 1, j + 1)
in the original grid, with i
and j
denoting row and column indices, respectively, in maxLocal
. Essentially, it can be visualized as overlaying a 3 x 3
grid on top of the main grid, moving it one cell at a time, and at each position, recording the maximum value found in this overlay into the new matrix.
Intuition
To solve this challenge, the intuitive approach is to perform a nested loop traversal across the main grid that captures every possible 3 x 3
submatrix. We start this process one row and one column in from the top-left of the grid (since the edge rows and columns don't have enough neighbors for a full 3 x 3
submatrix) and end one row and one column before the bottom-right. At each iteration of the loop, we find the largest value from the current 3 x 3
submatrix and store it in the corresponding cell in the maxLocal
matrix.
More specifically, the iteration will have two loops: one for traversing rows i
and another for columns j
. For each position (i, j)
, we look at rows i
to i + 2
and columns j
to j + 2
, creating a 3 x 3
region. Making use of a list comprehension and the max()
function, we find the largest value in that region and save it as the value of maxLocal[i][j]
. This two-step process - finding the 3 x 3
submatrix and then the maximum value within it - is repeated until the entire maxLocal
matrix is filled.
Solution Approach
The implementation utilizes a straightforward brute-force algorithm to address the problem. This strategy leverages the capability of nested loops and list comprehension for easy iteration through the matrix.
Here's a step-by-step walkthrough of the algorithm, using Python as the reference language:
- Determine the size
n
of the inputgrid
. - Initialize the
maxLocal
matrix filled with zeros, with the size(n - 2) x (n - 2)
, which will eventually store the largest values. - Start with two nested loops, where
i
iterates through rows from0
ton - 2
, andj
iterates through columns from0
ton - 2
. These ranges are chosen to ensure we can always extract a3 x 3
submatrix centered aroundgrid[i + 1][j + 1]
. - For each position
(i, j)
, extract the contiguous3 x 3
submatrix. This is done by another nested loop, or in this case, a list comprehension, that iterates through all possiblex
andy
coordinates in this submatrix, withx
ranging fromi
toi + 2
andy
ranging fromj
toj + 2
. - Calculate the maximum value within this
3 x 3
submatrix using themax()
function applied to the list comprehension, which iterates over the range ofx
andy
and accesses the values ingrid[x][y]
. - Assign this maximum value to the corresponding cell in
maxLocal[i][j]
.
By using a list comprehension within the nested loops to calculate the maximum, the implementation avoids the need for an explicit inner loop for exploring the 3 x 3
submatrix. This makes the code more concise and readable.
Additionally, the approach does not require any extra data structures aside from the maxLocal
matrix which is being filled in, indicating an in-place algorithm with no additional space complexity.
The final result will be the maxLocal
matrix, which now contains the largest number from every contiguous 3 x 3
submatrix of the original grid
.
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
The above code snippet corresponds to the entire algorithm discussed, simplified into a Python method definition within a Solution class.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have the following 4 x 4
grid:
9 9 8 1 5 7 5 1 7 8 6 2 4 3 2 0
We want to apply the algorithm to create a maxLocal
matrix with dimensions (4 - 2) x (4 - 2)
, which is 2 x 2
.
Here are the steps of the algorithm in action:
-
Start with
i=0
andj=0
. The3 x 3
submatrix is:9 9 8 5 7 5 7 8 6
The maximum value in this submatrix is
9
. So,maxLocal[0][0]
will be9
. -
Move to
i=0
andj=1
. The3 x 3
submatrix is:9 8 1 7 5 1 8 6 2
The maximum value in this submatrix is
9
. So,maxLocal[0][1]
will be9
. -
Next,
i=1
andj=0
. The3 x 3
submatrix is:5 7 5 7 8 6 4 3 2
The maximum value in this submatrix is
8
. So,maxLocal[1][0]
will be8
. -
Finally,
i=1
andj=1
. The3 x 3
submatrix is:7 5 1 8 6 2 3 2 0
The maximum value in this submatrix is
8
. So,maxLocal[1][1]
will be8
.
After filling all the cells in maxLocal
, we get the final matrix:
9 9 8 8
This 2x2
matrix represents the maximum values from each 3 x 3
sliding window within the original 4 x 4
grid.
Solution Implementation
1from typing import List
2
3class Solution:
4 def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
5 # Determining the size of the given grid.
6 grid_size = len(grid)
7
8 # Preparing the answer grid with the reduced size (n-2) since we are looking for
9 # 3x3 local grids and each local grid reduces the dimension by 2 on each axis.
10 largest_values_grid = [[0] * (grid_size - 2) for _ in range(grid_size - 2)]
11
12 # Iterating over each cell that will be the top-left corner of a 3x3 grid.
13 for row in range(grid_size - 2):
14 for col in range(grid_size - 2):
15
16 # Finding the largest value in the current 3x3 local grid.
17 largest_value = max(
18 grid[i][j] for i in range(row, row + 3) for j in range(col, col + 3)
19 )
20
21 # Storing the largest value found in the corresponding cell of the answer grid.
22 largest_values_grid[row][col] = largest_value
23
24 # Returning the answer grid containing all the largest values found in each 3x3 local grid.
25 return largest_values_grid
26
1class Solution {
2
3 // Method to find the largest element in every 3x3 subgrid
4 public int[][] largestLocal(int[][] grid) {
5 // Determine the size of the grid
6 int gridSize = grid.length;
7
8 // Initialize the answer grid with a reduced size
9 // because the border elements can't form a complete 3x3 subgrid
10 int[][] maxLocalValues = new int[gridSize - 2][gridSize - 2];
11
12 // Iterate through the grid, considering each 3x3 subgrid
13 for (int i = 0; i <= gridSize - 3; ++i) {
14 for (int j = 0; j <= gridSize - 3; ++j) {
15 // Initialize max value for the current 3x3 subgrid
16 int maxVal = Integer.MIN_VALUE;
17
18 // Nested loops to go through each element in the 3x3 subgrid
19 for (int x = i; x <= i + 2; ++x) {
20 for (int y = j; y <= j + 2; ++y) {
21 // Update maxVal if a larger value is found
22 maxVal = Math.max(maxVal, grid[x][y]);
23 }
24 }
25
26 // Assign the largest value in the 3x3 subgrid to the answer grid
27 maxLocalValues[i][j] = maxVal;
28 }
29 }
30 // Return the answer grid containing the largest values of each subgrid
31 return maxLocalValues;
32 }
33}
34
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
7 int size = grid.size(); // Get the size of the input grid.
8 // Initialize the result grid with dimensions (size - 2) x (size - 2) to accommodate the 3x3 window reduction.
9 vector<vector<int>> result(size - 2, vector<int>(size - 2));
10 // Loop through each cell where a 3x3 grid can start.
11 for (int row = 0; row < size - 2; ++row) {
12 for (int col = 0; col < size - 2; ++col) {
13 // Iterate through each cell within the current 3x3 window.
14 for (int localRow = row; localRow <= row + 2; ++localRow) {
15 for (int localCol = col; localCol <= col + 2; ++localCol) {
16 // Update the corresponding cell in the result grid with
17 // the maximum value seen so far in the 3x3 window.
18 result[row][col] = max(result[row][col], grid[localRow][localCol]);
19 }
20 }
21 }
22 }
23 // Return the populated result grid after processing the entire input grid.
24 return result;
25 }
26};
27
1function largestLocal(grid: number[][]): number[][] {
2 const gridSize = grid.length; // The size of the input grid
3 // Initialize the result grid with dimensions (gridSize - 2) x (gridSize - 2)
4 const resultGrid = Array.from({ length: gridSize - 2 }, () => new Array(gridSize - 2).fill(0));
5
6 // Iterate through the grid to fill the resultGrid with the maximum values from each local 3x3 grid
7 for (let row = 0; row < gridSize - 2; row++) {
8 for (let col = 0; col < gridSize - 2; col++) {
9 let localMax = 0; // The maximum value in the current 3x3 grid
10
11 // Iterate over the 3x3 grid starting at (row, col)
12 for (let k = row; k < row + 3; k++) {
13 for (let z = col; z < col + 3; z++) {
14 // Find the maximum value in the local 3x3 grid
15 localMax = Math.max(localMax, grid[k][z]);
16 }
17 }
18
19 // Assign the maximum value found to the corresponding position in resultGrid
20 resultGrid[row][col] = localMax;
21 }
22 }
23
24 // Return the result grid which contains the largest values found in each local 3x3 grid
25 return resultGrid;
26}
27
Time and Space Complexity
The provided code snippet is used to find the maximum local element in all 3x3 subgrids of a given 2D grid. Here is an analysis of its time and space complexity:
Time Complexity:
The time complexity of the code is determined by the nested loops and the operations within them. The outer two for
loops iterate over (n - 2) * (n - 2)
elements since we're examining 3x3 subgrids and thus can't include the last two columns and rows for starting points of our subgrids. For each element in the answer grid, we find the maximum value within the 3x3 subgrid, which involves iterating over 9 elements (3 rows by 3 columns).
Therefore, the time complexity is:
O((n-2)*(n-2)*9)
, which simplifies to O(n^2)
, assuming that the max operation within a constant-sized subgrid takes constant time.
Space Complexity:
The space complexity is determined by the additional space used by the algorithm, not including the input. In this case, weāre creating an output grid ans
of size (n - 2) * (n - 2)
to store the maxima of each 3x3 subgrid, which represents the additional space used.
Thus, the space complexity is:
O((n-2)*(n-2))
which simplifies to O(n^2)
as the size of the ans
grid grows quadratically with the input size n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!