3033. Modify the Matrix
Problem Description
Given a two-dimensional grid, 'matrix', with m rows and n columns, we are asked to create an identical grid, 'answer'. The task involves identifying elements in 'matrix' with a value of -1 and updating them to the maximum value found in their respective columns. It's important to keep in mind that our grids are 0-indexed, meaning that row and column indices start from 0. The goal is to process 'matrix' and transform it into 'answer' following this rule, ultimately returning 'answer'.
Intuition
The solution revolves around handling the grid column by column. For each column, we look for the highest number (disregarding any -1 values, since we're only interested in positive numbers for replacement). After finding this maximum value, we proceed down the same column, substituting any instance of -1 with the column's maximum value we previously found.
The process can be split into two main steps:
-
Traverse each column of the matrix to determine the maximum non-negative value present in that column.
-
Go through the matrix again, this time replacing every -1 with the maximum value found in step 1 for the respective column.
We perform this for every column, and once all substitutions are made, we have our 'answer' matrix ready to be returned. The approach is direct and mimics the exact procedure described in the problem, requiring no additional data structures or complicated logic—simple iteration and replacement suffice to solve this problem.
Solution Approach
The algorithm implemented in the provided solution is straightforward and efficient. It employs a nested loop structure to process the matrix column by column.
Here's the step-by-step breakdown of the algorithm:
-
Determine the size of the matrix using the
'len'
function to findm
(number of rows) andn
(number of columns). -
Use an outer loop to iterate through each column index from
0
ton - 1
. -
Inside the outer loop, perform a list comprehension to determine the maximum value
mx
in the current column. This is done by iterating over each rowi
for the current columnj
and collecting each element's value, except for-1
. Themax
function then gives the highest value in that column.- This is achieved with the expression:
max(matrix[i][j] for i in range(m))
- This is achieved with the expression:
-
After finding the maximum value for the column, we use another inner loop to go through each row for the same column.
-
Here we check if any element is
-1
and replace it with the maximum valuemx
found earlier.- The replacement is done only when the condition
if matrix[i][j] == -1:
is true.
- The replacement is done only when the condition
-
Once all the columns have been processed, the original
matrix
is now modified to theanswer
matrix with all-1
s replaced by their respective column maximums. -
Lastly, return the modified
matrix
as the result.
No additional data structures or complex patterns are used in this implementation; it utilizes only basic loops and list comprehension techniques. The space complexity is constant, as we're simply updating the original matrix in place, without using any extra space proportional to the size of the input (beyond the fixed number of variables needed for iteration).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have the following grid matrix
, consisting of 3 rows and 4 columns:
1matrix = [ 2 [0, -1, 3, 4], 3 [3, 2, 1, -1], 4 [-1, 2, -1, 0] 5]
Following the steps of the solution approach:
-
Determine the size of the matrix. We can see that
m
is 3 andn
is 4. -
Start with the first column (
j=0
). We iterate through each row and find that the maximum value for this column is 3 (ignoring the -1). -
Replace all
-1
values in this column with the maximum value found. There is one-1
value in the third row, so we get:1matrix = [ 2 [0, -1, 3, 4], 3 [3, 2, 1, -1], 4 [3, 2, -1, 0] 5]
-
Move to the second column (
j=1
). The maximum value for this column is 2. -
Replace
-1
values in this column. There is one-1
in the first row, resulting in:1matrix = [ 2 [0, 2, 3, 4], 3 [3, 2, 1, -1], 4 [3, 2, -1, 0] 5]
-
Continue to the third column (
j=2
). The maximum value, ignoring -1, is 3. -
Replace
-1
values in the third column. There is one-1
in the third row, leading to:1matrix = [ 2 [0, 2, 3, 4], 3 [3, 2, 1, -1], 4 [3, 2, 3, 0] 5]
-
Finally, proceed to the last column (
j=3
). The maximum value is 4. -
There's one
-1
in the second row that needs to be replaced:1matrix = [ 2 [0, 2, 3, 4], 3 [3, 2, 1, 4], 4 [3, 2, 3, 0] 5]
After completing these steps, matrix
is now transformed into answer
by replacing all -1
values with the maximum values in their respective columns. The resulting matrix is:
1answer = [ 2 [0, 2, 3, 4], 3 [3, 2, 1, 4], 4 [3, 2, 3, 0] 5]
This matrix is then returned as the final output of the algorithm. The approach ensures that each -1 in the original matrix is replaced by the maximum positive value present in its respective column.
Solution Implementation
1from typing import List
2
3class Solution:
4 def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
5 # Get the number of rows (m) and columns (n) in the matrix
6 num_rows, num_columns = len(matrix), len(matrix[0])
7
8 # Iterate over each column
9 for col in range(num_columns):
10 # Find the maximum value in the current column
11 max_value = max(matrix[row][col] for row in range(num_rows))
12
13 # Replace all occurrences of -1 with the maximum value in the current column
14 for row in range(num_rows):
15 if matrix[row][col] == -1:
16 matrix[row][col] = max_value
17
18 # Return the modified matrix
19 return matrix
20
1class Solution {
2
3 /**
4 * Modifies a given matrix such that every -1 entry in a column is replaced with
5 * the maximum value in that column.
6 *
7 * @param matrix The original matrix that will be modified.
8 * @return The modified matrix.
9 */
10 public int[][] modifiedMatrix(int[][] matrix) {
11 // Get the number of rows m and the number of columns n in the matrix
12 int rowCount = matrix.length;
13 int columnCount = matrix[0].length;
14
15 // Iterate over columns
16 for (int column = 0; column < columnCount; ++column) {
17 // Initialize the maximum value for the current column, starting with the smallest possible integer value
18 int maxInColumn = Integer.MIN_VALUE;
19 // Find the maximum value in the current column
20 for (int row = 0; row < rowCount; ++row) {
21 maxInColumn = Math.max(maxInColumn, matrix[row][column]);
22 }
23 // Replace all -1 entries in the current column with the maximum value found
24 for (int row = 0; row < rowCount; ++row) {
25 if (matrix[row][column] == -1) {
26 matrix[row][column] = maxInColumn;
27 }
28 }
29 }
30 // Return the modified matrix
31 return matrix;
32 }
33}
34
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // The function modifiedMatrix takes a 2D vector of integers, representing a matrix,
7 // and modifies it according to certain rules.
8 std::vector<std::vector<int>> modifiedMatrix(std::vector<std::vector<int>>& matrix) {
9 // Get the number of rows and columns in the matrix.
10 int rowCount = matrix.size();
11 int colCount = matrix[0].size();
12
13 // Iterate over columns
14 for (int col = 0; col < colCount; ++col) {
15 // Initialize 'maxValue' to the smallest possible integer to find the maximum later.
16 int maxValue = std::numeric_limits<int>::min();
17
18 // Find the maximum value in the current column.
19 for (int row = 0; row < rowCount; ++row) {
20 maxValue = std::max(maxValue, matrix[row][col]);
21 }
22
23 // Replace all -1s in the current column with the maximum value found.
24 for (int row = 0; row < rowCount; ++row) {
25 if (matrix[row][col] == -1) {
26 matrix[row][col] = maxValue;
27 }
28 }
29 }
30
31 // Return the modified matrix.
32 return matrix;
33 }
34};
35
1function modifiedMatrix(matrix: number[][]): number[][] {
2 // Get the number of rows (m) and columns (n) from the matrix.
3 const numberOfRows = matrix.length;
4 const numberOfColumns = matrix[0].length;
5
6 // Iterate over each column.
7 for (let columnIndex = 0; columnIndex < numberOfColumns; ++columnIndex) {
8 // Initialize maximum value in the column as the smallest possible number.
9 let maximumInColumn = -1;
10
11 // Find the maximum value in the current column.
12 for (let rowIndex = 0; rowIndex < numberOfRows; ++rowIndex) {
13 maximumInColumn = Math.max(maximumInColumn, matrix[rowIndex][columnIndex]);
14 }
15
16 // Replace all -1s in the current column with the maximum value found.
17 for (let rowIndex = 0; rowIndex < numberOfRows; ++rowIndex) {
18 if (matrix[rowIndex][columnIndex] === -1) {
19 matrix[rowIndex][columnIndex] = maximumInColumn;
20 }
21 }
22 }
23
24 // Return the modified matrix.
25 return matrix;
26}
27
Time and Space Complexity
The time complexity of the given code is O(m * n)
, where m
is the number of rows and n
is the number of columns in the matrix. This is because the code contains two nested loops, the outer loop iterating over the columns, and the inner loop iterating over the rows. For each column, the maximum value is found (taking O(m)
time), and then each row in that column is updated if necessary (another O(m)
time). Therefore, for each of the n
columns, the algorithm performs work proportional to the number of rows m
, leading to a total time complexity of O(m * n)
.
The space complexity of the algorithm is O(1)
. This reflects that the amount of extra space needed by the algorithm does not depend on the size of the input matrix. The only additional memory used is for the loop variables and the temporary variable mx
, and this does not scale with the size of the input matrix, hence the constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.