LeetCode 2174: Remove All Ones With Row and Column Flips II Solution

Master LeetCode problem 2174 (Remove All Ones With Row and Column Flips II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2174. Remove All Ones With Row and Column Flips II

Medium

Array Bit Manipulation Breadth-First Search Matrix

Problem Explanation

Explanation:

This problem asks us to remove all ones from a binary matrix using row and column flips. We are allowed to flip any row or column of the matrix. The goal is to minimize the number of flips required to remove all ones from the matrix.

To solve this problem, we can follow the steps below:

Iterate through each row of the matrix and check if it contains only ones.
If a row contains only ones, we can flip that row to remove all ones in that row.
If a row contains zeros or a mix of zeros and ones, we need to check the corresponding column to see if it contains only ones. If so, we can flip that column to remove all ones in that column.
If a row contains both zeros and ones, and the corresponding column also contains both zeros and ones, we cannot remove all ones from that row using a single flip. In this case, we need to flip both the row and column to remove all ones.

By following this approach, we can minimize the number of flips required to remove all ones from the matrix.

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix. Space Complexity: O(1) as we are not using any extra space.

: :

Solution Code

class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < (1 << m); i++) {
            int flips = 0;
            int[][] temp = new int[m][n];
            for (int j = 0; j < m; j++) {
                if (((i >> j) & 1) == 1) {
                    for (int k = 0; k < n; k++) {
                        temp[j][k] = 1 - mat[j][k];
                    }
                    flips++;
                } else {
                    for (int k = 0; k < n; k++) {
                        temp[j][k] = mat[j][k];
                    }
                }
            }
            int count = 0;
            for (int j = 0; j < n; j++) {
                int ones = 0;
                for (int k = 0; k < m; k++) {
                    ones += temp[k][j];
                }
                count += Math.min(ones, m - ones);
            }
            if (count == 0) {
                ans = Math.min(ans, flips);
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2174 (Remove All Ones With Row and Column Flips II)?

This page provides optimized solutions for LeetCode problem 2174 (Remove All Ones With Row and Column Flips II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2174 (Remove All Ones With Row and Column Flips II)?

The time complexity for LeetCode 2174 (Remove All Ones With Row and Column Flips II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2174 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2174 in Java, C++, or Python.

Back to LeetCode Solutions