Set Matrix Zeroes LeetCode Solution
Set Matrix Zeroes Leetcode Solution :
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.
Example :
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Set Matrix Zeroes LeetCode Solution :
Constraints :
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -231 <= matrix[i][j] <= 231 – 1
Example 1:
- 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]]
Approach:
- First, the code initializes two dummy vectors,
dummyRowanddummyCol, with initial values of -1. These vectors will be used to mark the rows and columns that need to be set to zero. - The code then iterates through each element of the matrix and checks if it is zero. If an element is zero, it updates the corresponding indices in
dummyRowanddummyColto 0. - After marking the rows and columns, the code iterates through the matrix again. For each element, it checks if the corresponding row index or column index in
dummyRowordummyColis zero. If either of them is zero, it sets the current element to zero. - Finally, the matrix will have rows and columns set to zero based on the values in
dummyRowanddummyCol.
Complexity:
- Time Complexity: O(mn), where m and n are the number of rows and columns in the matrix, respectively. We have to traverse the matrix twice.
- Space Complexity: O(m+n), where m and n are the number of rows and columns in the matrix, respectively. We are using two auxiliary vectors of size m and n to keep track of the rows and columns that contain zero elements.
Code :
C++
Java
Python
C++
class Solution {
public:
void setZeroes(vector< vector>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector dummyRow(row,-1);
vector dummyCol(col,-1);
for(int i=0;i< row;i++){
for(int j=0;j<col;j++){
if(matrix[i][j]==0){
dummyRow[i] = 0;
dummyCol[j] = 0;
}
}
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(dummyRow[i] == 0 || dummyCol[j] == 0 ){
matrix[i][j]=0;
}
}
}
}
};Java
class Solution {
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int[] dummyRow = new int[row];
int[] dummyCol = new int[col];
Arrays.fill(dummyRow, -1);
Arrays.fill(dummyCol, -1);
for(int i=0;i< row;i++){
for(int j=0;j<col;j++){
if(matrix[i][j]==0){
dummyRow[i] = 0;
dummyCol[j] = 0;
}
}
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(dummyRow[i] == 0 || dummyCol[j] == 0 ){
matrix[i][j]=0;
}
}
}
}
}Python
class Solution(object):
def setZeroes(self, matrix):
row = len(matrix)
col = len(matrix[0])
dummyRow = [-1] * row
dummyCol = [-1] * col
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
dummyRow[i] = 0
dummyCol[j] = 0
for i in range(row):
for j in range(col):
if dummyRow[i] == 0 or dummyCol[j] == 0:
matrix[i][j] = 0
Login/Signup to comment