Modify the Matrix
Problem Statement
Given a 0-indexed m x n integer matrix matrix, create a new 0-indexed matrix called answer. Make answer equal to matrix, then replace each element with the value -1 with the maximum element in its respective column. Return the matrix answer.
Examples:
Input: matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
Output: [[1,2,9],[4,8,6],[7,8,9]]
Explanation:
- We replace the value in the cell [1][1] with the maximum value in the column 1, that is 8.
- We replace the value in the cell [0][2] with the maximum value in the column 2, that is 9.
Input: matrix = [[3,-1],[5,2]]
Output: [[3,2],[5,2]]
Explanation: We replace the value in the cell [0][1] with the maximum value in the column 1, that is 2.
Constraints:
m == mat.length
n == mat[i].length
2 <= m, n <= 50
-1 <= mat[i][j] <= 100
Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
The given problem asks us to create a new matrix where all the cells that contain -1 are replaced with the maximum element from their respective columns.
Here's the clear intuition behind solving this problem:
Imagine you have a table (or matrix) where each column contains a list of numbers, and some of these numbers are -1. These -1 values are placeholders, and you are tasked with filling them with a more meaningful value — the largest number from the same column.
How we will achieve this?
To achieve this, we will first create a new matrix that is a copy of the given matrix. Then, for each column in the matrix, we will find the maximum value by scanning all the elements in that column. Once we have the maximum for each column, we will iterate through the entire matrix, and wherever we encounter a -1, we will replace it with the maximum value of its respective column. This ensures that all -1 values are replaced with the largest number in their column while leaving other values unchanged. Finally, we return the modified matrix, which now has no -1 values, but instead has the appropriate maximum values in place of the -1's.
Let's walk through an example:
Input Matrix: matrix = [[1, 2, -1], [4, -1, 6], [7, 8, 9]]
We traverse the matrix column by column to identify and replace -1 values with the maximum value in that column.
Step 1: Processing Column 0 (j = 0)
Values in Column 0: [1, 4, 7]
- Initialize maxi = -1.
- Traverse the rows in Column 0 to find the maximum value:
- Compare maxi with matrix[0][0] → maxi = max(-1, 1) = 1
- Compare maxi with matrix[1][0] → maxi = max(1, 4) = 4
- Compare maxi with matrix[2][0] → maxi = max(4, 7) = 7
Maximum value in Column 0: maxi = 7.
- Replace -1 in Column 0:
- No -1 values in this column, so no replacements are needed.
Step 2: Processing Column 1 (j = 1)
Values in Column 1: [2, -1, 8]
- Initialize maxi = -1.
- Traverse the rows in Column 1 to find the maximum value:
- Compare maxi with matrix[0][1] → maxi = max(-1, 2) = 2
- Compare maxi with matrix[1][1] → maxi = max(2, -1) = 2
- Compare maxi with matrix[2][1] → maxi = max(2, 8) = 8
Maximum value in Column 1: maxi = 8.
- Replace -1 in Column 1:
- Check matrix[1][1], which is -1. Replace it with maxi = 8.
Step 3: Processing Column 2 (j = 2)
Values in Column 2: [-1, 6, 9]
- Initialize maxi = -1.
- Traverse the rows in Column 2 to find the maximum value:
- Compare maxi with matrix[0][2] → maxi = max(-1, -1) = -1
- Compare maxi with matrix[1][2] → maxi = max(-1, 6) = 6
- Compare maxi with matrix[2][2] → maxi = max(6, 9) = 9
Maximum value in Column 2: maxi = 9.
- Replace -1 in Column 2:
- Check matrix[0][2], which is -1. Replace it with maxi = 9.
Final Output: The modified matrix is: [[1, 2, 9], [4, 8, 6], [7, 8, 9]]
How to convert it in code:
- Initialize Matrix Dimensions: Get the number of rows m and columns n.
- Create a Copy of the Input Matrix: Make a copy of the input matrix to avoid modifying it directly.
- Process Each Column:
Traverse column by column (index j from 0 to n-1):
Find the Maximum Value: Loop through all rows (index i from 0 to m-1) to find the maximum value in the current column.
Replace -1 Values: Loop through all rows again and replace any -1 in the current column with the maximum value. - Return the Modified Matrix: Return the updated matrix as the final output.
Code Implementation
C++
class Solution {
public:
vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
// Get the number of rows (m) and columns (n) in the matrix
int m = matrix.size(); // m is the number of rows
int n = matrix[0].size(); // n is the number of columns
// Create a new matrix 'answer' equal to 'matrix'
vector<vector<int>> answer = matrix; // Create a copy of the matrix
// Traverse each column (j) one by one
for (int j = 0; j < n; j++) {
int maxi = -1; // Initialize maxi to -1, which will hold the maximum value
// Find the maximum value in the column
for (int i = 0; i < m; i++) {
maxi = max(maxi, matrix[i][j]); // Update maxi with the largest value in the column
}
// Replace each -1 in the column with the maximum value found
for (int i = 0; i < m; i++) {
if (answer[i][j] == -1) {
answer[i][j] = maxi; // Replace -1 with the maximum value
}
}
}
// Return the modified matrix
return answer;
}
};Java
class Solution {
public int[][] modifiedMatrix(int[][] matrix) {
// Get the number of rows (m) and columns (n) in the matrix
int m = matrix.length; // m is the number of rows
int n = matrix[0].length; // n is the number of columns
// Create a new matrix 'answer' equal to 'matrix'
int[][] answer = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
answer[i][j] = matrix[i][j]; // Copy each element to answer
}
}
// Traverse each column (j) one by one
for (int j = 0; j < n; j++) {
int maxi = -1; // Initialize maxi to -1, to find the maximum in the column
// Find the maximum value in the column
for (int i = 0; i < m; i++) {
maxi = Math.max(maxi, matrix[i][j]); // Update maxi if a larger value is found
}
// Replace each -1 with the maximum value found in the column
for (int i = 0; i < m; i++) {
if (answer[i][j] == -1) {
answer[i][j] = maxi; // Replace -1 with the maximum value found
}
}
}
// Return the modified matrix
return answer;
}
}
Python
class Solution:
def modifiedMatrix(self, matrix):
# Get the number of rows (m) and columns (n) in the matrix
m = len(matrix) # m is the number of rows
n = len(matrix[0]) # n is the number of columns
# Create a new matrix 'answer' equal to 'matrix'
answer = [row[:] for row in matrix] # Deep copy of the matrix
# Traverse each column (j) one by one
for j in range(n):
maxi = -1 # Initialize maxi as -1, as we need to find the maximum element
# Find the maximum value in the column
for i in range(m):
maxi = max(maxi, matrix[i][j]) # Update maxi with the maximum value
# Replace each -1 with the maximum value in that column
for i in range(m):
if answer[i][j] == -1:
answer[i][j] = maxi # Replace -1 with the maximum value found
# Return the modified matrix
return answer
Javascript
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var modifiedMatrix = function(matrix) {
// Get the number of rows (m) and columns (n) in the matrix
const m = matrix.length; // m is the number of rows
const n = matrix[0].length; // n is the number of columns
// Create a new matrix 'answer' equal to 'matrix'
let answer = matrix.map(row => row.slice());
// Traverse each column (j) one by one
for (let j = 0; j < n; j++) {
// Initialize a variable 'maxi' to store the maximum value in the column
let maxi = -1;
// Traverse the column to find the maximum value in this column
for (let i = 0; i < m; i++) {
maxi = Math.max(maxi, matrix[i][j]); // Update 'maxi' with the maximum value found
}
// Traverse the column again to replace all -1's with the maximum value found
for (let i = 0; i < m; i++) {
if (answer[i][j] === -1) {
answer[i][j] = maxi; // Replace -1 with 'maxi'
}
}
}
// Return the modified matrix
return answer;
};
Time Complexity : O(m×n)
To analyze the time complexity, let’s break down the steps of the algorithm:
Step 1: Get Matrix Dimensions
- Operation: Calculate m (number of rows) and n (number of columns).
- Cost: O(1).
- Reason: This step involves a constant-time operation to access the matrix's length properties.
Step 2: Create a Copy of the Matrix
- Operation: Copy the input matrix to the answer matrix.
- Cost: O(m×n).
- Reason: Each of the m×n elements in the input matrix is copied to the new matrix.
Step 3: Process Each Column
For each column j (total n columns):
- Find the Maximum Value in the Column: Traverse all m rows in the column.
- Cost per column: O(m).
- Total cost for all columns: O(n×m).
- Replace All -1 Values in the Column:
- Traverse all mmm rows again.
- Cost per column: O(m).
- Total cost for all columns: O(n×m).
- Combined Cost for Processing All Columns: O(n×m)+O(n×m)=O(2×n×m)
Step 4: Return the Matrix
- Operation: Return the answer matrix.
- Cost: O(1).
- Reason: Returning a reference to the matrix involves a constant-time operation.
Summing up all the steps: O(1)+O(m×n)+O(2×n×m)+O(1)
The dominant term in the time complexity is O(m×n), which represents the work done in processing the matrix. So the the overall complexity is proportional to the product of the number of rows and columns, making O(m×n) the dominant factor in the algorithm.
Space Complexity: O(1)
The space complexity of the algorithm depends on the amount of extra space used beyond the input matrix.
- Input Matrix: The matrix itself is given as input, and we are not creating a completely separate matrix for our calculations. Instead, in this implementation, the updates are made directly to a copy of the matrix answer, so the size of this matrix is O(m×n), but it is considered part of the input.
- Extra Variables: A single integer variable maxi is used to store the maximum value of a column during the traversal. This requires O(1) space. Loop variables (i and j) are also used, but they are simple integers and require constant space, O(1).
- Output Matrix: The result answer is a new matrix that also has the same dimensions as the input matrix, O(m×n). However, since this matrix is expected as the output, it is not considered part of the extra space.
Overall Space Complexity: The extra space used is constant, O(1), since the algorithm does not require any additional data structures (like arrays or matrices) proportional to the size of the input. All modifications are made in place or to the expected output.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.
The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.
Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.