Set Matrix Zeroes In Place in DSA Java

Mental Model

When a cell in a matrix is zero, set its entire row and column to zero without using extra space.

Analogy: Imagine a grid of lights where if one light goes off, the entire row and column of lights must also turn off, but you only have one chance to mark which rows and columns to turn off without using extra boards.

Matrix before:
1 1 1
1 0 1
1 1 1

We mark row 1 and column 1 to be zeroed later.

Dry Run Walkthrough

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

Goal: Set entire row and column to zero for every zero cell, in place without extra matrix

Step 1: Check first row and first column for zeros to remember if they need zeroing

First row: 1 1 1
First column: 1 1 1

Why: We need to know if first row or column should be zeroed later since we use them as markers

Step 2: Traverse matrix from (1,1) to mark zeros in first row and column

Matrix after marking:
1 0 1
0 0 1
1 1 1

Why: Mark row 1 and column 1 as zero because matrix[1][1] is zero

Step 3: Use marks in first row and column to set zeros in matrix except first row and column

Matrix after zeroing inner cells:
1 0 1
0 0 0
1 0 1

Why: Zero rows and columns based on markers

Step 4: Zero first row if needed

Matrix after zeroing first row:
1 0 1
0 0 0
1 0 1

Why: First row had no zero originally, so no change

Step 5: Zero first column if needed

Matrix after zeroing first column:
1 0 1
0 0 0
1 0 1

Why: First column had no zero originally, so no change

Result:

1 0 1
0 0 0
1 0 1

Annotated Code

DSA Java

public class SetMatrixZeroes {
    public static void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

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

        // Check if first column has zero
        for (int r = 0; r < rows; r++) {
            if (matrix[r][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // Use first row and column as markers
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0; // mark row
                    matrix[0][c] = 0; // mark column
                }
            }
        }

        // Zero rows based on markers
        for (int r = 1; r < rows; r++) {
            if (matrix[r][0] == 0) {
                for (int c = 1; c < cols; c++) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Zero columns based on markers
        for (int c = 1; c < cols; c++) {
            if (matrix[0][c] == 0) {
                for (int r = 1; r < rows; r++) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Zero first row if needed
        if (firstRowZero) {
            for (int c = 0; c < cols; c++) {
                matrix[0][c] = 0;
            }
        }

        // Zero first column if needed
        if (firstColZero) {
            for (int r = 0; r < rows; r++) {
                matrix[r][0] = 0;
            }
        }
    }

    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1,1,1},
            {1,0,1},
            {1,1,1}
        };
        setZeroes(matrix);
        printMatrix(matrix);
    }
}

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

Check if first row contains zero to zero it later

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

Check if first column contains zero to zero it later

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; } } }

Mark rows and columns to be zeroed using first row and column

for (int r = 1; r < rows; r++) { if (matrix[r][0] == 0) { for (int c = 1; c < cols; c++) { matrix[r][c] = 0; } } }

Zero rows based on markers

for (int c = 1; c < cols; c++) { if (matrix[0][c] == 0) { for (int r = 1; r < rows; r++) { matrix[r][c] = 0; } } }

Zero columns based on markers

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

Zero first row if needed

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

Zero first column if needed

Output

1 0 1 

0 0 0 

1 0 1 

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each cell is visited a constant number of times

Space: O(1) because we use the matrix itself for marking without extra space

vs Alternative: Naive approach uses extra space O(m+n) for row and column markers, this approach saves space by using first row and column as markers

Edge Cases

Matrix with no zeros

Matrix remains unchanged

DSA Java

if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; }

Matrix with zero in first row or first column

First row or column is zeroed at the end using boolean flags

DSA Java

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

Matrix with all zeros

Entire matrix remains zeros

DSA Java

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; } } }

When to Use This Pattern

When you need to modify a matrix in place based on zero cells affecting entire rows and columns, use the marker-in-first-row-and-column pattern to save space.

Common Mistakes

Mistake: Zeroing rows and columns immediately when a zero is found, corrupting the matrix before finishing scanning
Fix: First mark rows and columns using first row and column, then zero after scanning entire matrix

Mistake: Not handling zeros in first row or first column separately
Fix: Use separate boolean flags to track if first row or column need zeroing

Summary

Sets entire row and column to zero for each zero cell in the matrix, modifying it in place.

Use when you must zero rows and columns without extra space beyond the matrix itself.

Use the first row and column as markers to remember which rows and columns to zero later.

Practice

1. What is the main goal of the Set Matrix Zeroes In Place problem?

easy

A. Count the number of zero elements in the matrix.

B. Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space.

C. Sort each row of the matrix in ascending order.

D. Find the sum of all elements in the matrix.

Solution

1. Step 1: Understand the problem requirement

   The problem asks to set entire rows and columns to zero if any element in them is zero, modifying the matrix directly.

2. Step 2: Recognize the constraint of in-place modification

   We must do this without using extra space for another matrix or large data structures.

3. Final Answer:

   Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space. -> Option B

4. Quick Check:

   Goal = Set rows and columns to zero in-place [OK]

Hint: Remember: zero means zero entire row and column in-place [OK]

Common Mistakes:

• Using extra space like another matrix
• Only zeroing rows or columns, not both
• Not modifying the matrix in-place

2. Which of the following Java code snippets correctly declares a 2D integer matrix named matrix with 3 rows and 4 columns?

easy

A. int[][] matrix = new int[3][4];

B. int matrix[][] = new int[4][3];

C. int matrix[3][4];

D. int matrix = new int[3][4];

Solution

1. Step 1: Recall Java 2D array declaration syntax

   In Java, 2D arrays are declared as int[][] name = new int[rows][columns];.

2. Step 2: Match the correct dimensions

   int[][] matrix = new int[3][4]; uses 3 rows and 4 columns correctly. int matrix[][] = new int[4][3]; reverses dimensions, C is invalid syntax, D misses array brackets.

3. Final Answer:

   int[][] matrix = new int[3][4]; -> Option A

4. Quick Check:

   Java 2D array syntax = int[][] matrix = new int[3][4]; [OK]

Hint: Use int[][] for 2D arrays with new int[rows][cols] [OK]

Common Mistakes:

• Swapping rows and columns in new int[][]
• Using C-style array declaration
• Missing brackets in declaration

3. What will be the state of the matrix after running the following Java code snippet for setting matrix zeroes in place?

int[][] matrix = {
  {1, 2, 0},
  {4, 5, 6},
  {7, 0, 9}
};

// After applying setZeroes(matrix) method
// (method sets entire row and column to zero if element is zero)

medium

A. [[0, 0, 0], [4, 0, 0], [0, 0, 0]]

B. [[1, 0, 0], [4, 0, 0], [0, 0, 0]]

C. [[0, 0, 0], [4, 5, 0], [0, 0, 0]]

D. [[0, 2, 0], [4, 0, 6], [0, 0, 0]]

Solution

1. Step 1: Identify zero elements and their rows and columns

   Zeros are at positions (0,2) and (2,1). Rows 0 and 2, columns 1 and 2 must be zeroed.

2. Step 2: Set entire rows and columns to zero

   Row 0 becomes [0,0,0], row 2 becomes [0,0,0]. Column 1 and 2 in row 1 become 0, so row 1 becomes [4,0,0].

3. Final Answer:

   [[0, 0, 0], [4, 0, 0], [0, 0, 0]] -> Option A

4. Quick Check:

   Zero rows and columns set correctly = [[0, 0, 0], [4, 0, 0], [0, 0, 0]] [OK]

Hint: Mark zero rows and columns first, then update matrix [OK]

Common Mistakes:

• Only zeroing rows or columns, not both
• Not updating all affected cells
• Overwriting zeros too early

4. Consider this buggy Java code snippet for setting matrix zeroes in place:

public void setZeroes(int[][] matrix) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  boolean[] rowZero = new boolean[rows];
  boolean[] colZero = new boolean[cols];

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (matrix[i][j] == 0) {
        rowZero[i] = true;
        colZero[j] = true;
      }
    }
  }

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (rowZero[i] || colZero[j]) {
        matrix[i][j] = 0;
      }
    }
  }
}

What is the main issue with this code regarding the problem constraints?

medium

A. It modifies the matrix before checking all zeros, causing incorrect results.

B. It does not correctly identify zero elements in the matrix.

C. It causes an ArrayIndexOutOfBoundsException.

D. It uses extra space proportional to rows and columns, violating in-place requirement.

Solution

1. Step 1: Analyze space usage of the code

   The code uses two boolean arrays, rowZero and colZero, sized by rows and columns, which is extra space.

2. Step 2: Compare with problem constraints

   The problem requires in-place modification without extra space, so using these arrays violates the constraint.

3. Final Answer:

   It uses extra space proportional to rows and columns, violating in-place requirement. -> Option D

4. Quick Check:

   Extra space used = violates in-place [OK]

Hint: Avoid extra arrays; use matrix first row/column as markers [OK]

Common Mistakes:

• Ignoring space constraints
• Using extra arrays for marking
• Not handling first row/column carefully

5. You have a 4x4 matrix:

1 2 3 4
5 0 7 8
9 10 11 12
0 14 15 16

Using the in-place method for setting matrix zeroes, what will be the matrix after the operation?

hard

A. [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 15, 16]]

B. [[0, 0, 0, 4], [0, 0, 0, 0], [0, 0, 0, 12], [0, 0, 0, 0]]

C. [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]]

D. [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Solution

1. Step 1: Identify zero positions and mark rows and columns

   Zeros at (1,1) and (3,0). Rows 1 and 3, columns 0 and 1 must be zeroed.

2. Step 2: Set zeros for affected rows and columns

   Rows 1 and 3 become entirely zeros. Columns 0 and 1 become zeros across all rows, resulting in row 0: [0,0,3,4]; row 2: [0,0,11,12].

3. Final Answer:

   [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] -> Option C

4. Quick Check:

   Zero rows and columns updated correctly = [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] [OK]

Hint: Mark first row/column, then update matrix carefully [OK]

Common Mistakes:

• Zeroing entire rows or columns unnecessarily
• Missing zeros in some cells
• Not handling first row and column markers properly