Largest Local Values in a Matrix

Easy
299.

Largest Local Values in a Matrix

Largest Local Values in a Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.

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 <= 8
  • grid[i].length == grid.length
  • 1 <= grid[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var largestLocal = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 8
  • grid[i].length == grid.length
  • 1 <= grid[i][j] <= 100

Hints for Largest Local Values in a Matrix

  1. Hint 1

    The output has two fewer rows and columns, because the block centre can never sit on the border.

  2. 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

  1. For i, j in 0 .. n - 3, compute max(grid[i+dr][j+dc]) over dr, 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