We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Local Values in a Matrix

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires identifying the maximum value in overlapping 3 x 3 submatrices of a given n x n matrix.
  • The resulting matrix will have dimensions (n - 2) x (n - 2), as each 3 x 3 submatrix can be centered at positions from (1, 1) to (n-2, n-2).
  • A straightforward nested loop approach can be employed to scan through the matrix and capture the maximum values.

Space and Time Complexity

Time Complexity: O(n^2) - We iterate through the matrix, and for each valid position, we check 9 elements. Space Complexity: O(n^2) - We create an output matrix of size (n - 2) x (n - 2).

Solution

To solve the problem, we will use a nested loop approach that iterates through the grid matrix to find the maximum value in each 3 x 3 submatrix. For each starting position (i, j) in the grid, we will examine the values in the 3 x 3 area centered around (i + 1, j + 1). The results will be stored in a new matrix of size (n - 2) x (n - 2).

Code Solutions

def largestLocal(grid):
    n = len(grid)
    maxLocal = [[0] * (n - 2) for _ in range(n - 2)]
    
    for i in range(n - 2):
        for j in range(n - 2):
            maxLocal[i][j] = 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 maxLocal
← Back to All Questions