/*
 * Copyright (C) 2014 Pedro Vicente Gómez Sánchez.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.pedrovgs.problem55;

/**
 * Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are
 * set to 0.
 *
 * @author Pedro Vicente Gómez Sánchez.
 */
public class RewriteRowAndColumnsWithZeros {

  public void rewrite(int[][] matrix) {
    validateInput(matrix);
  }

  private void validateInput(int[][] matrix) {
    if (matrix == null) {
      throw new IllegalArgumentException("You can't pass a null insntace as input parameter.");
    }
  }
}

@@ -645,16 +645,65 @@
 lem55;%0A%0A
+import java.util.HashSet;%0Aimport java.util.Set;%0A%0A
 /**%0A * W
@@ -909,70 +909,1569 @@
 %0A%0A  
-public void rewrite(int%5B%5D%5B%5D matrix) %7B%0A    validateInput(matrix
+/**%0A   * Iterative algorithm. The complexity order of this solution in time terms is equals to O(N*M)%0A   * where N and M are the height and width of the matrix. In space terms, the complexity order of%0A   * this algorithm has a linear relation to the number of zeros in the matrix and the size of%0A   * this, at the end, equals to O(N*M) because we are using two auxiliary data structures to keep%0A   * temporal data which is going to grow following a linear relation to the matrix size.%0A   */%0A  public void rewrite(int%5B%5D%5B%5D matrix) %7B%0A    validateInput(matrix);%0A%0A    Set%3CInteger%3E rowsToSkip = new HashSet%3CInteger%3E();%0A    Set%3CInteger%3E columnsToSkip = new HashSet%3CInteger%3E();%0A    for (int i = 0; i %3C matrix.length; i++) %7B%0A      for (int j = 0; j %3C matrix%5Bi%5D.length; j++) %7B%0A        if (shouldPaintRowAndColumn(matrix, i, j, rowsToSkip, columnsToSkip)) %7B%0A          rewriteRow(matrix, i, rowsToSkip);%0A          rewriteColumn(matrix, j, columnsToSkip);%0A        %7D%0A      %7D%0A    %7D%0A  %7D%0A%0A  private void rewriteRow(int%5B%5D%5B%5D matrix, int i, Set%3CInteger%3E rowsToSkip) %7B%0A    rowsToSkip.add(i);%0A    for (int x = 0; x %3C matrix.length; x++) %7B%0A      matrix%5Bi%5D%5Bx%5D = 0;%0A    %7D%0A  %7D%0A%0A  private void rewriteColumn(int%5B%5D%5B%5D matrix, int j, Set%3CInteger%3E columnsToSkip) %7B%0A    columnsToSkip.add(j);%0A    for (int y = 0; y %3C matrix%5Bj%5D.length; y++) %7B%0A      matrix%5By%5D%5Bj%5D = 0;%0A    %7D%0A  %7D%0A%0A  private boolean shouldPaintRowAndColumn(int%5B%5D%5B%5D matrix, int i, int j, Set%3CInteger%3E rowsToSkip,%0A      Set%3CInteger%3E columnsToSkip) %7B%0A    return matrix%5Bi%5D%5Bj%5D == 0 && !rowsToSkip.contains(i) && !columnsToSkip.contains(j
 );%0A 

Add iterative solution to problem 55