How do you solve Modify the Matrix on LeetCode?

Modify the Matrix (LeetCode #3033) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a separate array to store maximum values reduces redundant calculations.

What is the brute force solution for Modify the Matrix?

The brute force approach for Modify the Matrix is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves iterating through each element of the matrix. For every element that is -1, we will find the maximum value in its column and replace -1 with that maximum value. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Modify the Matrix?

Modify the Matrix uses the following concepts: Array, Matrix. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Modify the Matrix?

Always clarify the problem statement before jumping into coding. Think about edge cases and how your solution handles them. Discuss your thought process with the interviewer to showcase your understanding.

What are common mistakes when solving Modify the Matrix?

Not initializing the max array correctly. Forgetting to handle cases where all elements in a column are -1.

#3033

Modify the Matrix

Easy

ArrayMatrixHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution first computes the maximum values for each column in a single pass, then modifies the matrix in a second pass. This reduces the number of times we need to traverse the matrix.

⚙️

Algorithm

3 steps

1Step 1: Create an array to store the maximum values of each column.
2Step 2: Traverse the matrix once to fill the maximum values for each column.
3Step 3: Traverse the matrix again to replace -1 with the corresponding maximum value from the array.

solution.py17 lines

1# Full working Python code
2matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
3m, n = len(matrix), len(matrix[0])
4max_cols = [float('-inf')] * n
5
6for j in range(n):
7    for i in range(m):
8        if matrix[i][j] != -1:
9            max_cols[j] = max(max_cols[j], matrix[i][j])
10
11answer = [row[:] for row in matrix]
12for j in range(n):
13    for i in range(m):
14        if matrix[i][j] == -1:
15            answer[i][j] = max_cols[j]
16
17print(answer)

ℹ

Complexity note: The time complexity is O(n) because we only traverse the matrix twice: once to find the maximum values and once to replace -1s. The space complexity is O(n) for the array that stores the maximum values of each column.

1Using a separate array to store maximum values reduces redundant calculations.
2Two passes through the matrix optimize the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.