algoadvance

Leetcode 73. Set Matrix Zeroes

Problem Statement

Leetcode Problem 73: Set Matrix Zeroes

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

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:

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

Follow-up:

• A straightforward solution using O(m*n) space is probably a bad idea.
• A simple improvement uses O(m + n) space.
• Could you devise a constant space solution?

Clarifying Questions

1. Q: Can we modify the input matrix directly? A: Yes, the problem statement requires us to modify the matrix in place.

2. Q: Can the matrix have any integer values including negative ones? A: Yes, the elements of the matrix can range from -2^31 to 2^31 - 1.

3. Q: Should we consider an empty matrix? A: No, given constraints ensure the matrix has dimensions at least 1x1.

Strategy

1. Initial Thoughts:
   • To achieve in place modification, we can use the first row and first column of the matrix itself to mark whether a particular row or column should be set to zero.
2. Steps:
   • First, determine if the first row or first column need to be zeroed initially (we can use separate boolean flags for this).
   • Then, traverse the rest of the matrix, and use the first row and first column to mark zeroes.
   • Finally, use these markings to set the appropriate rows and columns to zero.
   • Lastly, handle the first row and first column separately based on the initial flags.

Code

#include <vector>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    
    bool firstRowZero = false;
    bool firstColZero = false;
    
    // Check if the first row needs to be zero
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }

    // Check if the first column needs to be zero
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }
    
    // Use the first row and column to mark zero rows and columns
    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;
            }
        }
    }
    
    // Zero out cells based on marks
    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;
            }
        }
    }
    
    // Handle the first row separately
    if (firstRowZero) {
        for (int j = 0; j < n; ++j) {
            matrix[0][j] = 0;
        }
    }
    
    // Handle the first column separately
    if (firstColZero) {
        for (int i = 0; i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
}

Time Complexity

• Time Complexity: O(m * n) because we traverse the entire matrix multiple times but with a constant number of operations on each cell.
• Space Complexity: O(1) as we are using only constant extra space for flags and modifying the matrix in place.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?