Set Matrix Zeroes - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT_CELL = 'current_cell', CURRENT_CELL_COLOR = 'gold';

function visMainFunction(inputMatrix) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const matrix = new VisArray2D(...inputMatrix.map(row => VisArray.from(row)));
    const numOfRows = matrix.length;
    const numOfCols = matrix[0].length;

    let firstRowHasZero = false;
    let firstColHasZero = false;

    makeVisVariable(firstRowHasZero).options({ label: 'First Row Has Zero' }).createVis();
    makeVisVariable(firstColHasZero).options({ label: 'First Column Has Zero' }).createVis();

    endBatch();

    notification(`
      ✅ <b>Step 1: Scan the Matrix and Set Markers</b><br>
      As we scan for <b>0</b>s, whenever a <b>0</b> is found in a cell:
      <ul>
        <li>If the cell lies in the <b>first row</b> or <b>first column</b>, we update the corresponding flag (<code>firstRowHasZero</code> or <code>firstColHasZero</code>).</li>
        <li>Otherwise, we mark its <b>row</b> and <b>column</b> by setting <code>matrix[row][0]</code> and <code>matrix[0][col]</code> to <b>0</b>.</li>
      </ul>
    `);
    let rowIndex = 0;

    while (rowIndex < numOfRows) {
        let colIndex = 0;
        startPartialBatch();
        notification(`Scanning row ${makeColoredSpan(rowIndex, CURRENT_CELL_COLOR)}`);

        while (colIndex < numOfCols) {
            const visManager = matrix.makeVisManagerForIndexPair(rowIndex, colIndex);
            visManager.addClass(CURRENT_CELL);

            if (matrix[rowIndex][colIndex] === 0) {
                notification(`🟢 <b>Zero found at (${makeColoredSpan(rowIndex, CURRENT_CELL_COLOR)}, ${makeColoredSpan(colIndex, CURRENT_CELL_COLOR)})</b>:`);

                if (rowIndex === 0) {
                    notification(`The cell containing the <b>0</b> lies in the <b>first row</b>, so we set <b>firstRowHasZero = true</b>.`);
                    firstRowHasZero = true;
                } else {
                    matrix[rowIndex][0] = 0;
                    notification(`We mark <b>matrix[${makeColoredSpan(rowIndex, CURRENT_CELL_COLOR)}][${makeColoredSpan(0, CURRENT_CELL_COLOR)}]</b> as <b>0</b> to indicate that this entire row should be zeroed.`);
                }

                if (colIndex === 0) {
                    notification(`The cell containing the <b>0</b> lies in the <b>first cell</b>, so we set <b>firstColHasZero = true</b>.`);
                    firstColHasZero = true;
                } else {
                    matrix[0][colIndex] = 0;
                    notification(`We set <b>matrix[${makeColoredSpan(0, CURRENT_CELL_COLOR)}][${makeColoredSpan(colIndex, CURRENT_CELL_COLOR)}]</b> to <b>0</b> to mark that this entire column should be zeroed.`);
                }
            }

            visManager.removeClass(CURRENT_CELL);
            colIndex += 1;
        }

        endBatch();

        rowIndex += 1;
    }


    notification(`✅ <b>Step 2: Use the markers to set inner cells to zero where needed</b>`);
    endBatch();

    rowIndex = 1;
    while (rowIndex < numOfRows) {
        startPartialBatch();
        notification(`Zeroing out inner cells at row ${makeColoredSpan(rowIndex, CURRENT_CELL_COLOR)}`);
        
        let colIndex = 1;
        while (colIndex < numOfCols) {
            const visManager = matrix.makeVisManagerForIndexPair(rowIndex, colIndex);
            visManager.addClass(CURRENT_CELL);

            if (matrix[rowIndex][0] === 0 || matrix[0][colIndex] === 0) {
                notification(`
                  🟡 <b>Setting <code>matrix[${makeColoredSpan(rowIndex, CURRENT_CELL_COLOR)}][${makeColoredSpan(colIndex, CURRENT_CELL_COLOR)}]</code> as 0</b> because at least one of the following markers is 0:
                  <ul>
                    <li><b>Row marker:</b> <code>matrix[${makeColoredSpan(rowIndex, CURRENT_CELL_COLOR)}][${makeColoredSpan(0, CURRENT_CELL_COLOR)}]</code></li>
                    <li><b>Column marker:</b> <code>matrix[${makeColoredSpan(0, CURRENT_CELL_COLOR)}][${makeColoredSpan(colIndex, CURRENT_CELL_COLOR)}]</code></li>
                  </ul>
                  Hence, this cell must be set to 0 along with at least one of its entire row or column.
                `);
                matrix[rowIndex][colIndex] = 0;
            }
            visManager.removeClass(CURRENT_CELL);
            colIndex += 1;
        }
        endBatch();
        rowIndex += 1;
    }

    if (firstRowHasZero) {
        startPartialBatch();
        notification(`✅ <b>Step 3: Zero out the first row because <code>firstRowHasZero</code> is true</b>, meaning the original first row contained a 0.`);
        for (let colIndex = 0; colIndex < numOfCols; colIndex++) {
            matrix[0][colIndex] = 0;
        }
        endBatch();
    }

    if (firstColHasZero) {
        startPartialBatch();
        notification(`✅ <b>Step 4: Zero out the first column because <code>firstColHasZero</code> is true</b>, meaning the original first column contained a 0.`);
        for (let rowIndex = 0; rowIndex < numOfRows; rowIndex++) {
            matrix[rowIndex][0] = 0;
        }
        endBatch();
    }

    notification(`🏁 <b>Finished!</b> The matrix is modified in place`);
    return matrix;
}

function initClassProperties() {
    setClassProperties(CURRENT_CELL, {
        backgroundColor: CURRENT_CELL_COLOR
    });
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema</b>
        <ul>
            <li>Cells highlighted with a <b>${makeColoredSpan(CURRENT_CELL_COLOR + ' background', CURRENT_CELL_COLOR)}</b> represent the <b>currently inspected cell</b> during scanning or updating.</li>
            <li>These highlights move as we iterate through the matrix to show which cell is being processed at that moment.</li>
        </ul>
    `);
}

Approach

The goal is to modify the matrix in place so that if any cell contains 0, its entire row and column are set to 0. To avoid using extra space, we repurpose the first row and first column as markers. Two boolean flags — firstRowHasZero and firstColHasZero — are needed to preserve whether the first row or column originally contained any zeros, since these will later serve as marker storage and might otherwise lose their original information.

Step 1 — Scan & Mark:
Traverse all cells of the matrix. Whenever a 0 is found at position (r, c):
- If r === 0, set firstRowHasZero = true; otherwise mark the row by setting matrix[r][0] = 0.
- If c === 0, set firstColHasZero = true; otherwise mark the column by setting matrix[0][c] = 0.
Using the first row and column as markers is safe because writing a 0 there means the entire corresponding row or column will eventually be zeroed out — including that cell itself. The two boolean flags, firstRowHasZero and firstColHasZero, ensure that we remember whether the first row or column themselves originally contained a 0 and therefore need to be cleared at the end.
Step 2 — Zero Inner Cells Using Markers:
For all cells (r, c) with r ≥ 1 and c ≥ 1, set matrix[r][c] = 0 if either matrix[r][0] === 0 or matrix[0][c] === 0, meaning that the corresponding row or column was marked earlier.
Step 3 — Zero First Row (if needed):
If firstRowHasZero is true, set every cell in the first row to 0.
Step 4 — Zero First Column (if needed):
If firstColHasZero is true, set every cell in the first column to 0.

This approach ensures all rows and columns are zeroed correctly without using extra arrays. The algorithm runs in O(m × n) time since every cell is visited at most twice, and uses only O(1) additional space for the two boolean flags besides the matrix itself.

Time Complexity

The whole matrix is scanned twice, and the first row and first column are scanned at most once. Therefore, the time complexity is O(m × n), where m is the number of rows and n is the number of columns.

Space Complexity

Only two boolean variables (firstRowHasZero and firstColHasZero) are used for tracking, so the algorithm requires constant extra space. Therefore, the space complexity is O(1).

Input-1

Set Matrix Zeroes - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity