Largest Local Values in a Matrix — Problem & Solution
Largest Local Values in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Largest Local Values in a Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an n × n integer matrix grid.
Return an (n - 2) × (n - 2) matrix maxLocal where maxLocal[i][j] is the largest value in the 3 × 3 block of grid centred at row i + 1, column j + 1.
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]]
Example 2
Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: [[1]]
Example 3
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[9]]
Constraints
3 <= grid.length <= 8grid[i].length == grid.length1 <= grid[i][j] <= 100
Hints for Largest Local Values in a Matrix
Hint 1
The output has two fewer rows and columns, because the block centre can never sit on the border.
Hint 2
Anchor each block at its top-left corner
(i, j)and take the maximum of the nine cells from there.
How to solve Largest Local Values in a Matrix
Anchor each 3 × 3 block at its top-left corner (i, j) and take the maximum of its nine cells.
Approach
- For
i, jin0 .. n - 3, computemax(grid[i+dr][j+dc])overdr, dc ∈ {0, 1, 2}.
Why it works
The block centred at (i+1, j+1) spans rows i..i+2 and columns j..j+2, and centres cannot lie on the border, giving an (n-2) × (n-2) output.
Complexity
- Time —
O(n²) - Space —
O(n²) for the output
Pitfalls
- Nothing more clever is needed at this size; a sliding-max would matter only for large blocks.
Reference solution
Python
def largestLocal(grid):
n = len(grid)
return [[max(grid[r + dr][c + dc] for dr in range(3) for dc in range(3))
for c in range(n - 2)] for r in range(n - 2)]Java
public static int[][] largestLocal(int[][] grid) {
int n = grid.length;
int[][] out = new int[n - 2][n - 2];
for (int r = 0; r < n - 2; r++) {
for (int c = 0; c < n - 2; c++) {
int best = 0;
for (int dr = 0; dr < 3; dr++) {
for (int dc = 0; dc < 3; dc++) {
if (grid[r + dr][c + dc] > best) best = grid[r + dr][c + dc];
}
}
out[r][c] = best;
}
}
return out;
}C++
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n = (int) grid.size();
vector<vector<int>> out(n - 2, vector<int>(n - 2, 0));
for (int r = 0; r < n - 2; r++) {
for (int c = 0; c < n - 2; c++) {
int best = 0;
for (int dr = 0; dr < 3; dr++) {
for (int dc = 0; dc < 3; dc++) {
best = max(best, grid[r + dr][c + dc]);
}
}
out[r][c] = best;
}
}
return out;
}JavaScript
var largestLocal = function(grid) {
const n = grid.length;
const out = [];
for (let r = 0; r < n - 2; r++) {
const row = [];
for (let c = 0; c < n - 2; c++) {
let best = 0;
for (let dr = 0; dr < 3; dr++) {
for (let dc = 0; dc < 3; dc++) {
if (grid[r + dr][c + dc] > best) best = grid[r + dr][c + dc];
}
}
row.push(best);
}
out.push(row);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal