Largest Local Values in a Matrix - Practice Coding Problems

Largest Local Values in a Matrix - Problem

Array Matrix Easy

You are given an n x n integer matrix grid.

Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:

maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.

In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.

Return the generated matrix.

Input & Output

Example 1 — Basic 4x4 Grid

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

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

💡 Note: For position (0,0): 3x3 window has max value 9. For position (0,1): 3x3 window has max value 9. For position (1,0): 3x3 window has max value 8. For position (1,1): 3x3 window has max value 6.

Example 2 — Minimum 3x3 Grid

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: [[1]]

💡 Note: Only one 3x3 window possible, and the maximum value in all 1s is 1.

Example 3 — Larger Grid with Negatives

$ Input: grid = [[-1,2,-3],[4,-5,6],[-7,8,-9]]

› Output: [[8]]

💡 Note: The single 3x3 window contains all elements, and the maximum is 8.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

4x4 matrix with integer values

Extract Windows

Find all possible 3x3 submatrices

Find Maximums

Calculate maximum for each 3x3 window

Key Takeaway

🎯 Key Insight: The problem is essentially applying a 3x3 maximum filter to the matrix, reducing dimensions by 2 in each direction

Asked in

G Google 45 a Amazon 35 M Microsoft 28 A Apple 22

The key insight is that each output position corresponds to the maximum value in a 3x3 sliding window. Best approach is the brute force iteration which directly checks each 3x3 window. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All 3x3 Windows	O(n²)	O(1)	Iterate through each possible 3x3 window and find the maximum value
Optimized Single Pass	O(n²)	O(1)	Direct iteration with inline maximum calculation for each 3x3 window

Brute Force - Check All 3x3 Windows — Algorithm Steps

Step 1: Iterate through each valid top-left corner of 3x3 windows
Step 2: For each window, check all 9 cells to find the maximum
Step 3: Store the maximum in the result matrix

Visualization

Tap to expand

Step-by-Step Walkthrough

Position (0,0)

Check 3x3 window at top-left

Position (0,1)

Move window right and check again

Continue

Repeat for all valid positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int** solution(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    int n = gridSize;
    *returnSize = n - 2;
    *returnColumnSizes = (int*)malloc((*returnSize) * sizeof(int));
    
    int** result = (int**)malloc((*returnSize) * sizeof(int*));
    
    for (int i = 0; i < n - 2; i++) {
        (*returnColumnSizes)[i] = n - 2;
        result[i] = (int*)malloc((n - 2) * sizeof(int));
        
        for (int j = 0; j < n - 2; j++) {
            int maxVal = INT_MIN;
            // Check 3x3 window starting at (i, j)
            for (int di = 0; di < 3; di++) {
                for (int dj = 0; dj < 3; dj++) {
                    if (grid[i + di][j + dj] > maxVal) {
                        maxVal = grid[i + di][j + dj];
                    }
                }
            }
            result[i][j] = maxVal;
        }
    }
    
    return result;
}

int main() {
    // For simplicity, assuming input format and parsing
    // This is a simplified version for the algorithm demonstration
    int grid[4][4] = {{9,9,8,1},{5,6,2,6},{8,2,6,4},{6,2,2,2}};
    int* gridPtr[4];
    int gridColSize[4] = {4,4,4,4};
    
    for (int i = 0; i < 4; i++) {
        gridPtr[i] = grid[i];
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(gridPtr, 4, gridColSize, &returnSize, &returnColumnSizes);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We iterate through (n-2)×(n-2) positions, checking 9 cells each, but since 9 is constant, it's O(n²)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables, result matrix doesn't count as extra space

✓ Linear Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All 3x3 Windows — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler