grid47 Exploring patterns and algorithms
Oct 30, 2024
6 min read
Solution to LeetCode 73: Set Matrix Zeroes Problem
You are given an m x n matrix of integers. Whenever an element in the matrix is 0, you need to set all elements in the corresponding row and column to 0, but the operation must be done in place. This means you cannot use extra space for another matrix.
Problem
Approach
Steps
Complexity
Input: You are given a matrix of size m x n containing integers.
• Explanation: The second row has a 0 at (1,1). Hence, the entire second row and the second column are set to 0.
Approach: The solution involves using the first row and column to store the state of rows and columns that need to be zeroed. This allows the matrix to be modified in place without using additional space.
Observations:
• The matrix needs to be transformed in place without extra space.
• We can use the first row and column to store flags for marking rows and columns that need to be zeroed.
• Using a flag system for the first row and column will prevent overwriting important data during the transformation.
Steps:
• Traverse the matrix to check for zeros.
• Mark the first row and first column if they contain a zero.
• Use the first row and column to flag other rows and columns that contain zeros.
• Traverse the matrix again to apply the zeroing transformation.
• Handle the first row and column separately if they were marked as containing zeros.
Empty Inputs:
• If the matrix has only one row or one column, it must be handled appropriately.
Large Inputs:
• Consider cases where the matrix size is at the upper limit (200x200).
Special Values:
• Ensure that negative numbers and boundary values are handled correctly.
Constraints:
• The solution must be implemented in-place and must not use additional matrices for storage.
voidsetZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRowZero =false, firstColZero =false;
// Check if first row has a zero
for (int j =0; j < n; j++) {
if (matrix[0][j] ==0) {
firstRowZero =true;
break;
}
}
// Check if first column has a zero
for (int i =0; i < m; i++) {
if (matrix[i][0] ==0) {
firstColZero =true;
break;
}
}
// Mark the rows and columns with zeros using the first row and column
for (int i =1; i < m; i++) {
for (int j =1; j < n; j++) {
if (matrix[i][j] ==0) {
matrix[i][0] = matrix[0][j] =0;
}
}
}
// Set the rows and columns marked as zero to zero
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;
}
}
}
// Set the first row to zero if necessary
if (firstRowZero) {
for (int j =0; j < n; j++) {
matrix[0][j] =0;
}
}
// Set the first column to zero if necessary
if (firstColZero) {
for (int i =0; i < m; i++) {
matrix[i][0] =0;
}
}
}
1 : Function Declaration
voidsetZeroes(vector<vector<int>>& matrix) {
Declares a function `setZeroes` that takes a 2D vector `matrix` as input and modifies it in-place.
2 : Variable Initialization
int m = matrix.size(), n = matrix[0].size();
Initializes variables `m` and `n` to store the number of rows and columns in the matrix.
3 : Variable Initialization
bool firstRowZero =false, firstColZero =false;
Initializes boolean flags `firstRowZero` and `firstColZero` to track if the first row and column contain zeros.
4 : Loop Iteration
for (int j =0; j < n; j++) {
if (matrix[0][j] ==0) {
firstRowZero =true;
break;
}
}
Iterates through the first row of the matrix and sets `firstRowZero` to `true` if a zero is found.
5 : Loop Iteration
for (int i =0; i < m; i++) {
if (matrix[i][0] ==0) {
firstColZero =true;
break;
}
}
Iterates through the first column of the matrix and sets `firstColZero` to `true` if a zero is found.
6 : Nested Loops
for (int i =1; i < m; i++) {
for (int j =1; j < n; j++) {
if (matrix[i][j] ==0) {
matrix[i][0] = matrix[0][j] =0;
}
}
}
Iterates through the matrix, excluding the first row and column. If a zero is found, marks the corresponding row and column using the first row and column as markers.
7 : Nested Loops
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;
}
}
}
Iterates through the matrix again, setting elements to zero based on the markers in the first row and column.
8 : Conditional
if (firstRowZero) {
for (int j =0; j < n; j++) {
matrix[0][j] =0;
}
}
If the first row was originally zero, set all elements in the first row to zero.
9 : Conditional
if (firstColZero) {
for (int i =0; i < m; i++) {
matrix[i][0] =0;
}
}
If the first column was originally zero, set all elements in the first column to zero.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: The time complexity is O(m * n) because we iterate through the entire matrix twice.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because the solution is implemented in-place without additional storage.
