Set Matrix Zeroes Leetcode Problem 73 [Python Solution]

In this blog post, we'll discuss the Set Matrix Zeroes problem from LeetCode.

We'll provide you with a Python solution and dive deep into the problem's overview, constraints, time and space complexity, as well as a detailed explanation of the efficient approach.

Let's get started!

Problem Overview

The Set Matrix Zeroes problem on LeetCode asks us to modify a given m x n matrix in-place.

When we encounter a 0 in the matrix, we need to set the entire row and column containing that 0 to 0.

Here's a couple of examples to illustrate the problem:

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

Understanding the Constraints

Before we delve into the solution, it's essential to understand the problem's constraints.

This helps us design an efficient algorithm while considering edge cases.

The constraints for this problem are relatively straightforward:

The matrix dimensions are limited to a maximum of 200 rows and 200 columns.
The values in the matrix can range from -2^31 to 2^31 – 1.
We are required to solve this problem in-place, meaning we cannot use additional data structures to store intermediate results.

Set Matrix Zeroes LeetCode Problem Solution

Let's move on to the solution for this problem.

We'll explore an efficient approach that solves the problem in-place with O(1) space complexity.

Here's the Python code for it:

View on GitHub ➹

def setZeroes(matrix):
    ROWS, COLS = len(matrix), len(matrix[0])
    rowZero = False

    # Determine which rows/cols need to be zero
    for r in range(ROWS):
        for c in range(COLS):
            if matrix[r][c] == 0:
                matrix[0][c] = 0
                if r &gt; 0:
                    matrix[r][0] = 0
                else:
                    rowZero = True

    for r in range(1, ROWS):
        for c in range(1, COLS):
            if matrix[0][c] == 0 or matrix[r][0] == 0:
                matrix[r][c] = 0

    if matrix[0][0] == 0:
        for r in range(ROWS):
            matrix[r][0] = 0

    if rowZero:
        for c in range(COLS):
            matrix[0][c] = 0

Now, let's break down the code and understand the reasoning behind this efficient approach.

1. Determining Which Rows and Columns to Zero Out

The first step is to iterate through the entire matrix and determine which rows and columns need to be zeroed out.

To do this, we use the first row and the first column as markers.

If we encounter a 0 in the matrix, we mark the corresponding positions in the first row and the first column with 0.

2. Zeroing Out the Non-First Rows and Columns

After identifying which rows and columns need to be zeroed out, we iterate through the matrix again, excluding the first row and the first column.

For each cell, if either the corresponding position in the first row or the first column is 0, we set the cell's value to 0.

3. Handling the First Row and First Column

Finally, we handle the first row and the first column separately.

If the first row (i.e., rowZero) contains any 0, we set all values in the first row to 0.

If the top-left cell of the matrix is 0, we set all values in the first column to 0.

This approach ensures that we zero out the entire rows and columns when a 0 is encountered, while keeping the rest of the matrix intact.

It utilizes O(1) extra space, making it an efficient solution for this problem.

Time and Space Complexity

Now, let's discuss the time and space complexity of our solution.

Time Complexity

We iterate through the entire matrix three times:

The first pass identifies which rows and columns to zero out.
The second pass zeros out the non-first rows and columns.
The third pass handles the first row and first column.

Since we visit each element in the matrix only once, the time complexity of our solution is O(m * n), where m is the number of rows and n is the number of columns.

Space Complexity

Our solution uses only a constant amount of extra space (O(1)).

We don't create any additional data structures to store intermediate results, meeting the problem's requirement of an in-place solution with minimal memory usage.

Reasoning Behind Our Efficient Approach

The efficient approach we've discussed is based on the idea of using the first row and first column of the matrix to store information about which rows and columns need to be zeroed out.

By carefully iterating through the matrix and utilizing these markers, we can achieve an in-place solution with minimal space complexity.

The key insight is to use the first row and the first column to keep track of which rows and columns need zeroing without requiring extra memory.

This allows us to determine the changes that need to be made in the matrix and then apply those changes without using additional data structures.

Conclusion

In this blog post, we explored the Set Matrix Zeroes problem from LeetCode.

We provided a Python solution that efficiently solves the problem in-place with O(1) space complexity.

We discussed the problem's overview, constraints, and an explanation of our approach.

If you have any questions, suggestions, or would like to discuss this problem further, please feel free to leave a comment.

We encourage you to engage with the content and share it with others who might find it helpful.

For the full problem description and to try the solution on LeetCode, you can visit the following link:
Set Matrix Zeroes LeetCode Problem

Happy coding!