Created
April 18, 2016 17:25
-
-
Save cruxrebels/c93f58760c7de3769886d2a80edc8b3e to your computer and use it in GitHub Desktop.
Given an m x n matrix of 0s and 1s, if an element is 0, set its entire row and column to 0. Do it in place. Example Given array A as 1 0 1 1 1 1 1 1 1 On returning, the array A should be : 0 0 0 1 0 1 1 0 1 Note that this will be evaluated on the extra memory used. Try to minimize the space and time complexity. Tags: InterviewBit Arrays Problem h…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void Solution::setZeroes(vector<vector<int> > &A) { | |
int nR = A.size(); | |
int nC = A[0].size(); | |
vector<int> r; | |
vector<int> c; | |
for(int i=0; i<nR; ++i) | |
{ | |
for (int j=0; j<nC; ++j) | |
{ | |
if (A[i][j] == 0) | |
{ | |
if (find(r.begin(), r.end(), i) == r.end()) | |
r.emplace_back(i); | |
if (find(c.begin(), c.end(), j) == c.end()) | |
c.emplace_back(j); | |
} | |
} | |
} | |
for (const auto& k : r) | |
{ | |
for (int x=0; x<nC; ++x) | |
{ | |
A[k][x] = 0; | |
} | |
} | |
for (const auto& l : c) | |
{ | |
for(int y=0; y<nR; ++y) | |
{ | |
A[y][l] = 0; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment