Coding-Decoded/August2021/SetMatrixZeroes.java at master · Sunchit/Coding-Decoded · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 class Solution {

     // TC : O(m*n)
     // SC : O(m+n)
     public void setZeroes(int[][] matrix) {
         List<Integer> rowZero = new ArrayList<>();
         List<Integer> colZero = new ArrayList<>();

         for(int i=0;i<matrix.length;i++){
             for(int j=0;j<matrix[0].length;j++){
                 if(matrix[i][j] == 0){
                     rowZero.add(i);
                     colZero.add(j);
                 }
             }
         }

         for(int rowIndex : rowZero){
             makeRowZero(matrix, rowIndex);
         }

         for(int colIndex : colZero){
             makeColZero(matrix, colIndex);
         }

         return;
     }

     private void makeRowZero(int[][] matrix, int rIndex){
         for(int j=0;j<matrix[0].length;j++) {
             matrix[rIndex][j] = 0;
         }
     }


     private void makeColZero(int[][] matrix, int cIndex){
         for(int i=0;i<matrix.length;i++) {
             matrix[i][cIndex] = 0;
         }
     }
 }


// TC : O(m*n)
// SC : O(1)
public class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix==null){
            return;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;

        for(int i=0; i<n; i++){
            if(matrix[0][i]==0){
                firstRowHasZero = true;
                break;
            }
        }

        for(int i=0; i<m; i++){
            if(matrix[i][0]==0){
                firstColHasZero = true;
                break;
            }
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][j]==0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }


        for(int j=1;j<n; j++){
            if(matrix[0][j]==0){
                nullifyCol(matrix, j, m, n);
            }
        }

        for(int i=1; i<m; i++){
            if(matrix[i][0]==0){
                nullifyRow(matrix, i, m, n);
            }
        }

        if(firstRowHasZero){
            nullifyRow(matrix, 0, m, n);
        }
        if(firstColHasZero){
            nullifyCol(matrix, 0, m, n);
        }

    }

    public void nullifyRow(int[][] matrix, int i, int m, int n){
        for(int col=0; col<n; col++){
            matrix[i][col] = 0;
        }
    }

    public void nullifyCol(int[][] matrix, int j, int m, int n){
        for(int row=0; row<m; row++){
            matrix[row][j] = 0;
        }
    }
}