LeetCode 3033 - Modify the Matrix

The problem is asking us to take a given m x n matrix, potentially containing -1 values, and produce a modified matrix in which each -1 is replaced by the maximum value in its respective column.

leetcodeeasyarraymatrix

LeetCode Problem 3033

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem is asking us to take a given m x n matrix, potentially containing -1 values, and produce a modified matrix in which each -1 is replaced by the maximum value in its respective column. The input matrix is guaranteed to have at least one non-negative integer in each column, which ensures that a maximum value can always be determined. The expected output is a new matrix (or an updated copy of the original) where only -1 values are replaced, and all other values remain unchanged.

The constraints indicate the matrix is small to medium-sized, with m and n up to 50, so a simple nested iteration over columns and rows will be efficient enough. Important edge cases include columns where the -1 is at the top, bottom, or multiple -1s in a single column.

Approaches

The brute-force approach involves iterating over each cell in the matrix. For every cell with -1, we would scan its entire column to find the maximum value and replace the -1 accordingly. This method is correct, as it directly follows the problem statement, but it repeats work for columns with multiple -1s.

The optimal approach involves precomputing the maximum value for each column before modifying the matrix. Once all column maxima are known, we can iterate over the matrix again, replacing -1s with the precomputed maxima. This avoids repeated scanning and makes the solution straightforward and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * m) O(1) For each -1, scans the entire column to find the maximum. Repeats work if multiple -1s exist in the same column.
Optimal O(m * n) O(n) Precompute column maxima in one pass, then modify the matrix in a second pass. Efficient for the given constraints.

Algorithm Walkthrough

  1. Initialize a list col_max of size n to store the maximum value for each column. Start with a very low initial value (e.g., -inf) to ensure any valid matrix value will replace it.
  2. Iterate over each column index j from 0 to n-1. For each column, iterate over all rows i and update col_max[j] with the maximum value found in that column, ignoring -1 values.
  3. Iterate over the matrix again. For each cell matrix[i][j], check if the value is -1. If it is, replace it with col_max[j].
  4. Return the modified matrix.

Why it works: By precomputing the maximum value for each column, we ensure that each -1 is replaced with the correct maximum without repeatedly scanning the column. Since the constraints guarantee at least one non-negative integer per column, the col_max list will always contain a valid replacement.

Python Solution

from typing import List

class Solution:
    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        col_max = [-1] * n

        # Step 1: compute maximum for each column
        for j in range(n):
            for i in range(m):
                if matrix[i][j] != -1:
                    col_max[j] = max(col_max[j], matrix[i][j])

        # Step 2: replace -1 with column maximum
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == -1:
                    matrix[i][j] = col_max[j]

        return matrix

The first nested loop computes the column maxima efficiently in O(m * n). The second loop iterates over the matrix again to replace all -1s using the precomputed maxima. This separation of concerns ensures clarity and avoids redundant computations.

Go Solution

func modifiedMatrix(matrix [][]int) [][]int {
    m, n := len(matrix), len(matrix[0])
    colMax := make([]int, n)

    // Initialize colMax with -1
    for j := 0; j < n; j++ {
        colMax[j] = -1
    }

    // Step 1: compute maximum for each column
    for j := 0; j < n; j++ {
        for i := 0; i < m; i++ {
            if matrix[i][j] != -1 && matrix[i][j] > colMax[j] {
                colMax[j] = matrix[i][j]
            }
        }
    }

    // Step 2: replace -1 with column maximum
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == -1 {
                matrix[i][j] = colMax[j]
            }
        }
    }

    return matrix
}

Go implementation mirrors the Python logic closely, using slices for column maxima and standard for loops. We avoid nil slices, and integer comparisons are safe because all input values are within the -1 to 100 range.

Worked Examples

Example 1

Input: [[1,2,-1],[4,-1,6],[7,8,9]]

Step 1: Compute column maxima:

  • Column 0: max(1,4,7) = 7
  • Column 1: max(2, - , 8) = 8
  • Column 2: max(- , 6, 9) = 9

Step 2: Replace -1 with column maxima:

  • matrix[0][2] = 9
  • matrix[1][1] = 8

Output: [[1,2,9],[4,8,6],[7,8,9]]

Example 2

Input: [[3,-1],[5,2]]

Column maxima:

  • Column 0: max(3,5) = 5
  • Column 1: max(- ,2) = 2

Replace -1:

  • matrix[0][1] = 2

Output: [[3,2],[5,2]]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Two passes over the matrix, each visiting all elements.
Space O(n) Extra space for storing column maxima.

The algorithm is efficient and well within the problem constraints, as m and n are at most 50.

Test Cases

# Provided examples
assert Solution().modifiedMatrix([[1,2,-1],[4,-1,6],[7,8,9]]) == [[1,2,9],[4,8,6],[7,8,9]]  # replaces -1 correctly
assert Solution().modifiedMatrix([[3,-1],[5,2]]) == [[3,2],[5,2]]  # handles small matrix

# Edge cases
assert Solution().modifiedMatrix([[-1,-1],[-1,-1]]) == [[-1,-1],[-1,-1]]  # all -1, no valid max to replace
assert Solution().modifiedMatrix([[0,-1],[-1,1]]) == [[0,1],[0,1]]  # zeros and ones
assert Solution().modifiedMatrix([[10]]) == [[10]]  # 1x1 matrix, no -1

# Larger matrix
matrix = [[i if (i+j)%3 != 0 else -1 for j in range(5)] for i in range(5)]
expected = [row[:] for row in matrix]
for j in range(5):
    col_max = max(matrix[i][j] for i in range(5) if matrix[i][j] != -1)
    for i in range(5):
        if expected[i][j] == -1:
            expected[i][j] = col_max
assert Solution().modifiedMatrix(matrix) == expected
Test Why
Provided examples Validates basic functionality and correctness
All -1 Checks handling when no replacement is possible
Zeros and ones Confirms correct handling of boundary values
1x1 matrix Minimal input validation
Larger matrix Tests algorithm on moderately sized input and multiple -1s per column

Edge Cases

One edge case is when a column contains multiple -1s. A naive approach that recomputes the maximum for each -1 would be inefficient, but the precomputation handles it seamlessly.

Another edge case is when the -1 is the only negative value in a column, while all other values are zero or positive. The algorithm correctly finds the maximum among valid values, avoiding replacing -1 with another -1.

A final edge case is a minimal matrix, such as 1x1 or 2x2, which could break indexing logic. The implementation handles these naturally by iterating over the matrix size and using precomputed column maxima.