Set matrix zero

[keipour]

Issue: The currently given solution has time complexity of O(n^2*m + n*m^2) and space complexity of O(n*m):

Description: Assume that all the matrix is zero, then there will be n*m entries in rows and cols. As a result, the lower loop's complexity will be O(n*m*(n + m)) and the space complexity will be O(n * m).

Suggested Fix: To keep both the time and space complexity at the ones claimed at the bottom of the page, a possible fix would be having two loops at the top (instead of one):

        // find the index of rows with zero elements
        for(int r = 0; r < row; r++){
            for (int c = 0; c < col; c++){
                if (!matrix[r][c]){
                    rows.push_back(r);
                    break;
                }//if
            }// for c
        } // for r
        // find the index of cols with zero elements
        for(int c = 0; c < col; c++){
            for (int r = 0; r < row; r++){
                if (!matrix[r][c]){
                    cols.push_back(c);
                    continue;
                }//if
            }// for c
        } // for r

This way, each unique column or row will be added exactly once. Therefore, rows and cols may have different sizes and the bottom loop should change to:

        // go over the rows/cols and set to zero cross-shape on the zeros
        for (int i = 0; i < rows.size(); i++){
            for(int c = 0; c < col; c++)
                matrix[rows[i]][c] = 0;
        }
        for (int i = 0; i < cols.size(); i++){
            for(int r = 0; r < row; r++)
                matrix[r][cols[i]] = 0;
        }