# C++, O(1)-space-solution

• ``````class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
int m = matrix.size();
if (m == 0) {
return;
}
int n = matrix[0].size();
int R = -1, C = -1;			// to store the 0 rows and column;
int i, j, k;
int store_found = false;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (matrix[i][j] == 0 && i != R && j != C) {
if (!store_found) {
R = i;
C = j;
store_found = true;
for (k = 0; k < n; k++) {			// mark the R-row
if (matrix[R][k] == 0) {
matrix[R][k] = -1;
}
else {
matrix[R][k] = 0;
}
}
for (k = 0; k < m; k++) {			// mark the C-clolumn
if (k == R) {
continue;
}
if (matrix[k][C] == 0 && k != R) {
matrix[k][C] = -1;
}
else {
matrix[k][C] = 0;
}
}
}
else {
matrix[i][C] = -1;
matrix[R][j] = -1;
}
}
}
}

if (!store_found){
return;
}

for (i = 0; i < m; i++){				// set marked row to be zero
if (matrix[i][C] == -1) {
for (k = 0; k < n; k++) {
if (i == R || k == C) {
continue;
}
matrix[i][k] = 0;
}
}
}

for (j = 0; j < n; j++){				// set marked column to be zero
if (matrix[R][j] == -1) {
for (k = 0; k < m; k++) {
if (j == C || k == R) {
continue;
}
matrix[k][j] = 0;
}
}
}

for (k = 0; k < n;k++){					// set the store row and column to be zero
matrix[R][k] = 0;
}
for (k = 0; k < m; k++){
matrix[k][C] = 0;
}
}
};``````

• What's the run-time like? I took a similar approach (show below), run-time is pretty horrible.

``````class Solution {
public:
// Store the rows, columns that are to be zeroed out in the first column, row respectively.
// Store whether the first row and column contained zero in two additional boolean variables.
// O(1) space solution

void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();

if(m == 0)
{
return;
}

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

if(n == 0)
{
return;
}

bool col_has_zero = false;
bool row_has_zero = false;

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

if(j == 0)
{
col_has_zero = true;
}

matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}

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

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

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

• the elements is non-negative?

• I don't see that specified in the question. I also had a similar idea, but I didnt make the assumption that -1 is not among the input values:-

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();//2
if(m == 0)return;
int n = matrix[0].size();//6
int store_row = -1;
int store_col = -1;
for(int i = 0;i < m;i++) {
for(int j = 0;j < n;j++) {
if(matrix[i][j] == 0) {
if(store_row == -1) {
store_row = i;//0
store_col = j;//2
}
else {
matrix[store_row][j] = 0;//matrix[0][5] = 0
matrix[i][store_col] = 0;//matrix[1][2] = 0
}
}
}
}
if(store_row == -1) return;
for(int j = 0;j < n;j++) {
if(matrix[store_row][j] == 0 && j != store_col) fill_col_with_zeroes(matrix, j);
}
for(int i = 0;i < m;i++) {
if(matrix[i][store_col] == 0 && i != store_row) fill_row_with_zeroes(matrix, i);
}
fill_row_with_zeroes(matrix, store_row);
fill_col_with_zeroes(matrix, store_col);
}

void fill_row_with_zeroes(vector<vector<int> >& v, int r) {
for(int i = 0;i < v[0].size();i++) {
v[r][i] = 0;
}
}

void fill_col_with_zeroes(vector<vector<int> >& v, int c) {
for(int i = 0;i < v.size();i++) {
v[i][c] = 0;
}

}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.