Menu Close

Leetcode 2373: Largest Local Values in a Matrix solution

Here, we will help you to understand how to solve Largest Local Values in a Matrix of leet code 2373 problem.

You are given an m x m integer matrix mat. You will have to generate another matrix lets say result_mat of size (m - 2) * (m - 2) out of given matrix such that:

  • result_mat[i][j] is equal to the largest value of the 3 x 3 matrix in mat centered around row i + 1 and column j + 1

In layman terms, you will have to find out largest value in every contiguous 3 x 3 matrix in mat.

Example 1:

Input:

9 9 6 1
5 6 2 6
8 2 6 4
6 2 2 2

Output:

9 9
8 6

Example 2:

Input:

1 1 1 1 1
1 1 1 1 1
1 1 4 1 1
1 1 1 1 1
1 1 1 1 1

Output:

4 4 4
4 4 4
4 4 4

Algorithm:

  • Iterate over each row and column in matrix of (m – 2) times respectively.
  • In each iteration, find out max value.
  • Store max value to an 2-D array.
  • Return the 2-D array.

Solution 1:

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
    vector<vector<int>> vv;
    vector<int> v;

    int row = grid.size();
    int col = grid[0].size();

    for(int i = 0; i < row && (row - i >= 3); i++) {
        for(int j = 0; j < col && (col - j >= 3) ; j++) {
    
            int max = INT_MIN;
            for(int x = i; x < i+3; x++) {
                for(int y = j; y < j + 3; y++) {
                    if(max < grid[x][y]) {
                        max = grid[x][y];
                    }
                }
            }
            v.push_back(max);
        }
        vv.push_back(v);
        v.clear();
    }
    return vv;
}

int main()
{
    vector<vector<int>> vv = {
        {9, 9, 8, 1},
        {5, 6, 2, 6},
        {8, 2, 6, 4},
        {6, 2, 2, 2}
    };
    
    vector<vector<int>> result = largestLocal(vv);
    
    for(auto it : result) {
        for(auto num : it) {
            cout<<num<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

Solution 2:

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int m(vector<vector<int>>& mat, int row, int col) {
    int ret = 0;
    ret = max(ret, mat[row][col]);
    ret = max(ret, mat[row][col + 1]);
    ret = max(ret, mat[row][col + 2]);
    ret = max(ret, mat[row + 1][col]);
    ret = max(ret, mat[row + 1][col + 1]);
    ret = max(ret, mat[row + 1][col + 2]);
    ret = max(ret, mat[row + 2][col]);
    ret = max(ret, mat[row + 2][col + 1]);
    ret = max(ret, mat[row + 2][col + 2]);
    return ret;
}

vector<vector<int>> largestLocal(vector<vector<int>>& mat) {
    int n = mat.size();
    vector<vector<int>> ret(n - 2, vector<int>(n - 2));
        
    for (int i = 0; i < n - 2; ++i) {
        for (int j = 0; j < n - 2; ++j) {
            ret[i][j] = m(mat, i, j);
        }
    }
    return ret;
}

int main()
{
    vector<vector<int>> vv = {
        {9, 9, 8, 1},
        {5, 6, 2, 6},
        {8, 2, 6, 4},
        {6, 2, 2, 2}
    };
    
    vector<vector<int>> result = largestLocal(vv);
    
    for(auto it : result) {
        for(auto num : it) {
            cout<<num<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

Output:

9 9
8 6

To learn more about C++ pls refer given below link:

References:

https://www.cplusplus.com/reference/vector/vector/?kw=vector

Posted in C++, Leetcode

Leave a Reply

Your email address will not be published. Required fields are marked *