Skip to main content
Talentd

Remove All Ones With Row and Column Flips II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBit ManipulationBreadth-First SearchMatrix6 min readAsked at: Google
Practice this problem

Problem Statement

You are given a 0-indexed m x n binary matrix grid.

In one operation, you can choose any i and j that meet the following conditions:

  • 0 <= i < m
  • 0 <= j < n
  • grid[i][j] == 1

and change the values of all cells in row i and column j to zero.

Return the minimum number of operations needed to remove all 1's from grid.

 

Example 1:

Input: grid = [[1,1,1],[1,1,1],[0,1,0]]
Output: 2
Explanation:
In the first operation, change all cell values of row 1 and column 1 to zero.
In the second operation, change all cell values of row 0 and column 0 to zero.

Example 2:

Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: 2
Explanation:
In the first operation, change all cell values of row 1 and column 0 to zero.
In the second operation, change all cell values of row 2 and column 1 to zero.
Note that we cannot perform an operation using row 1 and column 1 because grid[1][1] != 1.

Example 3:

Input: grid = [[0,0],[0,0]]
Output: 0
Explanation:
There are no 1's to remove so return 0.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • 1 <= m * n <= 15
  • grid[i][j] is either 0 or 1.

Approach Overview

Problem Overview: You are given a binary matrix. In one operation, you pick a cell containing 1 and flip every cell in its row and column. The goal is to reach a matrix of all zeros using the minimum number of operations.

Approach 1: Backtracking Simulation (Exponential)

The most direct idea is to simulate every possible sequence of operations. Iterate through the grid, pick any cell containing 1, flip its entire row and column, and recursively continue until the grid becomes all zeros. Because multiple sequences can reach the same matrix configuration, the search quickly explodes. Without strong pruning or memoization, this approach explores an exponential number of states. Time complexity is roughly O((mn)!) in the worst case, with O(mn) space for recursion depth. This method mainly helps you understand how operations transform the grid.

Approach 2: Breadth-First Search with Matrix States (O(2^(mn) * mn))

Treat each matrix configuration as a node in a graph. From a given state, iterate through every cell; if the value is 1, generate a new state by flipping its row and column. Use Breadth-First Search to explore states level by level. A visited set prevents revisiting the same configuration. BFS guarantees the first time you reach the all-zero matrix is the minimum number of operations. The state space can reach up to 2^(mn), and generating each neighbor costs O(mn). Space complexity is also O(2^(mn)) for the visited set.

Approach 3: BFS with Bitmask Compression (O(2^(mn) * mn))

Instead of storing the matrix directly, encode it as a single integer bitmask where each bit represents a cell. This reduces memory overhead and speeds up state comparisons. When selecting a cell containing 1, compute the next mask by toggling bits for every cell in the same row and column using bit manipulation. BFS runs over these compressed states while a hash set tracks visited masks. This approach is significantly faster in practice and is the typical implementation for problems involving small matrix grids with state transitions.

Recommended for interviews: BFS with bitmask compression. It models the problem as a shortest-path search over states while keeping operations efficient. Showing the brute-force reasoning first demonstrates understanding of the state space, while the bitmask BFS demonstrates strong algorithmic optimization.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking SimulationExponential (≈ O((mn)!))O(mn)Conceptual exploration of operation sequences; not practical for full constraints
BFS with Matrix StatesO(2^(mn) * mn)O(2^(mn))General shortest-path search across matrix configurations
BFS with Bitmask CompressionO(2^(mn) * mn)O(2^(mn))Optimal implementation when grid size is small and state compression is possible

Video Solution

2174. Remove All Ones With Row and Column Flips II • Shuo Yan • 565 views views

Frequently Asked Questions

Is Remove All Ones With Row and Column Flips II easy or hard?
The problem is rated Medium but requires strong state modeling. The challenge is recognizing that the matrix configurations form a graph and that BFS can find the minimum number of operations. Implementing the solution with bitmask compression makes it efficient enough for interview constraints.
Remove All Ones With Row and Column Flips II Python/Java solution
Most implementations follow the same pattern: convert the matrix to a bitmask, run BFS using a queue, and generate new states by toggling bits in the selected row and column. Python often uses integers and sets for masks, while Java and C++ typically use integers with bit operations for faster transitions.
How to solve Remove All Ones With Row and Column Flips II in O(2^(mn))?
Use BFS over compressed states represented by bitmasks. Convert the matrix into an integer where each bit corresponds to a cell. For every cell containing 1, toggle all bits in the same row and column to generate the next state. BFS ensures the minimum number of operations while a visited set prevents repeated exploration.
What is the best approach for Remove All Ones With Row and Column Flips II?
Breadth-First Search with bitmask state compression is the most effective approach. Each matrix configuration is encoded as a bitmask and BFS explores all reachable states while tracking visited ones. The first time the all-zero mask appears gives the minimum number of operations. This avoids redundant recomputation and keeps transitions efficient.
Is Remove All Ones With Row and Column Flips II asked at Google/Amazon/Meta?
Problems involving state search with BFS and bitmasking are common in interviews at companies like Google, Amazon, and Meta. Variants of matrix state transformation and minimum operations problems frequently appear because they test graph modeling, BFS traversal, and bit manipulation skills.
What data structure is used in Remove All Ones With Row and Column Flips II?
The main data structures are a queue for BFS traversal and a hash set for visited states. When optimized, the matrix state is stored as a bitmask integer, which enables fast bit operations and compact memory usage. This combination allows efficient exploration of all reachable configurations.
What is the time complexity of Remove All Ones With Row and Column Flips II?
The typical optimized solution runs in O(2^(m*n) * m*n) time. There can be up to 2^(m*n) possible matrix states, and for each state you may try up to m*n operations while constructing the next state. Space complexity is also O(2^(m*n)) due to the visited set used during BFS.

Ready to solve this problem?

Practice Remove All Ones With Row and Column Flips II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Next

Remove All Ones With Row and Column Flips