LeetCode Solution 73 - Set Matrix Zeroes

Problem Statement

Given an m x n matrix, if an element is 0, set its entire row and column to 0. You must do this in-place.

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

---

Optimal Approach

We use the first row and first column as markers to store which rows and columns should be set to zero. Instead of using extra space, we modify the matrix itself efficiently.

Steps:

1. Use a boolean variable colZero to check if the first column should be zero.
2. Traverse the matrix, marking the first row and first column based on encountered zeroes.
3. Iterate over the matrix (excluding the first row and column) and update elements accordingly.
4. Set the first row and first column to zeroes if required.

---

C++ Code Implementation (LeetCode-Compatible)

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool colZero = false;
        
        // Mark first row and column
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) colZero = true;
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Set matrix elements using marks
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (colZero) matrix[i][0] = 0;
        }
    }
};

---

Step-by-Step Explanation

1. Mark First Row and Column:
   • We traverse the matrix and store zero flags in the first row and column.
   • Use colZero to track if the first column should be zero.
2. Modify the Matrix Using Markers:
   • Traverse the matrix in reverse and update elements based on the markers in the first row and column.
3. Set the First Row and Column:
   • If the first column or row had zeros, update them accordingly.

---

Dry Run / Execution Steps

Input:

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

Steps:

1. Mark zero positions: matrix[1][0] and matrix[0][1].
2. Modify the matrix based on marks.
3. Update first row and column.

Output:

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

---

Alternative Approaches

1. Brute Force (Nested Loops) 🛑

• Traverse entire matrix, store zero positions, and update in a second pass.
• Time Complexity: O(m*n), Space Complexity: O(m+n) (extra arrays).

2. Using Extra Matrix 🛑

• Store a copy of the matrix and update based on zeros.
• Time Complexity: O(m*n), Space Complexity: O(m*n) (extra storage).

---

Best Solution & Why?

Approach	Time Complexity	Space Complexity	Explanation
Brute Force	O(m*n)	O(m+n)	Extra space needed for row & col storage
Extra Matrix	O(m*n)	O(m*n)	Inefficient due to extra storage
Optimized (In-place Marking)	O(m*n)	O(1)	Best as it avoids extra space

Why Best?

• Efficient: Uses constant space (O(1)) with in-place updates.
• No Extra Matrix: Uses first row and column as markers.

---

Complexity Analysis

• Time Complexity: O(m*n) (Each element is processed twice at most).
• Space Complexity: O(1) (No additional space used apart from variables).

---

Conclusion

• We use first row and first column as markers to optimize space usage.
• This in-place solution ensures O(1) extra space while maintaining O(m*n) time complexity.
• Related Problems:
  • Game of Life
  • Rotate Image
  • Spiral Matrix

---

This structured solution is LeetCode-submittable, optimized, and well-explained. 🚀