Problem: Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Example:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]
Approach: Instead of using an additional array we can use first row and first column for hashing to tell whether the current element should be 0 or not. The only problem which remains is if we overwrite first row and first column then how do we know that whether we should make first row and column zero or not? To solve this we can preprocess the matrix and store these values in say tow bool variables which will indicate whether we should make all the elements of first row and first column zero or not. That's it!
Implementation in C#:
public void SetZeroes(int[][] matrix)
{
int rows = matrix?.Length ?? 0;
if (rows == 0)
{
return;
}
int cols = matrix[0].Length;
bool isFirstRowZero = false;
bool isFirstColZero = false;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (matrix[i][j] == 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
if (i == 0)
{
isFirstRowZero = true;
}
if (j == 0)
{
isFirstColZero = true;
}
}
}
}
for (int i = 1; i < rows; ++i)
{
for (int j = 1; j < cols; ++j)
{
if (matrix[i][0] == 0 || matrix[0][j] == 0)
{
matrix[i][j] = 0;
}
}
}
if (isFirstRowZero)
{
for (int j = 0; j < cols; ++j)
{
matrix[0][j] = 0;
}
}
if(isFirstColZero)
{
for (int i = 0; i < rows; ++i)
{
matrix[i][0] = 0;
}
}
}
Complexity: O(m * n)
No comments:
Post a Comment