Home
Array
Set Matrix Zeroes

Set Matrix Zeroes

medium

By - Aman Pareek

Last Updated - 02/09/2024

On this page toc arrow icon

Problem Statement

Imagine you have a matrix of integers. Your task is to modify this matrix in place such that if any element in the matrix is zero, its entire row and column are set to zeroes.

Here’s how you should approach the problem:

  1. Input: A 2D matrix of integers. The matrix has dimensions m x n, where 1 <= m, n <= 200, and each integer in the matrix can range from -2^31 to 2^31 - 1.

  2. Output: The modified matrix where each row and column containing at least one zero has been set to zeroes.

Example 1

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

Output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]]

Example 2

Input: matrix = [ [0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5] ]

Output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Constraints

  • The matrix dimensions are between 1 x 1 and 200 x 200.

  • You must perform the operation in place, meaning you should not use extra space proportional to the matrix size. Try to achieve this with constant extra space.

Solution 1: Using Extra Space (O(m + n) Space)

function setZeroesUsingExtraSpace(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;
    const zeroRows = Array(numRows).fill(false);
    const zeroCols = Array(numCols).fill(false);

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    // Identify which rows and columns contain zeroes
    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                zeroRows[row] = true;
                zeroCols[col] = true;
            }
        }
    }

    // Set rows to zero
    for (let row = 0; row < numRows; row++) {
        if (zeroRows[row]) {
            for (let col = 0; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Set columns to zero
    for (let col = 0; col < numCols; col++) {
        if (zeroCols[col]) {
            for (let row = 0; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesUsingExtraSpace(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesUsingExtraSpace(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 2: Using Matrix First Row and Column for Marking

function setZeroesUsingMatrixMarks(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    let firstRowHasZero = false;
    let firstColHasZero = false;

    // Check if the first row has any zeroes
    for (let col = 0; col < numCols; col++) {
        if (matrix[0][col] === 0) {
            firstRowHasZero = true;
            break;
        }
    }

    // Check if the first column has any zeroes
    for (let row = 0; row < numRows; row++) {
        if (matrix[row][0] === 0) {
            firstColHasZero = true;
            break;
        }
    }

    // Use the first row and column to mark zero rows and columns
    for (let row = 1; row < numRows; row++) {
        for (let col = 1; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                resultMatrix[row][0] = 0;
                resultMatrix[0][col] = 0;
            }
        }
    }

    // Set zeroes in the marked rows
    for (let row = 1; row < numRows; row++) {
        if (resultMatrix[row][0] === 0) {
            for (let col = 1; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Set zeroes in the marked columns
    for (let col = 1; col < numCols; col++) {
        if (resultMatrix[0][col] === 0) {
            for (let row = 1; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Zero out the first row if needed
    if (firstRowHasZero) {
        for (let col = 0; col < numCols; col++) {
            resultMatrix[0][col] = 0;
        }
    }

    // Zero out the first column if needed
    if (firstColHasZero) {
        for (let row = 0; row < numRows; row++) {
            resultMatrix[row][0] = 0;
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesUsingMatrixMarks(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesUsingMatrixMarks(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 3: In-place Matrix Modification with Boolean Flags

function setZeroesWithFlags(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    let zeroFirstRow = false;
    let zeroFirstCol = false;

    // Determine if first row or column has zeroes
    for (let row = 0; row < numRows; row++) {
        if (matrix[row][0] === 0) zeroFirstCol = true;
    }
    for (let col = 0; col < numCols; col++) {
        if (matrix[0][col] === 0) zeroFirstRow = true;
    }

    // Use first row and column as markers
    for (let row = 1; row < numRows; row++) {
        for (let col = 1; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                resultMatrix[row][0] = 0;
                resultMatrix[0][col] = 0;
            }
        }
    }

    // Set zeroes based on markers
    for (let row = 1; row < numRows; row++) {
        if (resultMatrix[row][0] === 0) {
            for (let col = 1; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }
    for (let col = 1; col < numCols; col++) {
        if (resultMatrix[0][col] === 0) {
            for (let row = 1; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Handle the first row and column
    if (zeroFirstRow) {
        for (let col = 0; col < numCols; col++) {
            resultMatrix[0][col] = 0;
        }
    }
    if (zeroFirstCol) {
        for (let row = 0; row < numRows; row++) {
            resultMatrix[row][0] = 0;
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesWithFlags(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesWithFlags(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 4: Using a Set for Row and Column Tracking

function setZeroesUsingSets(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;
    const zeroRows = new Set();
    const zeroCols = new Set();

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    // Identify zero rows and columns
    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                zeroRows.add(row);
                zeroCols.add(col);
            }
        }
    }

    // Set rows to zero
    for (const row of zeroRows) {
        for (let col = 0; col < numCols; col++) {
            resultMatrix[row][col] = 0;
        }
    }

    // Set columns to zero
    for (const col of zeroCols) {
        for (let row = 0; row < numRows; row++) {
            resultMatrix[row][col] = 0;
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesUsingSets(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesUsingSets(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 5: In-place Using Boolean Matrix

function setZeroesWithBooleanMatrix(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;
    const zeroRows = Array(numRows).fill(false);
    const zeroCols = Array(numCols).fill(false);

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    // Find zeroes and mark the rows and columns
    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                zeroRows[row] = true;
                zeroCols[col] = true;
            }
        }
    }

    // Zero out rows
    for (let row = 0; row < numRows; row++) {
        if (zeroRows[row]) {
            for (let col = 0; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Zero out columns
    for (let col = 0; col < numCols; col++) {
        if (zeroCols[col]) {
            for (let row = 0; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesWithBooleanMatrix(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesWithBooleanMatrix(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 6: Using Single Array for Marking

function setZeroesUsingSingleArray(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;
    const marks = Array(numRows + numCols).fill(false);

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    // Mark the rows and columns
    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                marks[row] = true;
                marks[numRows + col] = true;
            }
        }
    }

    // Set rows to zero
    for (let row = 0; row < numRows; row++) {
        if (marks[row]) {
            for (let col = 0; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Set columns to zero
    for (let col = 0; col < numCols; col++) {
        if (marks[numRows + col]) {
            for (let row = 0; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesUsingSingleArray(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesUsingSingleArray(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 7: Diagonal Method

function setZeroesUsingDiagonal(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    let hasZeroInFirstRow = false;
    let hasZeroInFirstCol = false;

    // Check first row and column
    for (let col = 0; col < numCols; col++) {
        if (matrix[0][col] === 0) {
            hasZeroInFirstRow = true;
            break;
        }
    }
    for (let row = 0; row < numRows; row++) {
        if (matrix[row][0] === 0) {
            hasZeroInFirstCol = true;
            break;
        }
    }

    // Use diagonal to mark zeroes
    for (let row = 1; row < numRows; row++) {
        for (let col = 1; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                resultMatrix[row][0] = 0;
                resultMatrix[0][col] = 0;
            }
        }
    }

    // Zero out the rows
    for (let row = 1; row < numRows; row++) {
        if (resultMatrix[row][0] === 0) {
            for (let col = 1; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Zero out the columns
    for (let col = 1; col < numCols; col++) {
        if (resultMatrix[0][col] === 0) {
            for (let row = 1; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    // Handle the first row and column
    if (hasZeroInFirstRow) {
        for (let col = 0; col < numCols; col++) {
            resultMatrix[0][col] = 0;
        }
    }
    if (hasZeroInFirstCol) {
        for (let row = 0; row < numRows; row++) {
            resultMatrix[row][0] = 0;
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesUsingDiagonal(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesUsingDiagonal(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 8: Two-Pass Algorithm with Auxiliary Array

function setZeroesTwoPass(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;
    const zeroRows = Array(numRows).fill(false);
    const zeroCols = Array(numCols).fill(false);

    // Create a copy of the matrix
    const resultMatrix = matrix.map(row => row.slice());

    // First pass: identify zeroes
    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                zeroRows[row] = true;
                zeroCols[col] = true;
            }
        }
    }

    // Second pass: apply zeroes
    for (let row = 0; row < numRows; row++) {
        if (zeroRows[row]) {
            for (let col = 0; col < numCols; col++) {
                resultMatrix[row][col] = 0;
            }
        }
    }
    for (let col = 0; col < numCols; col++) {
        if (zeroCols[col]) {
            for (let row = 0; row < numRows; row++) {
                resultMatrix[row][col] = 0;
            }
        }
    }

    return resultMatrix;
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesTwoPass(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesTwoPass(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solution 9: Using Bitwise Operations for Flagging

function setZeroesUsingBitwise(matrix) {
    const numRows = matrix.length;
    const numCols = matrix[0].length;

    let zeroFirstRow = false;
    let zeroFirstCol = false;

    // Check if the first row contains zeroes
    for (let col = 0; col < numCols; col++) {
        if (matrix[0][col] === 0) {
            zeroFirstRow = true;
            break;
        }
    }

    // Check if the first column contains zeroes
    for (let row = 0; row < numRows; row++) {
        if (matrix[row][0] === 0) {
            zeroFirstCol = true;
            break;
        }
    }

    // Use the first row and first column to mark zeroes
    for (let row = 1; row < numRows; row++) {
        for (let col = 1; col < numCols; col++) {
            if (matrix[row][col] === 0) {
                matrix[row][0] = 0;
                matrix[0][col] = 0;
            }
        }
    }

    // Zero out cells based on the marks in the first row and column
    for (let row = 1; row < numRows; row++) {
        for (let col = 1; col < numCols; col++) {
            if (matrix[row][0] === 0 || matrix[0][col] === 0) {
                matrix[row][col] = 0;
            }
        }
    }

    // Zero out the first row if needed
    if (zeroFirstRow) {
        for (let col = 0; col < numCols; col++) {
            matrix[0][col] = 0;
        }
    }

    // Zero out the first column if needed
    if (zeroFirstCol) {
        for (let row = 0; row < numRows; row++) {
            matrix[row][0] = 0;
        }
    }

    // Return a new matrix with the modifications
    return matrix.map(row => row.slice());
} 

const matrix1 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
setZeroesUsingBitwise(matrix1);  //output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1]] 

const matrix2 = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
];
setZeroesUsingBitwise(matrix2);  //output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

More Problems Solutions

Is array equalArray of strings containing numbersFlatten array Get first positive integer in arrayRemove All Falsy Values from an Array

Popular Solutions