LeetCode 2174 - Remove All Ones With Row and Column Flips II

The problem gives us an m x n binary matrix where every cell contains either 0 or 1. Our goal is to remove all 1s using the minimum number of operations. An operation can only be performed on a cell (i, j) that currently contains a 1.

leetcodemediumarraybit-manipulationbreadth-first-searchmatrix

LeetCode Problem 2174

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem gives us an m x n binary matrix where every cell contains either 0 or 1. Our goal is to remove all 1s using the minimum number of operations.

An operation can only be performed on a cell (i, j) that currently contains a 1. Once we choose such a cell, we immediately set every cell in row i and every cell in column j to 0.

This is important because the operation affects an entire row and an entire column simultaneously. The chosen cell acts as the "anchor" of the operation, but the effect spreads across both dimensions.

The output should be the minimum number of operations required so that the entire matrix becomes all zeros.

The constraints are the key to solving this problem efficiently:

  • 1 <= m, n <= 15
  • 1 <= m * n <= 15

Although the matrix dimensions can individually be as large as 15, the total number of cells is at most 15. This is a very strong hint that we should think about representing the entire matrix as a bitmask.

Since there are at most 15 cells, the total number of possible matrix states is at most:

2^15 = 32768

That is small enough for exhaustive state exploration using BFS or memoized DFS.

Several edge cases are important:

  • The matrix may already contain all zeros, in which case the answer is 0.
  • A matrix may contain only a single 1, which requires exactly one operation.
  • Different operation orders may produce different numbers of steps, so greedy strategies are unreliable.
  • Performing an operation can remove many 1s at once, especially in dense matrices.
  • Since operations are only allowed on cells currently equal to 1, we cannot arbitrarily choose any row and column combination.

These observations naturally lead us toward state-space search.

Approaches

Brute Force Approach

A naive brute-force strategy would recursively try every possible valid operation from the current matrix state.

At each step:

  1. Scan the matrix for all cells containing 1.
  2. For each such cell, simulate the operation.
  3. Recurse on the resulting matrix.
  4. Track the minimum number of operations among all possibilities.

This approach is correct because it explores every possible sequence of operations. Eventually, it will discover the optimal sequence.

However, the problem is that many matrix states repeat through different operation orders. Without remembering previously computed states, the recursion tree grows exponentially and performs massive redundant work.

Even though the total state count is only 2^15, naive recursion may revisit the same state many times.

Key Insight

The crucial observation is that the entire matrix can be represented as a bitmask because there are at most 15 cells.

Each unique matrix configuration becomes a node in a graph:

  • A node represents one matrix state.
  • An edge represents performing one valid operation.

Since every operation has equal cost, the shortest path from the initial state to the all-zero state can be found using Breadth-First Search.

BFS is ideal here because:

  • Each operation costs exactly 1.
  • BFS guarantees the first time we reach the all-zero state is with the minimum number of operations.
  • The total number of states is small enough to explore exhaustively.

We also avoid repeated work by storing visited states.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential, potentially much larger than 2^(mn) due to repeated states Exponential recursion stack Explores all operation sequences redundantly
Optimal BFS with Bitmask O(2^(mn) * mn * mn) O(2^(mn)) Explores each state once using BFS

Algorithm Walkthrough

Step 1: Encode the Matrix as a Bitmask

We flatten the matrix into a single integer.

For every cell:

  • If grid[i][j] == 1, we set the corresponding bit in the mask.
  • If it is 0, the bit remains unset.

For example:

grid = [
  [1,0],
  [1,1]
]

can become:

bit positions:
0 1
2 3

mask = 1101₂

Using bitmasks makes state transitions extremely efficient.

Step 2: Initialize BFS

We start BFS from the initial mask.

We maintain:

  • A queue storing (state, steps)
  • A visited set to avoid revisiting states

The target state is simply:

0

because all bits cleared means all matrix cells are zero.

Step 3: Process Each BFS State

For the current mask:

  1. If the mask is 0, return the current step count.
  2. Otherwise, examine every cell in the matrix.

For each cell (i, j):

  • Check whether its bit is set.
  • If not set, we cannot perform an operation there.
  • If set, simulate the operation.

Step 4: Simulate an Operation

When choosing (i, j):

  • Every bit in row i becomes 0
  • Every bit in column j becomes 0

We create a new mask by clearing those bits.

This is done efficiently with bit operations.

Step 5: Push New States into BFS

If the resulting mask has not been visited:

  • Mark it visited
  • Push it into the queue with steps + 1

Because BFS explores states level by level, the first time we reach state 0 is guaranteed to be optimal.

Why it works

BFS explores all states reachable in k operations before exploring states requiring k + 1 operations. Every edge in the state graph has equal weight because every operation costs exactly one step. Therefore, the first time BFS reaches the all-zero state, it must be using the minimum possible number of operations.

Python Solution

from collections import deque
from typing import List

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        initial_mask = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    bit = i * n + j
                    initial_mask |= (1 << bit)

        queue = deque([(initial_mask, 0)])
        visited = {initial_mask}

        while queue:
            mask, steps = queue.popleft()

            if mask == 0:
                return steps

            for i in range(m):
                for j in range(n):
                    bit = i * n + j

                    if not (mask & (1 << bit)):
                        continue

                    next_mask = mask

                    # Clear entire row i
                    for col in range(n):
                        row_bit = i * n + col
                        next_mask &= ~(1 << row_bit)

                    # Clear entire column j
                    for row in range(m):
                        col_bit = row * n + j
                        next_mask &= ~(1 << col_bit)

                    if next_mask not in visited:
                        visited.add(next_mask)
                        queue.append((next_mask, steps + 1))

        return -1

The implementation begins by converting the matrix into a compact integer bitmask. Each matrix cell maps to one bit position. This allows the entire matrix state to fit inside a single integer because there are at most fifteen cells.

The BFS queue stores pairs of (mask, steps), where mask represents the current matrix configuration and steps represents how many operations were used to reach it.

For each state, the algorithm checks every cell. If the corresponding bit is set, that means the cell currently contains a 1, so it is a valid operation target.

To simulate the operation, the code clears all bits in the chosen row and column. Bit clearing is performed using:

next_mask &= ~(1 << position)

This efficiently removes cells from the matrix state.

The visited set ensures every state is processed at most once. Since BFS processes states in increasing order of operations, the first time we encounter the all-zero state is guaranteed to be optimal.

Go Solution

package main

import "container/list"

func removeOnes(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	initialMask := 0

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				bit := i*n + j
				initialMask |= (1 << bit)
			}
		}
	}

	type State struct {
		mask  int
		steps int
	}

	queue := list.New()
	queue.PushBack(State{initialMask, 0})

	visited := map[int]bool{
		initialMask: true,
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		current := front.Value.(State)
		mask := current.mask
		steps := current.steps

		if mask == 0 {
			return steps
		}

		for i := 0; i < m; i++ {
			for j := 0; j < n; j++ {
				bit := i*n + j

				if (mask & (1 << bit)) == 0 {
					continue
				}

				nextMask := mask

				// Clear row i
				for col := 0; col < n; col++ {
					rowBit := i*n + col
					nextMask &= ^(1 << rowBit)
				}

				// Clear column j
				for row := 0; row < m; row++ {
					colBit := row*n + j
					nextMask &= ^(1 << colBit)
				}

				if !visited[nextMask] {
					visited[nextMask] = true
					queue.PushBack(State{nextMask, steps + 1})
				}
			}
		}
	}

	return -1
}

The Go implementation follows the exact same BFS strategy as the Python version.

One notable difference is bit clearing syntax. In Go, the expression:

nextMask &= ^(1 << position)

is used instead of Python's ~.

The BFS queue is implemented using container/list, since Go does not provide a built-in deque structure. The visited structure uses a map[int]bool.

Because the maximum state count is only 32768, regular integer types are completely sufficient and there is no overflow concern.

Worked Examples

Example 1

Input:

[
  [1,1,1],
  [1,1,1],
  [0,1,0]
]

Initial mask:

111111010

BFS Level 0

State Steps
111111010 0

Suppose we choose cell (1,1).

Affected cells:

  • Entire row 1
  • Entire column 1

Resulting grid:

[
  [1,0,1],
  [0,0,0],
  [0,0,0]
]

New mask:

101000000

BFS Level 1

State Steps
101000000 1

Choose cell (0,0).

Affected:

  • Row 0
  • Column 0

Result:

[
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

Mask becomes:

000000000

Answer:

2

Example 2

Input:

[
  [0,1,0],
  [1,0,1],
  [0,1,0]
]

Initial mask contains four active bits.

One optimal sequence:

  1. Choose (1,0)
  2. Choose (2,1)

After the first operation:

[
  [0,1,0],
  [0,0,0],
  [0,1,0]
]

After the second operation:

[
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

Total operations:

2

Example 3

Input:

[
  [0,0],
  [0,0]
]

Initial mask:

0

The BFS immediately returns 0 because the matrix already contains no 1s.

Complexity Analysis

Measure Complexity Explanation
Time O(2^(mn) * mn * mn) Each state examines all cells and may clear rows and columns
Space O(2^(mn)) BFS queue and visited set store matrix states

The maximum number of states is 2^(mn), and mn <= 15, so the total state space is at most 32768.

For each state, we iterate through every cell to find valid operations. For each valid operation, we may scan an entire row and column to clear bits. Since both dimensions are at most 15, this remains efficient enough.

Test Cases

from typing import List

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> int:
        from collections import deque

        m = len(grid)
        n = len(grid[0])

        initial_mask = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    initial_mask |= (1 << (i * n + j))

        queue = deque([(initial_mask, 0)])
        visited = {initial_mask}

        while queue:
            mask, steps = queue.popleft()

            if mask == 0:
                return steps

            for i in range(m):
                for j in range(n):
                    bit = i * n + j

                    if not (mask & (1 << bit)):
                        continue

                    next_mask = mask

                    for col in range(n):
                        next_mask &= ~(1 << (i * n + col))

                    for row in range(m):
                        next_mask &= ~(1 << (row * n + j))

                    if next_mask not in visited:
                        visited.add(next_mask)
                        queue.append((next_mask, steps + 1))

        return -1

solution = Solution()

assert solution.removeOnes([[1,1,1],[1,1,1],[0,1,0]]) == 2  # Provided example 1

assert solution.removeOnes([[0,1,0],[1,0,1],[0,1,0]]) == 2  # Provided example 2

assert solution.removeOnes([[0,0],[0,0]]) == 0  # Already empty matrix

assert solution.removeOnes([[1]]) == 1  # Single cell with one

assert solution.removeOnes([[0]]) == 0  # Single cell with zero

assert solution.removeOnes([[1,1,1,1]]) == 1  # Single row

assert solution.removeOnes([[1],[1],[1]]) == 1  # Single column

assert solution.removeOnes([[1,0],[0,1]]) == 2  # Diagonal ones

assert solution.removeOnes([[1,1],[1,1]]) == 1  # Entire matrix removable in one step

assert solution.removeOnes([[1,0,1],[0,1,0]]) == 2  # Sparse matrix

assert solution.removeOnes([[1,0,0],[0,0,0],[0,0,1]]) == 2  # Far apart ones
Test Why
[[1,1,1],[1,1,1],[0,1,0]] Verifies dense matrix behavior
[[0,1,0],[1,0,1],[0,1,0]] Verifies nontrivial optimal choices
[[0,0],[0,0]] Checks already solved case
[[1]] Smallest nonzero input
[[0]] Smallest zero input
[[1,1,1,1]] Tests single-row clearing
[[1],[1],[1]] Tests single-column clearing
[[1,0],[0,1]] Ensures disconnected ones handled correctly
[[1,1],[1,1]] Verifies one-operation full clear
[[1,0,1],[0,1,0]] Sparse configuration
[[1,0,0],[0,0,0],[0,0,1]] Multiple isolated components

Edge Cases

One important edge case is when the matrix already contains no 1s. A careless implementation might still enter the BFS loop and attempt unnecessary processing. In this solution, the initial mask becomes 0, and BFS immediately returns 0 operations.

Another important edge case is a matrix with only one row or one column. In these situations, a single operation can potentially clear every remaining 1 because the chosen row or column covers the entire matrix dimension. The implementation handles this naturally because row and column clearing logic is completely general.

A third subtle edge case is disconnected 1s that cannot be removed together efficiently. Greedy strategies often fail here because choosing the locally best operation may not minimize the global operation count. BFS avoids this issue by exploring all possible operation sequences level by level, guaranteeing optimality.

A final edge case involves repeated states reached through different operation orders. Without a visited set, the algorithm would revisit the same masks repeatedly and become extremely inefficient. The visited set ensures each state is processed exactly once.