Set Matrix Zeroes

Problem Description
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Solution
At first, I came up with a solution: using the first column and first row to store the information about a row or column should be zero. However, the code is very ugly (See Appendix A). Later, I improved the code by use only the row that we first met an zero to store information about whether the column should be zero. Below is the clean code.

view plainprint?

1. public class Solution {  
2.     public void setZeroes(int[][] matrix) {  
3.   
4.         int m = -1;  
5.         for(int i = 0; i<matrix.length; i++){  
6.             boolean foundZero = false;  
7.             for(int j=0; j<matrix[i].length; j++){  
8.                 if(matrix[i][j] == 0){  
9.                     foundZero = true;  
10.                     break;  
11.                 }  
12.             }  
13.             if(foundZero && m==-1){  
14.                 m = i;  
15.                 continue;  
16.             }  
17.             if(foundZero){  
18.                 for(int j =0;j<matrix[i].length; j++){  
19.                     if(matrix[i][j] == 0) matrix[m][j] = 0;  
20.                     matrix[i][j] = 0;  
21.                 }  
22.             }  
23.         }  
24.         if(m!= -1){  
25.             for(int j = 0; j<matrix[m].length; j++){  
26.                 if(matrix[m][j] == 0)  
27.                 for(int i =0; i<matrix.length; i++)  
28.                     matrix[i][j] = 0;  
29.                 matrix[m][j] = 0;  
30.             }  
31.         }  
32.     }  
33. }  

public class Solution {
    public void setZeroes(int[][] matrix) {

        int m = -1;
        for(int i = 0; i<matrix.length; i++){
            boolean foundZero = false;
            for(int j=0; j<matrix[i].length; j++){
                if(matrix[i][j] == 0){
                    foundZero = true;
                    break;
                }
            }
            if(foundZero && m==-1){
                m = i;
                continue;
            }
            if(foundZero){
                for(int j =0;j<matrix[i].length; j++){
                    if(matrix[i][j] == 0) matrix[m][j] = 0;
                    matrix[i][j] = 0;
                }
            }
        }
        if(m!= -1){
            for(int j = 0; j<matrix[m].length; j++){
                if(matrix[m][j] == 0)
                for(int i =0; i<matrix.length; i++)
                    matrix[i][j] = 0;
                matrix[m][j] = 0;
            }
        }
    }
}

Appendix A: How ugly it was

view plainprint?

1. public class Solution {  
2.     public void setZeroes(int[][] matrix) {  
3.           
4.         boolean firstRowZero = false;  
5.         boolean firstColZero = false;  
6.           
7.         for(int i =0; i<matrix.length; i++)  
8.             if(matrix[i][0] == 0) {  
9.                 firstColZero = true;  
10.                 break;  
11.             }  
12.               
13.         for(int i =0; i<matrix[0].length; i++)  
14.             if(matrix[0][i] == 0) {  
15.                 firstRowZero = true;  
16.                 break;  
17.             }  
18.                   
19.         for(int i = 1; i<matrix.length; i++){  
20.             for(int j = 1; j<matrix[0].length; j++){  
21.                 if(matrix[i][j] == 0){  
22.                     matrix[i][0] = 0;  
23.                     matrix[0][j] = 0;  
24.                 }  
25.             }  
26.         }  
27.           
28.         for(int i=1; i<matrix.length; i++){  
29.             if(matrix[i][0] == 0)  
30.             for(int j=1; j<matrix[0].length; j++){  
31.                 matrix[i][j] = 0;  
32.             }  
33.         }  
34.         for(int i=1; i<matrix[0].length; i++){  
35.             if(matrix[0][i] == 0)  
36.             for(int j=1; j<matrix.length; j++){  
37.                 matrix[j][i] = 0;  
38.             }  
39.         }  
40.           
41.         if (firstRowZero)  
42.             for(int i =0; i<matrix[0].length; i++)  
43.                 matrix[0][i] = 0;  
44.         if (firstColZero)  
45.             for(int i=0; i<matrix.length; i++)  
46.                 matrix[i][0] = 0;  
47.     }  
48. }  

public class Solution {
    public void setZeroes(int[][] matrix) {
        
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        for(int i =0; i<matrix.length; i++)
            if(matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
            
        for(int i =0; i<matrix[0].length; i++)
            if(matrix[0][i] == 0) {
                firstRowZero = true;
                break;
            }
                
        for(int i = 1; i<matrix.length; i++){
            for(int j = 1; j<matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(int i=1; i<matrix.length; i++){
            if(matrix[i][0] == 0)
            for(int j=1; j<matrix[0].length; j++){
                matrix[i][j] = 0;
            }
        }
        for(int i=1; i<matrix[0].length; i++){
            if(matrix[0][i] == 0)
            for(int j=1; j<matrix.length; j++){
                matrix[j][i] = 0;
            }
        }
        
        if (firstRowZero)
            for(int i =0; i<matrix[0].length; i++)
                matrix[0][i] = 0;
        if (firstColZero)
            for(int i=0; i<matrix.length; i++)
                matrix[i][0] = 0;
    }
}

Appendix B: Python Code for the good solution

view plainprint?

1. class Solution(object):  
2.     def setZeroes(self, matrix):  
3.         """ 
4.         :type matrix: List[List[int]] 
5.         :rtype: void Do not return anything, modify matrix in-place instead. 
6.         """  
7.         m = -1  
8.         for i in range(len(matrix)):  
9.             found = False  
10.             for j in range(len(matrix[0])):  
11.                 if matrix[i][j] == 0:  
12.                     found = True  
13.                     break  
14.             if found and m==-1:  
15.                 m = i  
16.                 continue  
17.             if found:  
18.                 for j in range(len(matrix[i])):  
19.                     if matrix[i][j] == 0:  
20.                         matrix[m][j] = 0  
21.                     matrix[i][j] = 0  
22.           
23.         if m!=-1:          
24.             for j in range(len(matrix[m])):  
25.                 if matrix[m][j] == 0:  
26.                     for i in range(0, len(matrix)):  
27.                         matrix[i][j] = 0  
28.                 matrix[m][j] = 0  

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        m = -1
        for i in range(len(matrix)):
            found = False
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    found = True
                    break
            if found and m==-1:
                m = i
                continue
            if found:
                for j in range(len(matrix[i])):
                    if matrix[i][j] == 0:
                        matrix[m][j] = 0
                    matrix[i][j] = 0
        
        if m!=-1:        
            for j in range(len(matrix[m])):
                if matrix[m][j] == 0:
                    for i in range(0, len(matrix)):
                        matrix[i][j] = 0
                matrix[m][j] = 0