Simple java O(m * n) solution with O(1) space


#1

Logic: Reuse first row and first column to record which column to clear out and which row to clear out respectively.

public class Solution {
    public void setZeroes(ArrayList<ArrayList<Integer>> a) {
        int m = a.size();
        int n = a.get(0).size();
        
        boolean firstRow = false;
        boolean firstColumn = false;
        
        // Check if first row contains any 0 element to clear out the first row at the end
        for (int j = 0; j < n; j++) {
            if (a.get(0).get(j) == 0) {
                firstRow = true;
                break;
            }
        }
        
        // Check if first column contains any 0 element to clear out the first column at the end
        for (int i = 0; i < m; i++) {
            if (a.get(i).get(0) == 0) {
                firstColumn = true;
                break;
            }
        }
        
        // If 0 is present in the matrix, then use first column and first row to record its presence
        for (int i = 1; i< m; i++) {
            for (int j = 1; j < n; j++) {
                if (a.get(i).get(j) == 0) {
                    a.get(0).set(j, 0);
                    a.get(i).set(0, 0);
                }
            }
        }
        
        // Use the first row and first column to see if that row or column needs to be cleared out
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (a.get(0).get(j) == 0 || a.get(i).get(0) == 0){
                    a.get(i).set(j, 0);
                }
            }
        }
        
        // If first row ORIGINALLY had any 0 element, then clear that out
        if (firstRow) {
            for (int j = 0; j < n; j++) {
                a.get(0).set(j, 0);
            }
        }
        
        // If first column ORIGINALLY had any 0 element, then clear that out
        if (firstColumn) {
            for (int i = 0; i < m; i++) {
                a.get(i).set(0, 0);
            }
        }
    }
}