Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2373.html

2373. Largest Local Values in a Matrix

  • Difficulty: Easy.
  • Related Topics: Array, Matrix.
  • Similar Questions: .

Problem

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

Solution (Java, C++, Python)

  • class Solution {
        public int[][] largestLocal(int[][] grid) {
            int n = grid.length;
            int[][] res = new int[n - 2][n - 2];
            for (int i = 0; i < n - 2; i++) {
                for (int j = 0; j < n - 2; j++) {
                    for (int p = i; p < i + 3; p++) {
                        for (int q = j; q < j + 3; q++) {
                            res[i][j] = Math.max(res[i][j], grid[p][q]);
                        }
                    }
                }
            }
            return res;
        }
    }
    
    ############
    
    class Solution {
        public int[][] largestLocal(int[][] grid) {
            int n = grid.length;
            int[][] ans = new int[n - 2][n - 2];
            for (int i = 0; i < n - 2; ++i) {
                for (int j = 0; j < n - 2; ++j) {
                    for (int x = i; x <= i + 2; ++x) {
                        for (int y = j; y <= j + 2; ++y) {
                            ans[i][j] = Math.max(ans[i][j], grid[x][y]);
                        }
                    }
                }
            }
            return ans;
        }
    }
    
  • 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
    
    ############
    
    # 2373. Largest Local Values in a Matrix
    # https://leetcode.com/problems/largest-local-values-in-a-matrix/
    
    class Solution:
        def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
            n = len(grid)
            res = [[0] * (n - 2) for _ in range(n - 2)]
            
            for i in range(n - 2):
                for j in range(n - 2):
                    mmax = 0
                    for di in range(i, i + 3):
                        for dj in range(j, j + 3):
                            mmax = max(mmax, grid[di][dj])
                    
                    res[i][j] = mmax
            
            return res
            
    
    
  • class Solution {
    public:
        vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
            int n = grid.size();
            vector<vector<int>> ans(n - 2, vector<int>(n - 2));
            for (int i = 0; i < n - 2; ++i) {
                for (int j = 0; j < n - 2; ++j) {
                    for (int x = i; x <= i + 2; ++x) {
                        for (int y = j; y <= j + 2; ++y) {
                            ans[i][j] = max(ans[i][j], grid[x][y]);
                        }
                    }
                }
            }
            return ans;
        }
    };
    
  • func largestLocal(grid [][]int) [][]int {
    	n := len(grid)
    	ans := make([][]int, n-2)
    	for i := range ans {
    		ans[i] = make([]int, n-2)
    		for j := 0; j < n-2; j++ {
    			for x := i; x <= i+2; x++ {
    				for y := j; y <= j+2; y++ {
    					ans[i][j] = max(ans[i][j], grid[x][y])
    				}
    			}
    		}
    	}
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • function largestLocal(grid: number[][]): number[][] {
        const n = grid.length;
        const res = Array.from({ length: n - 2 }, () => new Array(n - 2).fill(0));
        for (let i = 0; i < n - 2; i++) {
            for (let j = 0; j < n - 2; j++) {
                let max = 0;
                for (let k = i; k < i + 3; k++) {
                    for (let z = j; z < j + 3; z++) {
                        max = Math.max(max, grid[k][z]);
                    }
                }
                res[i][j] = max;
            }
        }
        return res;
    }
    
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions