Set Matrix Zeroes

                                            
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        bool firstRowZero = false;
        bool firstColZero = false;
        
        // Check if first row has zero
        for(int j=0; j<n; j++){
            if(matrix[0][j] == 0){
                firstRowZero = true;
                break;
            }
        }
        
        // Check if first column has zero
        for(int i=0; i<m; i++){
            if(matrix[i][0] == 0){
                firstColZero = true;
                break;
            }
        }
        
        // Mark zeros on first row and column
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Set elements to zero based on first row and column
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Set first row to zero
        if(firstRowZero){
            for(int j=0; j<n; j++){
                matrix[0][j] = 0;
            }
        }
        
        // Set first column to zero
        if(firstColZero){
            for(int i=0; i<m; i++){
                matrix[i][0] = 0;
            }
        }
    }
};

                                            
class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) firstRowZero = true;
                    if (j == 0) firstColZero = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

                                            
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        m, n = len(matrix), len(matrix[0])
        row_zero, col_zero = False, False
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    if i == 0:
                        row_zero = True
                    if j == 0:
                        col_zero = True
                    matrix[0][j] = 0
                    matrix[i][0] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        if row_zero:
            for j in range(n):
                matrix[0][j] = 0
        
        if col_zero:
            for i in range(m):
                matrix[i][0] = 0

                                            
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = *matrixColSize;
    bool firstRowZero = false;
    bool firstColZero = false;

    // Check if the first row contains zero
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }

    // Check if the first column contains zero
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }

    // Mark zeros on first row and first column
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Set zeros based on marks in first row and first column
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // Set zeros for the first row if needed
    if (firstRowZero) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }

    // Set zeros for the first column if needed
    if (firstColZero) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
}

                                            
public class Solution {
    public void SetZeroes(int[][] matrix) {
        bool firstRowHasZero = false;
        bool firstColHasZero = false;

        // Check if the first row has zero
        for (int j = 0; j < matrix[0].Length; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Check if the first column has zero
        for (int i = 0; i < matrix.Length; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // Mark zeros on first row and column
        for (int i = 1; i < matrix.Length; i++) {
            for (int j = 1; j < matrix[0].Length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Set zeros based on first row and column markers
        for (int i = 1; i < matrix.Length; i++) {
            for (int j = 1; j < matrix[0].Length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Set zeros for the first row if needed
        if (firstRowHasZero) {
            for (int j = 0; j < matrix[0].Length; j++) {
                matrix[0][j] = 0;
            }
        }

        // Set zeros for the first column if needed
        if (firstColHasZero) {
            for (int i = 0; i < matrix.Length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

                                            
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    
    let firstRowZero = false;
    let firstColZero = false;
    
    for(let i = 0; i < rows; i++) {
        for(let j = 0; j < cols; j++) {
            if(matrix[i][j] === 0) {
                if(i === 0) firstRowZero = true;
                if(j === 0) firstColZero = true;
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    
    for(let i = 1; i < rows; i++) {
        for(let j = 1; j < cols; j++) {
            if(matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    if(firstRowZero) {
        for(let j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }
    
    if(firstColZero) {
        for(let i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
};

                                            
function setZeroes(matrix: number[][]): void {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let firstRowHasZero = false;
    let firstColHasZero = false;
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === 0) {
                if (i === 0) firstRowHasZero = true;
                if (j === 0) firstColHasZero = true;
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    if (firstRowHasZero) {
        for (let j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }
    
    if (firstColHasZero) {
        for (let i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
}

                                            
class Solution {
    /**
     * @param Integer[][] $matrix
     */
    function setZeroes(&$matrix) {
        $row = count($matrix);
        $col = count($matrix[0]);
        
        $col0 = false;
        
        for ($i = 0; $i < $row; $i++) {
            if ($matrix[$i][0] == 0) {
                $col0 = true;
            }
            for ($j = 1; $j < $col; $j++) {
                if ($matrix[$i][$j] == 0) {
                    $matrix[$i][0] = 0;
                    $matrix[0][$j] = 0;
                }
            }
        }
        
        for ($i = $row - 1; $i >= 0; $i--) {
            for ($j = $col - 1; $j >= 1; $j--) {
                if ($matrix[$i][0] == 0 || $matrix[0][$j] == 0) {
                    $matrix[$i][$j] = 0;
                }
            }
            if ($col0) {
                $matrix[$i][0] = 0;
            }
        }
    }
}

                                            
class Solution {
    func setZeroes(_ matrix: inout [[Int]]) {
        var firstRowHasZero = false
        var firstColHasZero = false
        
        for i in 0..<matrix.count {
            for j in 0..<matrix[0].count {
                if matrix[i][j] == 0 {
                    if i == 0 {
                        firstRowHasZero = true
                    }
                    if j == 0 {
                        firstColHasZero = true
                    }
                    matrix[0][j] = 0
                    matrix[i][0] = 0
                }
            }
        }
        
        for i in 1..<matrix.count {
            for j in 1..<matrix[0].count {
                if matrix[0][j] == 0 || matrix[i][0] == 0 {
                    matrix[i][j] = 0
                }
            }
        }
        
        if firstRowHasZero {
            for j in 0..<matrix[0].count {
                matrix[0][j] = 0
            }
        }
        
        if firstColHasZero {
            for i in 0..<matrix.count {
                matrix[i][0] = 0
            }
        }
    }
}

                                            
class Solution {
    fun setZeroes(matrix: Array<IntArray>): Unit {
        val rows = matrix.size
        val cols = matrix[0].size
        var isCol = false

        for (i in 0 until rows) {
            if (matrix[i][0] == 0) {
                isCol = true
            }

            for (j in 1 until cols) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }

        for (i in 1 until rows) {
            for (j in 1 until cols) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
        }

        if (matrix[0][0] == 0) {
            for (j in 0 until cols) {
                matrix[0][j] = 0
            }
        }

        if (isCol) {
            for (i in 0 until rows) {
                matrix[i][0] = 0
            }
        }
    }
}

                                            
class Solution {
  void setZeroes(List<List<int>> matrix) {
    bool firstRowHasZero = false;
    bool firstColHasZero = false;

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

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

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

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

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

                                            
func setZeroes(matrix [][]int)  {
    rows := len(matrix)
    cols := len(matrix[0])
    zeroFirstCol := false

    for i := 0; i < rows; i++ {
        if matrix[i][0] == 0 {
            zeroFirstCol = true
        }
        for j := 1; j < cols; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    for i := 1; i < rows; i++ {
        for j := 1; j < cols; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }

    if matrix[0][0] == 0 {
        for j := 0; j < cols; j++ {
            matrix[0][j] = 0
        }
    }

    if zeroFirstCol {
        for i := 0; i < rows; i++ {
            matrix[i][0] = 0
        }
    }
}

                                            
# @param {Integer[][]} matrix
# @return {Void} Do not return anything, modify matrix in-place instead.
def set_zeroes(matrix)
    rows = matrix.length
    cols = matrix[0].length
    zero_rows = []
    zero_cols = []
    
    (0...rows).each do |i|
        (0...cols).each do |j|
            if matrix[i][j] == 0
                zero_rows << i
                zero_cols << j
            end
        end
    end
    
    zero_rows.each { |row| matrix[row] = [0] * cols }
    (0...rows).each { |i| zero_cols.each { |col| matrix[i][col] = 0 } }
end

                                            
object Solution {
    def setZeroes(matrix: Array[Array[Int]]): Unit = {
        var firstRowZero = false
        var firstColZero = false
        
        for (i <- 0 until matrix.length) {
            for (j <- 0 until matrix(0).length) {
                if (matrix(i)(j) == 0) {
                    if (i == 0) firstRowZero = true
                    if (j == 0) firstColZero = true
                    matrix(0)(j) = 0
                    matrix(i)(0) = 0
                }
            }
        }
        
        for (i <- 1 until matrix.length) {
            for (j <- 1 until matrix(0).length) {
                if (matrix(0)(j) == 0 || matrix(i)(0) == 0) {
                    matrix(i)(j) = 0
                }
            }
        }
        
        if (firstRowZero) {
            for (j <- 0 until matrix(0).length) {
                matrix(0)(j) = 0
            }
        }
        
        if (firstColZero) {
            for (i <- 0 until matrix.length) {
                matrix(i)(0) = 0
            }
        }
    }
}

                                            
impl Solution {
    pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
        let mut first_col_zero = false;
        
        // Mark the rows and columns to be zeroed out
        for i in 0..matrix.len() {
            if matrix[i][0] == 0 {
                first_col_zero = true;
            }
            for j in 1..matrix[0].len() {
                if matrix[i][j] == 0 {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Zero out based on the marks
        for i in (1..matrix.len()).rev() {
            for j in (1..matrix[0].len()).rev() {
                if matrix[i][0] == 0 || matrix[0][j] == 0 {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Zero out the first row if needed
        if matrix[0][0] == 0 {
            for j in 0..matrix[0].len() {
                matrix[0][j] = 0;
            }
        }
        
        // Zero out the first column if needed
        if first_col_zero {
            for i in 0..matrix.len() {
                matrix[i][0] = 0;
            }
        }
    }
}

To solve this coding challenge, we need to update an \( m \times n \) matrix such that if an element is 0, its entire row and column are set to 0. The constraint is that it should be done in place without using extra space beyond O(1), which means modifying the matrix directly without using additional arrays or lists of size proportional to \( m \) or \( n \).

Explanation

Approach:

Identify Rows and Columns with Zeroes:

Iterate over the matrix to identify which rows and columns need to be set to zero.
Instead of using extra storage, we can use the first row and the first column of the matrix itself to store this information.
Use two flags,
row_zero

and
col_zero

, to keep track of whether the first row or first column should be zeroed out.

Mark the Zeroes:

During the iteration, if a cell contains zero, set the corresponding first row and first column cells to zero.
Also, if the zero is in the first row or first column, set the respective flag to true.

Update the Matrix:

Iterate through the matrix again (excluding the first row and column), and for each cell, if its corresponding first row or first column cell is zero, set the cell to zero.

Zero Out the First Row and Column:

Finally, check the
row_zero

and
col_zero

flags and zero out the first row and first column if needed.

Detailed Steps in Pseudocode:

Step 1: Initialize Variables and Flags

                                            
# initialize dimensions of the matrix
rows = length(matrix)
cols = length(matrix[0])

# flags to check if first row or first column should be zeroed
row_zero = False
col_zero = False

Step 2: Identify Rows and Columns to be Zeroed

                                            
for i from 0 to rows - 1:
    for j from 0 to cols - 1:
        if matrix[i][j] == 0:
            # mark the first cell of current row and column
            matrix[0][j] = 0
            matrix[i][0] = 0
            
            # mark if the zero is in the first row or column
            if i == 0:
                row_zero = True
            if j == 0:
                col_zero = True

Step 3: Update the Matrix Based on Markers

                                            
for i from 1 to rows - 1:
    for j from 1 to cols - 1:
        if matrix[i][0] == 0 or matrix[0][j] == 0:
            matrix[i][j] = 0

Step 4: Zero Out the First Row and Column if Needed

                                            
if row_zero:
    for j from 0 to cols - 1:
        matrix[0][j] = 0

if col_zero:
    for i from 0 to rows - 1:
        matrix[i][0] = 0

Summary:

By using the first row and the first column of the matrix to store markers, we avoid the need for additional storage space. This approach ensures the solution is efficient in terms of both time and space complexity. Specifically, the algorithm operates in O(m * n) time complexity and O(1) extra space complexity, which adheres to the constraints provided.