Set Matrix Zeroes In Place in DSA Java - Build from Scratch

Set Matrix Zeroes In Place

📖 Scenario: Imagine you have a grid representing a garden with plants. Some spots have dead plants marked as zero. You want to mark the entire row and column of any dead plant as dead (zero) to prepare for replanting.

🎯 Goal: Build a program that updates the garden grid in place. If any spot is zero, set its entire row and column to zero without using extra space for another grid.

📋 What You'll Learn

Create a 2D integer array called garden with exact values

Create two boolean variables firstRowHasZero and firstColHasZero

Use the first row and first column of garden to mark rows and columns to be zeroed

Update the garden array in place based on these markers

Print the final state of garden row by row

💡 Why This Matters

🌍 Real World

This technique is useful in image processing, spreadsheets, and grid-based games where marking rows and columns efficiently is needed.

💼 Career

Understanding in-place matrix manipulation is important for software engineers working with data transformations, optimization, and memory-efficient algorithms.

1

Create the garden matrix

Create a 2D integer array called garden with these exact values:
{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}

DSA Java

// Create the garden matrix with given values
// Your code here

Hint

Use int[][] garden = {{...}, {...}, {...}}; to create the matrix.

2

Create flags for first row and column zeros

Create two boolean variables called firstRowHasZero and firstColHasZero and set both to false

DSA Java

int[][] garden = {
    {1, 1, 1},
    {1, 0, 1},
    {1, 1, 1}
};
// Create boolean flags for first row and column zeros
// Your code here

Hint

Use boolean firstRowHasZero = false; and boolean firstColHasZero = false;

3

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

Write code to check if the first row has zero and set firstRowHasZero accordingly. Then check if the first column has zero and set firstColHasZero. Next, use nested for loops with variables i and j starting from 1 to mark zeros in the first row and column of garden where zeros are found.

DSA Java

int[][] garden = {
    {1, 1, 1},
    {1, 0, 1},
    {1, 1, 1}
};
boolean firstRowHasZero = false;
boolean firstColHasZero = false;
// Check first row and first column for zeros
// Mark zeros in first row and column for other rows and columns
// Your code here

Hint

Use loops to check first row and column, then mark zeros in first row and column for other cells.

4

Set zeros in garden based on markers and print result

Use nested for loops with variables i and j starting from 1 to set garden[i][j] to zero if garden[i][0] or garden[0][j] is zero. Then, if firstRowHasZero is true, set all elements in the first row to zero. If firstColHasZero is true, set all elements in the first column to zero. Finally, print the garden matrix row by row, with elements separated by spaces.

DSA Java

int[][] garden = {
    {1, 1, 1},
    {1, 0, 1},
    {1, 1, 1}
};
boolean firstRowHasZero = false;
boolean firstColHasZero = false;

for (int j = 0; j < garden[0].length; j++) {
    if (garden[0][j] == 0) {
        firstRowHasZero = true;
        break;
    }
}

for (int i = 0; i < garden.length; i++) {
    if (garden[i][0] == 0) {
        firstColHasZero = true;
        break;
    }
}

for (int i = 1; i < garden.length; i++) {
    for (int j = 1; j < garden[0].length; j++) {
        if (garden[i][j] == 0) {
            garden[i][0] = 0;
            garden[0][j] = 0;
        }
    }
}
// Set zeros in garden based on markers
// Set zeros in first row and first column if needed
// Print the garden matrix row by row
// Your code here

Hint

Use loops to update the matrix based on markers, then print each row with spaces.

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