必要なメモリの計算

M×Nの行列について、要素が0であればその行と列の全てを0にするようなアルゴリズムを考えます。

「解法」
行列の全ての要素を順番に調べて、0があればその行と列を0にしていうだけの一見簡単そうに見えるアルゴリズムですが、その場で行と列を0で埋める処理をしてしまうと、あっという間に全ての要素が0になってしまうでしょう。

この問題を解決するにはもう一つ行列を用意し、0で埋める場所を記録していく方法が考えられますが、行列の全ての要素を２回走査する必要があります。このアルゴリズムではO(MN)のメモリが必要になります。

しかし、本当にO(MN)も必要なのでしょうか？答えはノーです。全ての列と行を0にセットするのですから、行列の詳細な要素を正確に追っていく必要はないのです。必要な情報は「二列目のどこかに０がある」とか「４行目のどこかに0がある」のようなことだけなのです。そして、0が含まれているわかっている列・行をとにかく０で埋めるだけ。

以下のコードは今説明したアルゴリズムを実装したものです。列と行のそれぞれに関しての配列を使い、それらに０が含まれるかどうかを記録しておきます。その情報をもとに、列か行に０が含まれていれば、そこを埋めていくのです。

Java
1public void setZeros(int[][] matrix) {
2        boolean[] row = new boolean[matrix.length];
3        boolean[] column = new boolean[matrix[0].length];
4
5        //0を含む行及び列のインデックスを保持
6        for(int i = 0;i < matrix.length;i++) {
7            for(int j = 0;j< matrix[0].length;j++) {
8                if(matrix[i][j] == 0) {
9                    row[i] = true;
10                    column[j] = true;
11                }
12            }
13        }
14
15        //行iまたは列jが0を含んでいれば、各要素を全て0にする
16        for(int i = 0;i < matrix.length;i++) {
17            for(int j = 0;j < matrix[0].length;j++) {
18                if(row[i]||column[j]) {
19                    matrix[i][j] = 0;
20                }
21            }
22        }
23    }

上の文章の「この問題を解決するにはもう一つ行列を用意し、0で埋める場所を記録していく方法が考えられますが、行列の全ての要素を２回走査する必要があります。このアルゴリズムではO(MN)のメモリが必要になります。」の部分がよくわかりません。
上に示したアルゴリズムでも二回走査していませんか？
また、

Java
1public void setZeros2(int[][] matrix) {
2        int[][] newMatrix = new int[matrix.length][];
3        for(int i = 0;i<matrix[0].length;i++){
4            newMatrix[i] = Arrays.copyOf(matrix[i], matrix[0].length);
5            
6            //以下ほぼ同様のコード
7        }
8
9    }