Set Matrix Zeroes
Problem Statement
Given an m x n integer matrix mat, if an element is 0, set its entire row and column to 0's. You must do it in place.
Examples
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Explanation: The middle element (matrix[1][1] = 0) causes the entire second row and second column to be set to zero.
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Explanation: The first row and first column contain zeroes, so the entire first row and first column are set to zero. The element at matrix[1][3] (value 2) marks the 4th column to be set to zero in the second row.
Constraints
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
In the given problem, if an element in the matrix is 0, we need to set every value in its row and column to 0. So the brute force approach that should come to our mind is first, we traverse the entire matrix to identify all the cells that contain 0.
For this, we create an auxiliary matrix of the same size as the original, initialized with false (or 0). As we iterate through the matrix, whenever we encounter a 0 at position (i, j), we mark the corresponding cell in the auxiliary matrix as true (or 1). This auxiliary matrix effectively serves as a map to indicate which rows and columns need to be zeroed out in the original matrix.
Once we have completed the first pass and marked all the positions of 0's, we perform a second traversal of the matrix. During this traversal, we refer to the auxiliary matrix to determine if any cell belongs to a row or column that should be zeroed. If the corresponding position in the auxiliary matrix is marked as true, we set the element in the original matrix to 0.
Let's Understand with an Example:
Input Matrix : matrix = [[0, 1, 2, 0],[3, 4, 5, 2],[1, 3, 1, 5]]
We observe that the first row contains two 0's at positions (0,0) and (0,3).
Step 1: Initialize the Auxiliary Matrix
- The auxiliary matrix is created to track which rows and columns need to be set to zero. This matrix is of the same size as the original matrix and is initialized with False (or 0).
- marks = [[False, False, False, False], [False, False, False, False], [False, False, False, False]]
Step 2: Traverse the Original Matrix to Mark Zeros
- The first step is to loop through the original matrix to identify all the positions that contain a 0.
- When we encounter a 0, we mark the corresponding cell in the auxiliary matrix marks as True.
- First Row (matrix[0] = [0, 1, 2, 0]):
At (0, 0), there is a 0, so we mark marks[0][0] = True.
At (0, 3), there is a 0, so we mark marks[0][3] = True.
Now, the marks matrix looks like this:
marks = [[True, False, False, True], [False, False, False, False], [False, False, False, False]] - Second Row (matrix[1] = [3, 4, 5, 2]):
No 0's are encountered in this row, so the marks matrix remains unchanged. - Third Row (matrix[2] = [1, 3, 1, 5]):
No 0's are encountered in this row, so the marks matrix remains unchanged.
After the first pass, the marks matrix looks like this:
marks = [[True, False, False, True], [False, False, False, False], [False, False, False, False]]
Step 3: Update the Original Matrix Based on the Marks Matrix
- In the second traversal of the matrix, we check each cell of the original matrix. If marks[i][j] is True, it means that the cell at position (i, j) corresponds to a 0 in the original matrix, so we need to set all elements in that row and column to 0.
Let’s walk through this second pass:
- First Row ( matrix[0] = [0, 1, 2, 0] ):
matrix = [[0, 0, 0, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Since marks[0][0] = True, we set the entire first row to 0. So, after this step: - First Column ( matrix[0][0], matrix[1][0], matrix[2][0]):
matrix = [[0, 0, 0, 0], [0, 4, 5, 2], [0, 3, 1, 5]]
Since marks[0][0] = True, we set all elements in the first column to 0. So, after this step: - Fourth Column (matrix[0][3], matrix[1][3],matrix[2[3]):
matrix = [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
Since marks[0][3] = True, we set all elements in the fourth column to 0. So, after this step:
Final Matrix: After both traversals, the final modified matrix is:
matrix = [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
Step to Write Code
Step 1: Input and Initialize Auxiliary Matrix
- Start by taking the input matrix.
- Create an auxiliary matrix ( marks ) of the same size as the input matrix.
- Initialize all elements in marks as False.
Step 2: Traverse the Input Matrix to Mark Positions
- Loop through each element in the input matrix.
- Whenever you encounter a 0 at position (i, j), update marks[i][j] to True.
Step 3: Update the Original Matrix Using the Marks
- Loop through the matrix again. For each element (i, j):
- If marks[i][k] for any column k in the same row or marks[l][j] for any row l in the same column is True, set matrix[i][j] = 0.
Step 4: Return the Updated Matrix
- After modifying the matrix, return the output.
Code Implementation
C++
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
// Step 1: Create auxiliary matrix and initialize to False (0)
vector<vector<bool>> marks(m, vector<bool>(n, false));
// Step 2: Traverse the input matrix to mark positions of zeroes
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
marks[i][j] = true; // Mark this position
}
}
}
// Step 3: Update the input matrix based on marks
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (marks[i][j]) {
// Set all elements in row i to 0
for (int k = 0; k < n; k++) {
matrix[i][k] = 0;
}
// Set all elements in column j to 0
for (int l = 0; l < m; l++) {
matrix[l][j] = 0;
}
}
}
}
}
};
Java
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of columns
// Step 1: Create auxiliary matrix initialized to false
boolean[][] marks = new boolean[m][n];
// Step 2: Mark positions of zeroes
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
marks[i][j] = true;
}
}
}
// Step 3: Update rows and columns based on marks
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (marks[i][j]) {
// Set entire row i to 0
for (int k = 0; k < n; k++) {
matrix[i][k] = 0;
}
// Set entire column j to 0
for (int l = 0; l < m; l++) {
matrix[l][j] = 0;
}
}
}
}
}
}
Python
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None. Modify matrix in-place.
"""
m, n = len(matrix), len(matrix[0]) # Dimensions of the matrix
# Step 1: Create an auxiliary matrix to track zeros
marks = [[False] * n for _ in range(m)]
# Step 2: Mark positions where zeros are found
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
marks[i][j] = True # Mark this position
# Step 3: Update rows and columns in the original matrix
for i in range(m):
for j in range(n):
if marks[i][j]: # If this position was marked
# Set entire row `i` to 0
for k in range(n):
matrix[i][k] = 0
# Set entire column `j` to 0
for l in range(m):
matrix[l][j] = 0
Javascript
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
let m = matrix.length; // Number of rows
let n = matrix[0].length; // Number of columns
// Step 1: Create an auxiliary matrix to mark zero positions
let marks = Array.from({ length: m }, () => Array(n).fill(false));
// Step 2: Traverse the matrix and mark positions with zeros
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
marks[i][j] = true; // Mark this position
}
}
}
// Step 3: Update the original matrix based on the marks
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (marks[i][j]) {
// Set the entire row to 0
for (let k = 0; k < n; k++) {
matrix[i][k] = 0;
}
// Set the entire column to 0
for (let l = 0; l < m; l++) {
matrix[l][j] = 0;
}
}
}
}
};
Time Complexity: O(m×n×(m+n))
The time complexity of the provided solution can be analyzed step by step based on the operations performed in each part of the algorithm:
Step 1: Create Auxiliary Matrix
- The auxiliary matrix marks is initialized with size m×n (same as the input matrix matrix).
- Initializing all elements to false involves iterating through the m×n matrix.
Time complexity of Step 1: O(m×n)
Step 2: Traverse Input Matrix to Mark Zeroes
- A nested loop is used to iterate through every element of the input matrix matrix.
- For each element, a comparison is made to check whether it is zero. If it is zero, the corresponding position in the marks matrix is set to true.
Time complexity of Step 2: O(m×n)
Step 3: Update Input Matrix Based on Marks
- The outer loop iterates through all elements of the input matrix again.
- If an element in the marks matrix is true, the algorithm performs two operations:
- Sets all elements in the corresponding row to 0. This requires O(n) operations for each row.
- Sets all elements in the corresponding column to 0. This requires O(m) operations for each column.
In the worst case, where every element in the input matrix is 0, the entire row and column of each element are updated. This results in redundant operations because multiple rows and columns are repeatedly set to zero.
- For a matrix of size m×n, the worst-case number of operations is approximately: O(m×n×(m+n))
Time complexity of Step 3: O(m×n×(m+n))
Therefore, the overall time complexity of the algorithm is: O(m×n×(m+n))
Space Complexity: O(m×n)
- Auxiliary Matrix
- An auxiliary matrix marks of size m×n
vector<vector<bool>> marks(m, vector<bool>(n, false)) - This matrix stores a boolean value for every element in the input matrix.
- Space required: O(m×n)
2. Input Matrix
- The input matrix matrix of size m×n is passed as a reference. Since it is part of the input, it does not contribute to extra space complexity.
3. Temporary Variables
- A few integer variables (m, n, i, j, k, l) are used to iterate over the matrix. These occupy constant space: O(1)
Total Space Complexity: Adding the contributions:
- Auxiliary matrix: O(m×n)
- Temporary variables: O(1)
Thus, the overall space complexity is dominated by the auxiliary matrix: O(m×n)
Since this solution take the space of O(m*n) can we optimize it?
Better Approach
Yes, The previous solution uses an auxiliary 2D matrix to store the positions of zeroes and ones. However, this approach requires O(m*n) space. To optimize the solution, we can use two separate arrays: one for rows and one for columns.
- The rows array will track which rows contain a cell with a value of 0. If rows[i] is true, it means row i has at least one cell with a value of 0.
- Similarly, the columns array will track which columns contain a cell with a value of 0. If columns[j] is true, it means column j has at least one cell with a value of 0.
This approach reduces the space complexity and makes the solution more efficient.
Let's break it down step by step with the given example:
Let's Understand with an Example:
Goal: If a cell in the matrix contains 0, set its entire row and entire column to 0.
Step-by-Step Explanation:
Step 1: Identify rows and columns with zeroes
We use two separate arrays:
- rows: To track which rows have a 0.
- columns: To track which columns have a 0.
Initially, both arrays are empty:
rows = [False, False, False]
columns = [False, False, False, False]
Now, we scan through the matrix to update the rows and columns arrays:
- In row 0, we find 0 at indices 0 and 3.
→ Mark rows[0] = True and columns[0] = True, columns[3] = True. - In row 1, no zeroes are found.
- In row 2, no zeroes are found.
At the end of this step:
rows = [True, False, False]
columns = [True, False, False, True]
Step 2: Modify the matrix
Now, using the rows and columns arrays:
- If rows[i] = True, set all elements in row i to 0.
- If columns[j] = True, set all elements in column j to 0.
Start updating the matrix:
- Row 0: rows[0] = True → Set all elements in row 0 to 0.
Result:[[0, 0, 0, 0], [3, 4, 5, 2], [1, 3, 1, 5]] - Row 1: rows[1] = False → No change to row 1.
- Row 2: rows[2] = False → No change to row 2.
Now handle the columns:
- Column 0: columns[0] = True → Set all elements in column 0 to 0.
Result: [[0, 0, 0, 0], [0, 4, 5, 2], [0, 3, 1, 5]] - Column 1: columns[1] = False → No change to column 1.
- Column 2: columns[2] = False → No change to column 2.
- Column 3: columns[3] = True → Set all elements in column 3 to 0.
Result: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
Final Output: [[0, 0, 0, 0], [0, 4, 5, 0],[0, 3, 1, 0]]
Steps to write code
Step 1: Initialize helper arrays
- Create two Boolean arrays, rows and columns, to track which rows and columns need to be set to 0.
- rows should have a size equal to the number of rows in the matrix.
- columns should have a size equal to the number of columns in the matrix.
- Initialize both arrays to False.
Step 2: Identify rows and columns with zeroes
- Iterate through the matrix using a nested loop:
- Outer loop for rows (i from 0 to m-1).
- Inner loop for columns (j from 0 to n-1).
- If matrix[i][j] == 0, mark:
- rows[i] = True (indicating row i has a 0).
- columns[j] = True (indicating column j has a 0).
Step 3: Update the matrix
- Iterate through the matrix again:
- For each cell matrix[i][j]:
- If rows[i] == True or columns[j] == True, set matrix[i][j] = 0.
Step 4: Return the updated matrix
- Return or print the modified matrix.
Code Implementation
C++
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
vector<bool> rows(m, false); // Track rows to zero
vector<bool> cols(n, false); // Track columns to zero
// Step 2: Identify rows and columns with zeros
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
// Step 3: Update the matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
}
};Java
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of columns
boolean[] rows = new boolean[m]; // Track rows to zero
boolean[] cols = new boolean[n]; // Track columns to zero
// Step 2: Identify rows and columns with zeros
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
// Step 3: Update the matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
}
}
Python
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None. Modify matrix in-place.
"""
m, n = len(matrix), len(matrix[0]) # Rows and columns
rows = [False] * m # Track rows to zero
cols = [False] * n # Track columns to zero
# Step 2: Identify rows and columns with zeros
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
rows[i] = True
cols[j] = True
# Step 3: Update the matrix
for i in range(m):
for j in range(n):
if rows[i] or cols[j]:
matrix[i][j] = 0
Javascript
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
let m = matrix.length; // Number of rows
let n = matrix[0].length; // Number of columns
let rows = new Array(m).fill(false); // Track rows to zero
let cols = new Array(n).fill(false); // Track columns to zero
// Step 2: Identify rows and columns with zeros
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
rows[i] = true;
cols[j] = true;
}
}
}
// Step 3: Update the matrix
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
};
Time Complexity: O(m×n)
- Initialization of Row and Column Tracking Arrays
- Two vectors, rows and cols, of sizes mmm (number of rows) and nnn (number of columns) are initialized.
- Initializing these arrays requires O(m) and O(n), respectively.
Time complexity for this step: O(m+n)
2. Identifying Rows and Columns with Zeroes
- A nested loop iterates through all m×n elements of the matrix.
- For each element, the algorithm checks whether it is zero and updates the corresponding indices in the rows and cols vectors.
Time complexity for this step: O(m×n)
3. Updating the Matrix
- Another nested loop iterates through all m×n elements of the matrix.
- For each element, it checks the corresponding entries in the rows and cols arrays to decide if the element should be set to zero.
Time complexity for this step: O(m×n)
Total Time Complexity
Adding up all the steps:
- Initializing rows and cols: O(m+n)
- Identifying rows and columns with zeroes: O(m×n)
- Updating the matrix: O(m×n)
The total time complexity is dominated by the O(m×n) steps, so: O(m×n)
Space Complexity: O(m+n)
1. Input Matrix
- The input matrix is passed as a reference, so it does not contribute to extra space complexity.
2. Auxiliary Arrays (rows and cols)
- Two auxiliary vectors are used:
- rows of size m (number of rows).
- cols of size n (number of columns).
Space required: O(m)+O(n)=O(m+n)
3. Temporary Variables
- A few integer variables (e.g., m, n, i, j) are used for iterating over the matrix.
- These occupy constant space.
Space required: O(1)
Total Space Complexity: The dominant space contribution comes from the auxiliary arrays, so the overall space complexity is: O(m+n)
Since our previous approach takes the space complexity of O(m+n), can we optimize it further?
Optimal Approach
The answer is yes, we can avoid this additional space by using the first row and first column of the matrix itself to store the markers. We can mark the cells in the first row and first column to indicate which rows and columns need to be set to zero. This allows us to eliminate the need for auxiliary arrays and keeps the space complexity down to O(1) (ignoring the input matrix).
Now, what about the first row and first column themselves? Can we use them as markers too?
Here's the challenge: Since we're using these rows and columns to store our markers, we need to handle them carefully, as we don't want to overwrite the markers before we've processed them.
The solution is to first check if the first row and first column themselves contain any zeros. We can do this by using two boolean variables:
- firstrow: This flag will indicate if the first row needs to be set to zero.
- firstcolumn: This flag will indicate if the first column needs to be set to zero.
After scanning the entire matrix, we can use the first row and first column to mark the rows and columns that need to be set to zero. Finally, we'll handle the first row and first column separately based on the flags firstrow and firstcolumn. If either flag is set to true, we'll zero out the corresponding row or column.
In this way, we achieve the goal of marking the necessary rows and columns with minimal space usage while still handling edge cases like the first row and column containing zeros.
Let's Understand with a Example
Given the matrix: [[0,1,2,0], [3,4,5,2], [1,3,1,5]]
- Mark Rows and Columns: This leads to the following matrix after marking: [[0, 1, 0, 0], [0, 4, 5, 2], [0, 3, 1, 5]]
- We traverse the matrix and for each zero we find, we mark the corresponding row and column:
- At position (0, 0), we set matrix[0][0] = 0 and matrix[0][0] = 0 (already 0).
- At position (0, 3), we set matrix[0][3] = 0 and matrix[0][3] = 0.
- At position (1, 0), we set matrix[1][0] = 0 and matrix[0][0] = 0 (already 0).
- Zero Out Cells:
The matrix after this step looks like this:[[0, 0, 0, 0], [0, 4, 5, 0], [0, 0, 0, 0]] - Now, we traverse the rest of the matrix starting from (1, 1). Based on the markers in the first row and column:
- At (1, 1), matrix[1][0] = 0 → Set matrix[1][1] = 0.
- At (1, 2), matrix[1][0] = 0 → Set matrix[1][2] = 0.
- At (1, 3), matrix[1][0] = 0 → Set matrix[1][3] = 0.
- At (2, 1), matrix[0][1] = 0 → Set matrix[2][1] = 0.
- At (2, 2), matrix[0][2] = 0 → Set matrix[2][2] = 0.
- At (2, 3), matrix[0][3] = 0 → Set matrix[2][3] = 0.
- Zero Out First Row and Column:
The final result is:[[0, 0, 0, 0], [0, 4, 5, 0], [0, 0, 0, 0]] - Finally, based on the flags firstrow and firstcolumn, we check and zero out the first row and first column:
- Since firstrow is true (the first row had a 0), we set the entire first row to 0.
- Since firstcolumn is true (the first column had a 0), we set the entire first column to 0.
Steps to write the Code
- Initial Setup:
Declare two boolean flags, firstrow, and firstcolumn, to check if the first row and first column should be set to zero. Initialize both to false. - First Pass (Marking Zeroes in First Row and First Column):
Loop through the matrix starting from the first row and first column.
If a cell contains zero, mark its corresponding row and column in the first row and first column.
Specifically, if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
While doing this, check if any zeroes are present in the first row and first column.
Set firstrow = true if the first row needs to be zeroed and firstcolumn = true if the first column needs to be zeroed. - Second Pass (Setting Matrix Cells to Zero Based on Marks):
Loop through the matrix starting from the second row and second column (i.e., i = 1 and j = 1).
If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0. This step zeros out the cells based on the markings made in the first pass. - Handle the First Row:
If firstrow == true, it means the first row needs to be set to zero. Iterate over the entire first row and set all elements to zero. - Handle the First Column:
If firstcolumn == true, it means the first column needs to be set to zero. Iterate over the entire first column and set all elements to zero. - Edge Case Handling:
Handle the special cases where the first row or column might already be zeroes, using the firstrow and firstcolumn flags to avoid overwriting the markers prematurely.
Code Implementation
C++
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
bool firstrow = false, firstcolumn = false;
// Step 1: Check if first row needs to be zeroed
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstrow = true;
break;
}
}
// Step 2: Check if first column needs to be zeroed
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstcolumn = true;
break;
}
}
// Step 3: Mark zeroes in the first row and first column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Step 4: Set matrix cells to zero based on marks in the first row and first column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// Step 5: Handle the first row
if (firstrow) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Step 6: Handle the first column
if (firstcolumn) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
};
Java
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of columns
boolean firstrow = false, firstcolumn = false;
// Step 1: Check if first row needs to be zeroed
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstrow = true;
break;
}
}
// Step 2: Check if first column needs to be zeroed
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstcolumn = true;
break;
}
}
// Step 3: Mark zeroes in the first row and first column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Step 4: Set matrix cells to zero based on marks in the first row and first column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// Step 5: Handle the first row
if (firstrow) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Step 6: Handle the first column
if (firstcolumn) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
Python
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None. Modify matrix in-place.
"""
m, n = len(matrix), len(matrix[0]) # Rows and columns
# Step 1: Initialize flags
firstrow, firstcolumn = False, False
# Step 2: Check if first row needs to be zeroed
for j in range(n):
if matrix[0][j] == 0:
firstrow = True
break
# Step 3: Check if first column needs to be zeroed
for i in range(m):
if matrix[i][0] == 0:
firstcolumn = True
break
# Step 4: Mark zeroes in the first row and first column
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Step 5: Set matrix cells to zero based on marks in the first row and first column
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Step 6: Handle first row
if firstrow:
for j in range(n):
matrix[0][j] = 0
# Step 7: Handle first column
if firstcolumn:
for i in range(m):
matrix[i][0] = 0
Javascript
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
let m = matrix.length; // Number of rows
let n = matrix[0].length; // Number of columns
let firstrow = false, firstcolumn = false;
// Step 1: Check if first row should be zeroed
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
firstrow = true;
break;
}
}
// Step 2: Check if first column should be zeroed
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
firstcolumn = true;
break;
}
}
// Step 3: Mark the first row and first column
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Step 4: Set matrix cells to zero based on marks
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
// Step 5: Handle the first row
if (firstrow) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Step 6: Handle the first column
if (firstcolumn) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
};
Time Complexity: O(m × n)
The time complexity of the provided code is O(m × n), where:
- m is the number of rows in the matrix.
- n is the number of columns in the matrix.
Breakdown of time complexity:
- Step 1: Check if the first row needs to be zeroed.
This involves iterating over all columns in the first row.
Time complexity: O(n). - Step 2: Check if the first column needs to be zeroed.
This involves iterating over all rows in the first column.
Time complexity: O(m). - Step 3: Mark zeroes in the first row and first column.
This involves iterating over the entire matrix (excluding the first row and column).
Time complexity: O((m−1)×(n−1)), which simplifies to O(m×n). - Step 4: Set matrix cells to zero based on marks in the first row and first column.
This also involves iterating over the entire matrix (excluding the first row and column).
Time complexity: O((m−1)×(n−1)), which simplifies to O(m×n). - Step 5: Handle the first row.
This involves iterating over all columns in the first row.
Time complexity: O(n). - Step 6: Handle the first column.
This involves iterating over all rows in the first column.
Time complexity: O(m).
Total Time Complexity:
Adding all the terms: O(n)+O(m)+O(m×n)+O(m×n)+O(n)+O(m)
The dominant term is O(m×n), as it grows faster than the others for large m and n.
Thus, the overall time complexity is O(m×n).
Space Complexity: O(1)
The space complexity of the given code is O(1) (constant space).
Explanation:
- In-place Modification:
- The algorithm uses the first row and first column of the matrix itself to store markers, indicating which rows and columns need to be zeroed.
- This eliminates the need for additional memory to store separate markers.
- Boolean Variables:
- Two Boolean variables (firstrow and firstcolumn) are used to track whether the first row and first column need to be zeroed.
- These occupy O(1) space.
- No Extra Data Structures:
- No additional arrays, matrices, or other data structures are created.
Total Space Complexity:
Since the algorithm does not use any extra space that grows with the size of the input, the space complexity is O(1).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Given an m x n matrix, return all elements of the matrix in spiral order.