<p>Given an <code>m x n</code> integer matrix <code>matrix</code>, if an element is <code>0</code>, set its entire row and column to <code>0</code>&#39;s.</p>

<p>You must do it <a href="https://en.wikipedia.org/wiki/In-place_algorithm" target="_blank">in place</a>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg" style="width: 450px; height: 169px;" />
<pre>
<strong>Input:</strong> matrix = [[1,1,1],[1,0,1],[1,1,1]]
<strong>Output:</strong> [[1,0,1],[0,0,0],[1,0,1]]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg" style="width: 450px; height: 137px;" />
<pre>
<strong>Input:</strong> matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
<strong>Output:</strong> [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[0].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>-2<sup>31</sup> &lt;= matrix[i][j] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong></p>

<ul>
	<li>A straightforward solution using <code>O(mn)</code> space is probably a bad idea.</li>
	<li>A simple improvement uses <code>O(m + n)</code> space, but still not the best solution.</li>
	<li>Could you devise a constant space solution?</li>
</ul>

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

        // a better approach is to store the index of those rows and columns which going to be zero and then run a loop to make them 0;

        // a optimize approach then the previous better approach is that instead of creating new arrays for row anc col which stores which index should be 0, we will make the first row and first column of the matrix act as a col arr and row arr
        // issue 1 : m[0,0] will be used as twice in both arrs, don't use m[0,0], use col0 and row0
        // issue 2 : since first row and col are now acting a arr which indicates whether m[i,j] should be zero or not, we will face errors if we update values of the first columns and rows, to solve this we will first set values of matrix from m[1][1] to m[m-1][n-1]
        // once m[1,1] to m[m-1,n-1] are updated, now update the m[0,0] , first row and first col,

    

        int r_size= m.size(), c_size = m.at(0).size();
        int col0=1,row0=1;

        // vector<int> row(r_size,0); // m[i,0] --> first column acts as a row array, row0
        // vector<int> col(c_size,0); // m[0,j] --> first row acts as a col array, col0

        for(int i=0;i<r_size;i++) {  // loop to set which row and col arrs index to be set to zero
            for(int j=0;j<c_size;j++) {
                if(m[i][j] == 0) {
                    if(i!=0) m[i][0] = 0;
                    else row0 = 0;

                    if(j!=0) m[0][j] = 0;
                    else col0 = 0;
                }
            }
        }

        for(int i=1;i<r_size;i++) {  /// loop to set the values of m[1,1] to m[m-1,n-1]
            for(int j=1;j<c_size;j++) {
                if(m[i][j] != 0) {
                    if(m[i][0] == 0 || m[0][j] == 0) {
                        m[i][j] = 0;
                    }
                }
            }
        }

        if(col0==0 || row0==0) m[0][0] = 0; // update the m[0,0] baed on col0 and row0

        if(row0 == 0) {
            for(int i=c_size-1;i>0;i--) { // loop to set the first row from m[0,n-1] to m[0,1]
                        m[0][i]=0;
            } 
        }

        if(col0 == 0) {
            for(int i=r_size-1;i>0;i--) { // loop to set the first column from m[m-1,0] to m[1,0]
                        m[i][0]=0;
            }
        }       
    }
};
16600