cpp-codes/Array_Leetcode_Set_Matrix_Zeros_73.cpp at master · abhinavkumaryadav1/cpp-codes · 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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*
73. Set Matrix Zeroes

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
-231 <= matrix[i][j] <= 231 - 1
*/

//Brute force (will fail if test case include the -ve number which you are setting in matrix)
// TC: O(M∗N∗(M+N))

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

      int m=matrix.size();
      int n=matrix[0].size();


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

            matrix[i][j] = -1608;


              int col=j;
              int row=i;

              //for columm
              for(int i=0;i<m;i++)
              {
                if(matrix[i][col] != 0 && matrix[i][col] != -1608) {

                 matrix[i][col] = -1608;
                }

              }

              //for row
              for(int i=0;i<n;i++)
              {
              if(matrix[row][i] != 0 && matrix[row][i] != -1608)
               {
                 matrix[row][i] = -1608;
              }

              }

          }
        }
      }

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

    }
};

//Better Approch : TC: O(M*N) : SC is still high

        // vector<int> row(m, 0);

        // vector<int> col(n, 0);


        // for(int i =0; i<m ; i++)
        // {
        //   for(int j=0;j<n;j++)
        //   {
        //     if(matrix[i][j] == 0)
        //     {
             // row[i]++; // jaha bhi mile 0 uska row aur col mark kar do aur baad me reiterate karke un har row col me 0 set kardo
        //       col[j]++;
        //     }
        //   }
        // }

      // for(int i =0; i<m ; i++)
      //   {
      //     for(int j=0;j<n;j++)
      //     {
      //       if(row[i]>0 || col[j]>0)
      //       {
      //         matrix[i][j] =0;
      //       }
      //     }
      //   }

        //Optimal Approch:

        int col0 =1;
        for(int i =0; i<m ; i++)
        {
          for(int j=0;j<n;j++)
          {
            if(matrix[i][j] == 0)
            {
              matrix[i][0]=0; //making matrix first row as Marking array
              if(j!=0)
              {
              matrix[0][j]=0; //making matrix first col as Marking array
              }
              else col0 =0;
            }
          }
        }

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

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

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