algoadvance

Leetcode 2373. Largest Local Values in a Matrix

Problem Statement

Given a grid of size n x n, a local value in a 3 x 3 block is defined as the maximum value in that 3 x 3 block. If there are multiple maximum values, any one may be chosen (since they are all equal).

You are tasked with finding the largest local values in each 3 x 3 block starting from the top-left of the grid. The result should be an (n-2) x (n-2) matrix where each element is the largest local value within the 3 x 3 block that starts from the same position in the original grid.

Example:

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

Output:
[[9,9],
 [8,6]]

Constraints:

• n == grid.length == grid[i].length
• 3 <= n <= 100
• 1 <= grid[i][j] <= 100

Clarifying Questions

1. Is it guaranteed that the input matrix will always be at least 3x3?
   • Yes, the constraints guarantee that.
2. Are there any constraints on the values inside the matrix?
   • Yes, the values inside the matrix are in the range from 1 to 100.

Strategy

1. Create an output matrix of size (n-2) x (n-2).
2. Iterate over each possible starting point of a 3 x 3 block in the input matrix.
3. For each 3 x 3 block, find the maximum value.
4. Store this maximum value in the corresponding cell of the output matrix.
5. Return the output matrix.

Code

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> result(n - 2, vector<int>(n - 2));
    
    for (int i = 0; i < n - 2; ++i) {
        for (int j = 0; j < n - 2; ++j) {
            int max_val = 0;
            for (int k = i; k < i + 3; ++k) {
                for (int l = j; l < j + 3; ++l) {
                    max_val = max(max_val, grid[k][l]);
                }
            }
            result[i][j] = max_val;
        }
    }
    
    return result;
}

Time Complexity

• Time Complexity: O(n^2)
  • Two nested loops iterate over the (n-2) x (n-2) grid, and within each iteration, another two nested loops iterate over the 3 x 3 block resulting in a constant time computation for each cell.
• Space Complexity: O(n^2)
  • The output matrix of size (n-2) x (n-2) is used, which takes up space proportional to the input size.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?