![73. Set Matrix Zeroes [Solved + Explanation] 3 Easy Method Explained](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhe506ptwV49Rk8iJQr_aJT72Uv9h1RjX-Azjq0Q5X-p7egVeNUEEZEdfBdqP3k8uBljHarfkwh6YpMDqCZ29MLD6LiypaWLmCg2rhGwfteQXTNtZS8_KJ1f9YlTkCjvDiqbp4WCf1NP5C9VCp1YetfGBmYO37bDU-IF4JCiq0kD5m2lSCBUm0wOdZojepL/s1921/Design%204%20(1).webp "3075. Maximize Happiness of Selected Children [Solved + Explanation] Easy Method Explained") |
| 73. Set Matrix Zeroes [Solved + Explanation] 3 Easy Method Explained |
Problem
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
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]]
Constraints:
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
Follow up:
- A straightforward solution using O(mn) space is probably a bad idea.
- A simple improvement uses O(m + n) space, but still not the best solution.
- Could you devise a constant space solution?
Solution
Intuition
We can solve this problem using Four approaches. (Here I have explained all the possible solutions of this problem).
- Solved using Matrix with Extra space. TC : O((NM)(N+M)), SC : O(N*M).
- Solved using Matrix with Constant space. TC : O((NM)(N+M)), SC : O(1).
- Solved using Array + Hash Table (Unordered set). TC : O(N*M), SC : O(N+M).
- Solved using Matrix with Constant space. Optimized Approaches. TC : O(N*M), SC : O(1).
Approach
We can easily understand the All the approaches by seeing the code which is easy to understand with comments.
Complexity
Time complexity:
Time complexity is given in code comment.
Space complexity:
Space complexity is given in code comment.
Code
/*
Time Complexity : O((N*M)*(N+M)), Where N is the number of row and M is number of column of matrix. Here
nested loops creates the time complexity. O(N*M) for traversing through each element and (N+M) for traversing
to row and column of elements having value 0.
Space Complexity : O(N*M), visited matrix space.
Solved using Matrix with Extra space.
*/
/***************************************** Approach 1 Code *****************************************/
class Solution {
public:
void setZeroes(vector>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector> visited = matrix;
for(int i=0; i>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
for(int i=0; i>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
unordered_set setRows;
unordered_set setColumns;
for(int i=0; i 0 || setColumns.count(j) > 0){
matrix[i][j] = 0;
}
}
}
}
};
/*
Time Complexity : O(N*M), Where N is the number of row and M is number of column of matrix. Here two nested
loops creates the time complexity.
Space Complexity : O(1), Constant space.
Solved using Matrix.
*/
/***************************************** Approach 2 Code *****************************************/
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == 0){
for(int k=0; k<m; k++){
if(matrix[i][k] != 0){
matrix[i][k] = -9999;
}
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == 0){
for(int k=0; k<n; k++){
if(matrix[k][j] != 0){
matrix[k][j] = -9999;
}
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == -9999){
matrix[i][j] = 0;
}
}
}
}
};
/*
Time Complexity : O(N*M), Where N is the number of row and M is number of column of matrix. Here two nested
loops creates the time complexity.
Space Complexity : O(N+M), Here Unordered set(setRows and setColumn) creates the space complexity. O(N) for
storing the row indexs and O(M) for storing the column indexs.
Solved using Matrix + Hash Table.
*/
/***************************************** Approach 3 Code *****************************************/
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
unordered_set<int> setRows;
unordered_set<int> setColumns;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == 0){
setRows.insert(i);
setColumns.insert(j);
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(setRows.count(i) > 0 || setColumns.count(j) > 0){
matrix[i][j] = 0;
}
}
}
}
};
/*
Time Complexity : O(N*M), Where N is the number of row and M is number of column of matrix. Here two nested
loops creates the time complexity.
Space Complexity : O(1), Constant space.
Solved using Matrix.
*/
/***************************************** Approach 4 Code *****************************************/
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
bool flag1 = false, flag2 = false;
for(int i=0; i<n; i++){
if(matrix[i][0] == 0){
flag1 = true;
}
}
for(int j=0; j<m; j++){
if(matrix[0][j] == 0){
flag2 = true;
}
}
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
if(matrix[i][j] == 0){
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}
}
}
if(flag1 == true){
for(int i=0; i<n; i++){
matrix[i][0] = 0;
}
}
if(flag2 == true){
for(int j=0; j<m; j++){
matrix[0][j] = 0;
}
}
}
}; Keywords :-
- leetcode solutions python,
- leetcode solutions two sum,
- Leetcode solutions pdf,
- Leetcode solutions java,
- leetcode solutions in c,
- Leetcode solutions github,
- leetcode solutions extension,
- leetcode solutions javascript,
- leetcode solutions c++ pdf,
- Leetcode solutions c++ github,
- leetcode problems and solutions pdf,
- Leetcode solutions c++ example,
- leetcode c++ easy,
- leetcode solutions java,
- leetcode problems and solutions java pdf,
- leetcode-solutions github,