LeetCode 3933 - Largest Local Values in a Matrix II

The problem asks us to find local maximums in a 2D matrix according to a specialized neighborhood rule. Each cell in the matrix has a value x.

leetcodemediumarraymatrixprefix-sum

LeetCode Problem 3933

Difficulty: 🟡 Medium
Topics: Array, Matrix, Prefix Sum

Solution

Problem Understanding

The problem asks us to find local maximums in a 2D matrix according to a specialized neighborhood rule. Each cell in the matrix has a value x. A cell is a local maximum if it is non-zero and no neighboring cell within a distance of x in both row and column has a strictly greater value, except for the corners at distance exactly x in both row and column, which are ignored.

In other words, for a non-zero cell (i, j) with value x, we consider all cells (r, c) such that |r - i| <= x and |c - j| <= x, excluding cells where both |r - i| == x and |c - j| == x. The cell is a local maximum if none of these considered cells contain a value larger than x.

The input is a matrix of size n x m with values from 0 to 200. Constraints ensure that n and m can go up to 200, which makes a brute-force approach feasible but potentially slow if implemented naively. Edge cases include cells with value 0 (ignored), cells at the boundary, and cells where the maximum neighborhood extends outside the matrix.

Important observations include that every cell only needs to compare against its relevant neighborhood, and ignoring the corners simplifies the comparison slightly. Non-zero checks are crucial because zero cells are never local maximums.

Approaches

The brute-force approach iterates over every cell in the matrix. For each non-zero cell (i, j), it computes x = matrix[i][j] and iterates over all cells in the x x x neighborhood, skipping corners at distance x. If no cell in the neighborhood has a value greater than x, the cell is counted as a local maximum. This guarantees correctness but can be slow when x is large because we potentially examine O(x^2) cells for each non-zero cell. In the worst case, this can approach O(n * m * max(n, m)^2) operations.

The optimal approach uses the fact that the maximum distance x is at most 200, and the matrix is bounded. We can still use brute-force because the total number of operations remains manageable for a 200 x 200 matrix, but we can optimize by avoiding redundant comparisons and by clipping the neighborhood to the matrix boundaries. We iterate only over valid row and column ranges, reducing unnecessary iterations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * x^2) worst case O(1) Checks every neighbor explicitly, skips corners
Optimized Neighborhood Scan O(n * m * x^2) worst case O(1) Bounds neighborhood to valid indices, slightly faster practically

In this problem, the brute-force approach with proper bounds checking is efficient enough due to small constraints, so we will implement that as the optimal solution.

Algorithm Walkthrough

  1. Initialize a counter count to 0. This will track the number of local maximums.
  2. Iterate over each cell (i, j) in the matrix. Skip the cell if matrix[i][j] == 0.
  3. Let x = matrix[i][j]. Compute the valid row range as max(0, i - x) to min(n - 1, i + x) and the valid column range as max(0, j - x) to min(m - 1, j + x).
  4. Initialize a flag isLocalMax to True.
  5. Iterate over all (r, c) in the computed ranges. Skip cells where both |r - i| == x and |c - j| == x.
  6. If matrix[r][c] > x, set isLocalMax = False and break out of the loops.
  7. After scanning the neighborhood, if isLocalMax is True, increment count by 1.
  8. Return count after processing all cells.

Why it works: This algorithm correctly checks each non-zero cell against its defined neighborhood, respecting the exclusion rule for corner cells. By bounding the indices to valid matrix positions, it avoids out-of-range errors and correctly counts local maximums.

Python Solution

class Solution:
    def countLocalMaximums(self, matrix: list[list[int]]) -> int:
        n, m = len(matrix), len(matrix[0])
        count = 0
        
        for i in range(n):
            for j in range(m):
                x = matrix[i][j]
                if x == 0:
                    continue
                isLocalMax = True
                row_start = max(0, i - x)
                row_end = min(n - 1, i + x)
                col_start = max(0, j - x)
                col_end = min(m - 1, j + x)
                
                for r in range(row_start, row_end + 1):
                    for c in range(col_start, col_end + 1):
                        if abs(r - i) == x and abs(c - j) == x:
                            continue
                        if matrix[r][c] > x:
                            isLocalMax = False
                            break
                    if not isLocalMax:
                        break
                
                if isLocalMax:
                    count += 1
        return count

The Python implementation follows the algorithm exactly. It computes the bounds for each neighborhood dynamically, skips corners, and breaks early if a larger value is found. The nested loops ensure all relevant neighbors are considered efficiently.

Go Solution

func countLocalMaximums(matrix [][]int) int {
    n, m := len(matrix), len(matrix[0])
    count := 0
    
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            x := matrix[i][j]
            if x == 0 {
                continue
            }
            isLocalMax := true
            rowStart := max(0, i - x)
            rowEnd := min(n-1, i + x)
            colStart := max(0, j - x)
            colEnd := min(m-1, j + x)
            
            for r := rowStart; r <= rowEnd; r++ {
                for c := colStart; c <= colEnd; c++ {
                    if abs(r - i) == x && abs(c - j) == x {
                        continue
                    }
                    if matrix[r][c] > x {
                        isLocalMax = false
                        break
                    }
                }
                if !isLocalMax {
                    break
                }
            }
            
            if isLocalMax {
                count++
            }
        }
    }
    return count
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

In Go, helper functions max, min, and abs are used since the standard library lacks generic min/max for integers. The logic mirrors Python closely.

Worked Examples

Example 1: matrix = [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,2,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]

  • Only cell (3,3) is non-zero with x = 2.
  • Row range: 1 to 5, Column range: 1 to 5.
  • Ignore corners (1,1), (1,5), (5,1), (5,5).
  • No other cell > 2, so count = 1.

Example 2: matrix = [[1,2],[3,4]]

  • Only cell (1,1) with value 4 has no neighbors greater than 4. Count = 1.

Example 3: matrix = [[1,0,1],[0,1,0],[1,0,1]]

  • All cells with 1 consider only neighbors with values ≤ 1. Count = 5.

Example 4: matrix = [[1,1],[1,1]]

  • Every cell is a local maximum. Count = 4.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m * x^2) worst case Each cell examines a neighborhood of size up to (2x+1)^2.
Space O(1) Only constant variables used for counting and iteration.

Even in the worst case of 200 x 200 matrix and x = 200, the algorithm performs about 64 million operations, which is acceptable for modern computers.

Test Cases

# Provided examples
assert Solution().countLocalMaximums([[0,0,0,0,0,0,0],[0,0,0,