Top Interview 150

The Set Matrix Zeroes problem is a common challenge involving in-place matrix manipulation. Let’s solve LeetCode 73: Set Matrix Zeroes step by step, focusing on achieving the O(1) space complexity requirement.

🚀 Problem Description

Given an m×n matrix:

• If an element is 0, set its entire row and column to 0.
• Perform this operation in-place.

💡 Examples

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 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]  
Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Constraints

• 1 ≤ m,n ≤ 200
• -2^31 ≤ matrix[i][j]≤ 2^31-1

🏆 JavaScript Solution

We can solve this problem efficiently using the first row and first column of the matrix as markers to indicate which rows and columns need to be set to 0.

Implementation

var setZeroes = function(matrix) {
    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; // Mark the first column
                matrix[0][j] = 0; // Mark the first row
            }
        }
    }

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

🔍 How It Works

1. Mark the First Row and Column:

   • Traverse the matrix to find zero elements.
   • Use the first row and first column as markers to remember which rows and columns need to be zeroed.

2. Set Elements to Zero:

   • For every cell not in the first row or column, check the corresponding marker.
   • If the marker indicates zero, set the cell to zero.

3. Handle the First Row and Column:

   • If the first row or first column originally contained zeros, set all their elements to zero.

🔑 Complexity Analysis

• Time Complexity: O(m⋅n), where m is the number of rows and n is the number of columns.

  • Each cell is visited once during marking and once during the update.

• Space Complexity: O(1), since no additional data structures are used.

📋 Dry Run

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

• Step 1: Mark the First Row and Column

• Step2: Update the Matrix

• Step 3: Update the First Row and Column

Output:

[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

✨ Pro Tips for Interviews

1. Explain Constant Space:

   • Highlight how you use the matrix itself for marking instead of additional space.

2. Clarify Edge Cases:

   • Single row/column matrices.
   • Matrices where all elements are zero.

3. Discuss Optimization:

   • Compare the O(mn) space solution to the O(1) optimized approach.

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Rotate Image - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀