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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment