Largest Local Values in a Matrix

🏠 ⬅️ ➡️

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.

Return the generated matrix.

Example 1:

Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]] Output: [[9,9],[8,6]] Explanation: The diagram above shows the original matrix and the generated matrix. Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

Example 2:

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 grid.

Constraints:

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
⚠️ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n, n) :: grid
    integer, dimension((n-2), (n-2)) :: maxLocal

    ! Example 1
    grid(:, :) = reshape([9, 9, 8, 1, &
                           5, 6, 2, 6, &
                           8, 2, 6, 4, &
                           6, 2, 2, 2], shape(grid))
    call solve(grid, maxLocal)
    write(*, '(A,*(I0, 1X))') 'Example 1:', maxLocal

    ! Example 2
    grid(:, :) = reshape([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], shape(grid))
    call solve(grid, maxLocal)
    write(*, '(A,*(I0, 1X))') 'Example 2:', maxLocal

contains

    subroutine solve(grid, maxLocal)
        implicit none
        integer, intent(in) :: grid(:, :)
        integer, intent(out) :: maxLocal(:, :)

        integer :: i, j, k, l
        integer :: maxValue

        do i = 2, n - 1
            do j = 2, n - 1
                maxValue = grid(i, j)
                do k = i - 1, i + 1
                    do l = j - 1, j + 1
                        if (grid(k, l) > maxValue) then
                            maxValue = grid(k, l)
                        end if
                    end do
                end do
                maxLocal(i - 1, j - 1) = maxValue
            end do
        end do

    end subroutine solve

end program main
✅ Compiled
✅ Executed
❌ Correct 
module max_local
    implicit none
    integer, parameter :: n = 4
    integer, parameter :: m = n - 2
    integer, parameter :: grid(n, n) = reshape([9, 9, 8, 1, 5, 6, 2, 6, 8, 2, 6, 4, 6, 2, 2, 2], [n, n])
    integer, parameter :: maxLocal(m, m) = reshape([9, 9, 8, 6, 8, 6, 6, 4], [m, m])
contains
    subroutine test_max_local()
        integer :: i, j
        do i = 1, m
            do j = 1, m
                if (maxLocal(i, j) /= max_value(grid, i + 1, j + 1)) then
                    write (*,*) "Error: maxLocal(", i, ", ", j, ") = ", maxLocal(i, j), " != ", max_value(grid, i + 1, j + 1)
                end if
            end do
        end do
    end subroutine test_max_local

    function max_value(grid, i, j) result(max)
        integer, intent(in) :: grid(n, n), i, j
        integer :: max
        integer :: local(3, 3)
        local = grid(i:i + 2, j:j + 2)
        max = maxval(local)
    end function max_value
end module max_local

program main
    use max_local
    implicit none
    call test_max_local()
end program main
🌐 Data from online sources 
def largest_matrix(grid):
    n = len(grid)
    maxLocal = [[0] * (n - 2) for _ in range(n - 2)]

    for i in range(1, n - 1):
        for j in range(1, n - 1):
            max_val = grid[i - 1][j - 1]
            for x in range(-1, 2):
                for y in range(-1, 2):
                    max_val = max(max_val, grid[i + x][j + y])
            maxLocal[i - 1][j - 1] = max_val

    return maxLocal

The algorithm iterates through each cell of the input grid, and for each cell, it considers the 3x3 submatrix centered around that cell. It finds the maximum value in that submatrix and saves it in the corresponding position in the maxLocal matrix. To obtain the largest value from the 3x3 submatrix, nested loops iterate through all positions of the submatrix, comparing the value of each position with a variable max_val, which is then updated with the largest value found. The generated maxLocal matrix is returned as the output.

🌐 Data from online sources 
#include <vector>

std::vector<std::vector<int>> largestMatrix(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    std::vector<std::vector<int>> maxLocal(n - 2, std::vector<int>(n - 2));

    for (int i = 1; i < n - 1; ++i) {
        for (int j = 1; j < n - 1; ++j) {
            int max_val = grid[i - 1][j - 1];
            for (int x = -1; x <= 1; ++x) {
                for (int y = -1; y <= 1; ++y) {
                    max_val = std::max(max_val, grid[i + x][j + y]);
                }
            }
            maxLocal[i - 1][j - 1] = max_val;
        }
    }

    return maxLocal;
}

The algorithm iterates through each cell of the input grid, and for each cell, it considers the 3x3 submatrix centered around that cell. It finds the maximum value in that submatrix and saves it in the corresponding position in the maxLocal matrix. To obtain the largest value from the 3x3 submatrix, nested loops iterate through all positions of the submatrix, comparing the value of each position with a variable max_val, which is then updated with the largest value found. The generated maxLocal matrix is returned as the output.