Set Matrix Zeros – In-Place Magic!

 Set Matrix Zeros – Modify In Place Like a Pro!

Given an m × n matrix, if any element is 0, set its entire row and column to 0. Simple? Not quite! The real challenge is doing it in place without extra space. Let’s explore the best way to tackle this problem.

The Best Data Structure for Solving It (and Why!)

Since we must modify the matrix in place, we avoid extra space as much as possible.

  • Brute Force Approach: Uses an auxiliary matrix (O(mn) space) → Not optimal!

  • Optimized Approach: Uses constant space O(1) with the first row & first column acting as storage.

Different Approaches – Brute Force to Optimized Solutions

1)Brute Force – Using an Extra Matrix

Idea: Store the original matrix in a separate grid, update the zeros in the new grid, and copy back.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] temp = new int[m][n];

        // Copy original matrix
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                temp[i][j] = matrix[i][j];

        // Modify the temp matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    for (int k = 0; k < n; k++) temp[i][k] = 0;
                    for (int k = 0; k < m; k++) temp[k][j] = 0;
                }
            }
        }

        // Copy back
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                matrix[i][j] = temp[i][j];
    }
}

This method is inefficient because it requires O(mn) extra space, which is unnecessary.

2)Optimized Approach – Using Two Extra Arrays

Idea: Instead of storing an entire matrix, use two 1D arrays to track which rows and columns should be zeroed.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        // Mark rows and columns to be zeroed
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        // Set rows and columns to zero
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (row[i] || col[j])
                    matrix[i][j] = 0;
    }
}

This approach is better than the brute force method, as it reduces space usage to O(m + n) instead of O(m × n). However, it still isn't the most optimal solution.

3)Most Efficient Approach – Constant Space O(1)

Idea: Instead of using extra arrays, we can use the first row and first column as flags to store the zero markers.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;

        // Check if first row or first column should be zero
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;

        // Use first row & column as storage
        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;
                }
            }
        }

        // Set corresponding rows & columns to zero
        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 first row and first column separately
        if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
        if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
}

This constant space approach is the most optimal because:

  • It avoids extra storage beyond the matrix itself.

  • It runs in O(m × n) time, just like previous methods.

  • It ensures in-place modification without altering the original structure unnecessarily.

⚠️ Common Mistakes & Pitfalls to Avoid

  1. Modifying the matrix while traversing it – This can lead to incorrect updates because changes propagate through the matrix prematurely.

  2. Forgetting to store first row/column flags – Leads to unintended modifications of matrix elements.

  3. Using a brute-force approach – Leads to inefficiency for large matrices with unnecessary space usage.

📊 Time & Space Complexity Analysis

  • Brute Force: O(m × n × (m + n)) time, O(mn) space (extra matrix).

  • Using Extra Arrays: O(m × n) time, O(m + n) space.

  • Best (Constant Space): O(m × n) time, O(1) space.

🌍 Real-World Applications

  • Image Processing – Handling corrupted pixels in an image by spreading missing information.

  • Database Management – Automatically marking rows/columns as invalid when an error occurs.

  • Excel/Spreadsheets – Auto-updating rows and columns based on conditions.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more