Set Matrix Zeroes

Question: Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

You may view the full question here.

Approach 1: Let’s start with a naive approach — 1. Scan all the elements in the matrix and store all the rows and columns where you encounter a zero. 2. Write zeroes into the rows and columns that have been marked in the previous step.

//Approach 1
//Runtime: 4
//Memory usage: 44MB
class Solution {
    public void setZeroes(int[][] matrix) {
        HashMap<Integer, Integer> rowMap = new HashMap();
        HashMap<Integer, Integer> colMap = new HashMap();
        
        for(int r = 0; r<matrix.length; r++){
            for(int c = 0; c<matrix[0].length; c++){
                if(matrix[r][c]==0){
                    if(!rowMap.containsKey(r)){
                        rowMap.put(r, 1);
                    }
                    if(!colMap.containsKey(c)){
                        colMap.put(c, 1);
                    }
                }
            }
        }
        for(int r = 0; r<matrix.length; r++){
            for(int c = 0; c<matrix[0].length; c++){
                if(rowMap.containsKey(r)||colMap.containsKey(c)){
                    matrix[r][c] = 0;
                }
            }
        }
    }
}

Approach 2: Optimized a little bit by traversing through only those rows and columns that need to be set to zero.

//Approach 2
//Runtime: 3ms
//Memory usage: 44.9MB
class Solution {
    public void setZeroes(int[][] matrix) {
        HashMap<Integer, Integer> rowMap = new HashMap();
        HashMap<Integer, Integer> colMap = new HashMap();
        
        for(int r = 0; r<matrix.length; r++){
            for(int c = 0; c<matrix[0].length; c++){
                if(matrix[r][c]==0){
                    if(!rowMap.containsKey(r)){
                        rowMap.put(r, 1);
                    }
                    if(!colMap.containsKey(c)){
                        colMap.put(c, 1);
                    }
                }
            }
        }
        for(int r : rowMap.keySet()){
            for(int c = 0; c<matrix[0].length; c++){
                matrix[r][c] = 0;
            }
        }
        
        for(int c : colMap.keySet()){
            for(int r = 0; r<matrix.length; r++){
                matrix[r][c] = 0;
            }
        }
    }
}

Find more posts here.

Cheers & Chao!