Tuesday, October 16, 2012

Given a matrix nxn

Zero all the columns and rows which contains at least one zero.

1 comment:

  1. for(int c=0; c < N; c++) {
    for(int r=0; r < N; r++) {
    if (A[r][c]==0) { markRow(A, r); markCol(A, c); }
    }
    }

    for(int c=0; c < N; c++) {
    for(int r=0; r < N; r++) {
    if (isMarked(A, r, c)) { A[r][c] = 0; }
    }
    }

    Now, the question is about what it means to mark a column/row. Some ideas:

    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.

    2) Assuming a matrix populated with references to Integer objects, mark a cell means set it to null.

    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].

    Then the solution is A = A + B.

    Of course this solution not only require O(n^2) in time but also O(n^2) in space... pretty inefficient!


    A second before to press the publish button I had this other idea which I think is good:

    List colsWithZeroes = new ArrayList();
    for(int c=0; c < N; c++) {
    boolean foundZeroInRow = false;
    for(int r=0; r < N; r++) {
    if (A[r][c]==0) {
    foundZeroInRow = true;
    colsWithZeroes.add(c);
    zeroPrevInRow(A, r, c);
    zeroPrevInCol(A, r, c);
    continue;
    }

    if (colsWithZeroes.contains(c) || foundZeroInRow) {
    A[r][c] = 0;
    continue;
    }
    }

    zeroPrevInRow and zeroPrevInCol just set to zero the previous cells on the row or on the column.

    This algo is O(n^2).

    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.

    If the current element is not zero, then either:

    1) zero the element if we found a zero previously on the row
    2) zero the element if the current column is contained in the list of previous columns containing a zero
    3) we leave the element as is if none of the previous conditions apply

    Thoughts?

    ReplyDelete