algoadvance

Leetcode 2373. Largest Local Values in a Matrix

Problem Statement

You are given an n x n integer matrix grid. Generate an n-2 x n-2 matrix result such that:

Example:

Input: grid = [[9,9,8,1],
               [5,6,2,6],
               [8,2,6,4],
               [6,2,2,2]]
Output: [[9,9],
         [8,6]]

Clarifying Questions

  1. What are the constraints on the size of the grid?
    • Typically, we would expect constraints like 3 <= n <= 100. This ensures the grid is large enough to form at least one 3x3 matrix.
  2. What are the possible ranges for the elements in the grid?
    • Usually, the elements can range from -10^5 to 10^5.
  3. Should we consider any specific data type to handle large numbers?
    • No, in Java, the default int can handle the range specified.

Strategy

  1. Iterate through the sub-matrices:
    • We’ll iterate through the grid such that at each point [i][j], we consider the 3x3 matrix centered around [i+1][j+1].
  2. Find the max value for each sub-matrix:
    • For each 3x3 matrix, compute the maximum value.
  3. Store the computed max value into the result matrix:
    • The resulting matrix is n-2 x n-2 in size.

Code

public class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] result = new int[n - 2][n - 2];
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                result[i][j] = getMaxFrom3x3(grid, i, j);
            }
        }
        
        return result;
    }
    
    private int getMaxFrom3x3(int[][] grid, int row, int col) {
        int max = Integer.MIN_VALUE;
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if (grid[i][j] > max) {
                    max = grid[i][j];
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
            {9, 9, 8, 1},
            {5, 6, 2, 6},
            {8, 2, 6, 4},
            {6, 2, 2, 2}
        };
        int[][] result = solution.largestLocal(grid);
        
        for (int[] row : result) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }
}

Time Complexity

Therefore, the overall time complexity is O((n-2)^2).

This approach is efficient given the problem constraints and should perform well within typical input size limits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI