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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Local Values in a Matrix

Number: 2454

Difficulty: Easy

Paid? No

Companies: Google, Amazon

Problem Description

Given an n x n integer matrix grid, generate a (n - 2) x (n - 2) matrix maxLocal where each element maxLocal[i][j] is the largest value in the 3 x 3 submatrix centered at grid[i+1][j+1]. In other words, for every contiguous 3 x 3 block in grid, find the maximum value and store it in maxLocal at the corresponding position.

Key Insights

  • The size of the output matrix is (n - 2) x (n - 2).
  • For each valid index (i, j) in the output, examine the 3 x 3 block in grid starting at grid[i][j] to grid[i+2][j+2].
  • Since each 3 x 3 block contains exactly 9 elements, finding the maximum in a block takes constant time.
  • Use nested loops to slide over the grid and efficiently compute each local maximum.

Space and Time Complexity

Time Complexity: O(n^2) – We iterate over (n-2) x (n-2) positions, and for each position, we look at 9 elements. Space Complexity: O(n^2) – The additional space is required for the output matrix.

Solution

The solution involves iterating over each possible 3 x 3 submatrix in grid. For each (i, j) starting index of the submatrix:

  1. Examine the nine elements from grid[i][j] to grid[i+2][j+2].
  2. Compute the maximum value from these elements.
  3. Store the maximum in the corresponding position of the result matrix. Data structures used include the result matrix for storing the maximum values. The algorithmic approach involves two nested loops (one for rows and one for columns) to traverse each possible starting position of a 3 x 3 window. The simplicity of the solution comes from the fixed 3x3 block size, which enables constant-time maximum computation for each block.

Code Solutions

# Python solution for finding the largest local values in a matrix

def largestLocal(grid):
    n = len(grid)  # dimension of the grid
    # Initialize the result matrix with zeros, of size (n-2) x (n-2)
    result = [[0] * (n - 2) for _ in range(n - 2)]
    
    # Loop through each possible top-left index of a 3x3 submatrix
    for i in range(n - 2):
        for j in range(n - 2):
            # Compute the maximum in the current 3x3 submatrix
            local_max = 0  # since grid elements are >= 1, starting with 0 is safe
            for k in range(3):
                for l in range(3):
                    local_max = max(local_max, grid[i + k][j + l])
            # Store the local maximum in the result matrix
            result[i][j] = local_max
    return result

# Example usage:
grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
print(largestLocal(grid))
← Back to All Questions