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]3 x 3matrix inmati + 1and columnj + 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