tag:blogger.com,1999:blog-6314876008291942531.post8456129414279439167..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Given a matrix nxnUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-86424521687449626432012-10-17T08:33:14.958-07:002012-10-17T08:33:14.958-07:00for(int c=0; c < N; c++) {
for(int r=0; r <...for(int c=0; c < N; c++) {<br /> for(int r=0; r < N; r++) {<br /> if (A[r][c]==0) { markRow(A, r); markCol(A, c); }<br /> }<br />}<br /><br />for(int c=0; c < N; c++) {<br /> for(int r=0; r < N; r++) {<br /> if (isMarked(A, r, c)) { A[r][c] = 0; }<br /> }<br />}<br /><br />Now, the question is about what it means to mark a column/row. Some ideas:<br /><br />1) Assuming a positive matrix, to mark a cell means to replace the content with it's negative value. Then a cell is marked if it's content is negative.<br /><br />2) Assuming a matrix populated with references to Integer objects, mark a cell means set it to null.<br /><br />All these assumptions don't cover the case where the matrix contains any kind of primitive integer (positive or negative). In this case it is not possible to identify a "marker". An idea to cover this case is to use a support matrix of size NxN (let's call it B) that contains zeroes everywhere except in the cells corresponding to the cells in A that need to be be zeroed. The value of such cells in B will be equals to -1* A[r][c].<br /><br />Then the solution is A = A + B.<br /><br />Of course this solution not only require O(n^2) in time but also O(n^2) in space... pretty inefficient! <br /><br /><br />A second before to press the publish button I had this other idea which I think is good:<br /><br />List colsWithZeroes = new ArrayList();<br />for(int c=0; c < N; c++) {<br /> boolean foundZeroInRow = false;<br /> for(int r=0; r < N; r++) {<br /> if (A[r][c]==0) { <br /> foundZeroInRow = true;<br /> colsWithZeroes.add(c);<br /> zeroPrevInRow(A, r, c);<br /> zeroPrevInCol(A, r, c);<br /> continue;<br /> }<br /><br /> if (colsWithZeroes.contains(c) || foundZeroInRow) {<br /> A[r][c] = 0;<br /> continue;<br /> }<br />}<br /><br />zeroPrevInRow and zeroPrevInCol just set to zero the previous cells on the row or on the column.<br /><br />This algo is O(n^2).<br /><br />The main idea is to scan the matrix top-left to bottom-right. Every time a zero is found we say that a zero has been found on the current row. We zero all the *previous* elements on the current row and on the current column. We also add the current column to the list of columns containing a zero no matter the row. After these operations we move on the next element.<br /><br />If the current element is not zero, then either:<br /><br />1) zero the element if we found a zero previously on the row<br />2) zero the element if the current column is contained in the list of previous columns containing a zero<br />3) we leave the element as is if none of the previous conditions apply<br /><br />Thoughts?<br /><br />Claudio Corsihttps://www.blogger.com/profile/13435215356783747956noreply@blogger.com