Posts Set Matrix Zeroes (InterviewBit)
Post
Cancel

Set Matrix Zeroes (InterviewBit)

This question is part of NeetCode150 series.

Problem Description

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place.

leetcode

Solution

APPROACH 1

Space Complexity: O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

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

        int n = matrix.length;
        int m = matrix[0].length;

        //we will use these two arrays to track if that particular row/column needs to be marked
        int[] rows = new int[n];
        int[] columns = new int[m];

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j] == 0){
                    rows[i] = 1;
                    columns[j] = 1;
                }
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(rows[i] == 1 || columns[j] == 1) matrix[i][j] = 0;
            }
        }

    }

}

APPROACH 2

NeetCode YouTube

The above approach is not in-place as we used extra space. Instead of maintaining two new arrays to track which rows and columns need to be updated, we can do it using first row and first column. The first cell is an overlap. So, we will use one extra variable for the first row.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {

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

        int n = matrix.length;
        int m = matrix[0].length;

        boolean firstRow = false;

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j] == 0){

                    matrix[0][j] = 0;

                    if(i == 0){
                        firstRow = true;
                    }else{
                        matrix[i][0] = 0;
                    }

                }
            }
        }

        for(int i=1; i<n; i++){
            for(int j=1; j<m; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }

        //first column
        if(matrix[0][0] == 0){
            for(int i=0; i<n; i++){
                matrix[i][0] = 0;
            }
        }

        //first row
        if(firstRow == true){
            for(int i=0; i<m; i++){
                matrix[0][i] = 0;
            }
        }

    }

}
This post is licensed under CC BY 4.0 by the author.