DEV Community

Dev Nirwal
Dev Nirwal

Posted on

Leetcode: 73 Set Matrix Zeroes

Intuition

In a naive solution, we can keep track of all the rows and columns to be made zero.

Approach

In the naive solution, we can use hash sets or sets to keep track of rows and columns to make zero using one iteration. In the second phase, we can iterate through our sets to set the saved rows and columns to zero.

Space complexity for Naive Solution: O(M+N)
Naive solution code:

class Solution {
    public void setRowZero(int[][] matrix, int row){
        for(int i = 0;i<matrix[0].length;i++){
            matrix[row][i] = 0;
        }
   }
    public void setColZero(int[][] matrix, int col){
        for(int i = 0;i<matrix.length;i++){
            matrix[i][col] = 0;
        }
    }
    public void setZeroes(int[][] matrix) {
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        for(int i =0;i<matrix.length;i++){
            for(int j = 0;j<matrix[i].length;j++){
                if(matrix[i][j] == 0){
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }
        for(int ele: rowSet){
            setRowZero(matrix,ele);
        }
        for(int ele: colSet){
            setColZero(matrix,ele);
        }     
    }
}



Enter fullscreen mode Exit fullscreen mode

In the below solution which is optimized, I have marked the first row and first column if we encounter any zero in the submatrix

[ (1, rows): (1, cols) ]

We can use two boolean variables to keep track of the first row and first column for any zero.

Complexity

  • Time complexity: O(M * N)

  • Space complexity: O(1)

Code

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean first_row_has_zero = false;
        boolean first_col_has_zero = false;

        // check if first row has any zero
        for(int c = 0;c<cols;c++){
            if(matrix[0][c] == 0){
                first_row_has_zero = true;
                break;
            }
        }

        // check if first col has any zero
        for(int r = 0;r<rows;r++){
            if(matrix[r][0] == 0){
                first_col_has_zero = true;
                break;
            }
        }
        // checking for zero elsewhere and keeping track of it in the first row and first column
        for(int r = 1;r<rows;r++){
            for(int c = 1;c<cols;c++){
                if(matrix[r][c] == 0){
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }

        // checking and setting respcted row to zero
        for(int c = 1;c<cols; c++){
            if(matrix[0][c] == 0){
                for(int r = 0;r<rows;r++){
                    matrix[r][c] = 0;
                }
            }
        }

        // checking and setting respcted cols to zero
        for(int r = 1;r<rows; r++){
            if(matrix[r][0] == 0){
                for(int c = 0;c<cols;c++){
                    matrix[r][c] = 0;
                }
            }
        }

        if(first_row_has_zero == true){
            for(int c = 0;c<cols;c++){
                matrix[0][c] = 0;
            }
        }

        if(first_col_has_zero == true){
            for(int r = 0;r<rows;r++){
                matrix[r][0] = 0;
            }
        }

    }
}
Enter fullscreen mode Exit fullscreen mode

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

Hey reader!

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Okay let's go

Community matters

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay