2174. Remove All Ones With Row and Column Flips II

MediumBit ManipulationBreadth-First SearchArrayMatrix
Leetcode Link

Problem Description

Given a matrix grid with dimensions m x n which contains only binary values (0s and 1s), the task is to perform a series of operations to remove all the 1s from the grid. For each operation, you may choose any cell that has a 1, identified by coordinates i and j. The constraints for these coordinates are 0 <= i < m and 0 <= j < n. When you select a cell with a 1, all the values in its row i and column j are changed to 0s. The goal is to find the minimum number of these operations required to turn every 1 in the grid into a 0.

Intuition

The solution to this problem involves simulating the process of zeroes spreading through rows and columns as we select cells with 1s and change their respective rows and columns to 0. However, directly simulating upon the grid itself would be inefficient and complex, especially since we need to keep track of the grid state after each operation. This is where the concept of bitmasking comes into play, providing a compact representation of the grid's state.

To grasp the intuition behind the solution, let's consider a few key points:

  1. Each cell in the grid can be represented by a single bit in a bitmask – a 1 indicates the presence of a 1 at that cell in the grid, and a 0 indicates a 0.

  2. By applying bitwise operations, we can simulate the operation that changes an entire row and column to 0s. Specifically, we can clear the bits corresponding to the selected cell's row and column in the bitmask.

  3. We use a breadth-first search (BFS) strategy to explore the minimum number of operations needed. We start with the initial state of the grid and generate new states after each operation. Each generated state represents the grid configuration after setting a particular row and column to 0s.

  4. To avoid repeated work, we keep track of the visited states using a set. Each time we generate a new state, we check if we've encountered this state previously. If not, we add it to the queue for further exploration.

  5. The BFS will continue until we reach a state where all bits are 0, indicating all 1s have been removed from the grid. When this state is reached, we return the number of operations performed.

Overall, the solution approach leverages bitwise operations and BFS search to simulate the process in an efficient way, avoiding unnecessary recomputation and keeping track of the grid's changing states.

Solution Approach

The implementation provided defines a Python class Solution with a single method removeOnes, responsible for computing the minimum number of operations to remove all ones ('1's) from a given grid.

  1. Initialize Variables: The solution starts by capturing the dimensions of the grid with m and n. It then creates a bitmask, state, to represent the initial state of the grid. Each bit in state corresponds to an element in the grid, and the bit is set to 1 if the grid element is 1.

  2. Breadth-First Search Setup: A queue q and a set vis are initialized to support the BFS process:

    • q: a deque (double-ended queue from Python's collections module) initially containing the starting bitmask.
    • vis: a set to record all visited states, starting with the initial state to prevent revisiting the same configuration.
  3. BFS Algorithm: The BFS algorithm iterates through each level (all states in the queue q). At each state, it checks if state equals 0, which implies that all ones are removed from the grid, allowing it to return the current number of steps (ans) taken.

    For every state, it will iterate through all possible selections of cells containing a 1 (i.e., for all i and j if grid[i][j] == 1). For each selected cell, the implementation crafts the next state nxt by:

    • Clearing bits that correspond to the selected cell's entire row.
    • Clearing bits that correspond to the selected cell's entire column.

    These operations are performed using bitwise AND and NOT: nxt &= ~(1 << (r * n + j)) for row clearing, nxt &= ~(1 << (i * n + c)) for column clearing.

  4. Check and Update Visited States: If this nxt state has not been visited (nxt not in vis), it's added to both the vis set and the q queue to be processed in subsequent iterations.

  5. Increment Operation Counter: Once all states at the current level are processed, the operation counter is incremented by 1 to reflect an additional step taken in the BFS traversal.

  6. BFS Completion: The BFS continues until either the grid is clear of ones (signaled by reaching a state where state == 0) or all possibilities are exhausted, which in theory should not happen since the problem implies there will always be a solution. If the grid is cleared, the minimum number of operations taken to achieve that (ans) is returned.

Overall, this approach combines bitmasking to represent grid states compactly and BFS to efficiently search for the minimal sequence of operations to remove all ones from the grid.

Example Walkthrough

Let's use a small 2x3 grid example to illustrate the solution approach:

Imagine we have the following grid:

1grid = [
2  [1, 0, 1],
3  [0, 1, 0]
4]

We'll walk through the BFS algorithm using this example:

  1. Initialize Variables: Our grid is 2x3, so m = 2 and n = 3. We initialize the state bitmask such that it represents the grid; in this case state = 101010 in binary (each row concatenated), which is 42 in decimal.

  2. Breadth-First Search Setup: Queue q is initialized with the starting state q = deque([42]), and visited set vis = {42} to record the starting state.

  3. BFS Algorithm: We start by dequeuing the initial state (42) and checking if it's zero. Since it's not, we proceed to explore potential operations:

    For the given state, we can choose three cells with a 1 (grid[0][0], grid[0][2], grid[1][1]).

    • Select cell (0,0): This zeroes out the entire first row and first column, resulting in nxt state 000000 or 0 in decimal.
    • Select cell (0,2): This zeroes out the entire first row and third column, resulting in nxt state 000000 or 0 in decimal.
    • Select cell (1,1): This zeroes out the second row and second column, but it won't clear all 1s because of the 1 in (0,2), so nxt state = 001000 or 8 in decimal.

    Let's consider we choose cell (0,0), which clears the grid entirely. Thus, we obtain a nxt state which is zero, and we can add it to the visited set and queue if it isn't already visited.

  4. Check and Update Visited States: Since state 0 has not been visited yet, it's added to the set vis. But since the state is 0, it indicates that all 1s are cleared, and we do not need to enqueue it.

  5. Increment Operation Counter: At this point, we've found that it takes one operation to clear this grid. Therefore, ans = 1.

  6. BFS Completion: We have an empty grid now, so we terminate the BFS and return the answer. The minimum number of operations to clear the grid of ones is 1.

In this small example, the process was straightforward because choosing either (0,0) or (0,2) clears the grid in just one operation. In larger grids, the BFS would continue until all ones are cleared, possibly taking multiple levels of iterations.

Python Solution

1from collections import deque
2
3class Solution:
4    def removeOnes(self, grid):
5        # Get the dimensions of the grid
6        rows, columns = len(grid), len(grid[0])
7      
8        # Calculate the initial state by converting the grid to a bitmask
9        initial_state = sum(1 << (row * columns + col) for row in range(rows) for col in range(columns) if grid[row][col])
10      
11        # Initialize the queue with the initial state and a set for visited states
12        queue = deque([initial_state])
13        visited = {initial_state}
14      
15        # Counter for the number of steps
16        steps = 0
17      
18        # Perform a breadth-first search
19        while queue:
20            # Iterate through all states at the current level
21            for _ in range(len(queue)):
22                state = queue.popleft()
23              
24                # If the state is 0, all ones have been removed
25                if state == 0:
26                    return steps
27              
28                # Try turning off each 1 in the grid
29                for row in range(rows):
30                    for col in range(columns):
31                        if grid[row][col] == 1:
32                            next_state = state
33                          
34                            # Turn off all bits in the same column
35                            for r in range(rows):
36                                next_state &= ~(1 << (r * columns + col))
37
38                            # Turn off all bits in the same row
39                            for c in range(columns):
40                                next_state &= ~(1 << (row * columns + c))
41                          
42                            # If the next state hasn't been visited, add it to the queue and visited set
43                            if next_state not in visited:
44                                visited.add(next_state)
45                                queue.append(next_state)
46          
47            # Increment the number of steps after checking all states at the current level
48            steps += 1
49      
50        # If no solution is found, return -1
51        return -1
52

Java Solution

1import java.util.ArrayDeque;
2import java.util.Deque;
3import java.util.HashSet;
4import java.util.Set;
5
6class Solution {
7  
8    public int removeOnes(int[][] grid) {
9        int rows = grid.length, cols = grid[0].length;
10      
11        // Initialize state to represent the grid using bit manipulation
12        int initialState = 0;
13        for (int i = 0; i < rows; ++i) {
14            for (int j = 0; j < cols; ++j) {
15                if (grid[i][j] == 1) {
16                    initialState |= 1 << (i * cols + j);
17                }
18            }
19        }
20      
21        // Set up a queue for BFS approach and a set to keep track of visited states
22        Deque<Integer> queue = new ArrayDeque<>();
23        queue.offer(initialState);
24        Set<Integer> visited = new HashSet<>();
25        visited.add(initialState);
26      
27        // Level counter (answer) for the number of steps (transformations)
28        int steps = 0;
29      
30        while (!queue.isEmpty()) {
31            // Iterate over the current level
32            for (int k = queue.size(); k > 0; --k) {
33                int currentState = queue.poll();
34              
35                // If current state is all zeros, we're done
36                if (currentState == 0) {
37                    return steps;
38                }
39              
40                // Check each cell in the grid
41                for (int i = 0; i < rows; ++i) {
42                    for (int j = 0; j < cols; ++j) {
43                        if (grid[i][j] == 0) { // Skip if the original cell was zero
44                            continue;
45                        }
46                      
47                        // Calculate the new state after flipping row and column
48                        int nextState = currentState;
49                        for (int r = 0; r < rows; ++r) {
50                            nextState &= ~(1 << (r * cols + j));
51                        }
52                        for (int c = 0; c < cols; ++c) {
53                            nextState &= ~(1 << (i * cols + c));
54                        }
55                      
56                        // If we haven't encountered this state, add it to the queue
57                        if (!visited.contains(nextState)) {
58                            visited.add(nextState);
59                            queue.offer(nextState);
60                        }
61                    }
62                }
63            }
64            // Increment the number of steps after each level
65            ++steps;
66        }
67      
68        // -1 indicates that we can't achieve a grid with all zeros
69        return -1;
70    }
71}
72

C++ Solution

1class Solution {
2public:
3    int removeOnes(vector<vector<int>>& grid) {
4        int rows = grid.size(); // Get the number of rows in the grid
5        int cols = grid[0].size(); // Get the number of columns in the grid
6        int state = 0; // This will represent the current state of the grid using bits
7      
8        // Generate the initial state of the grid, where '1's are set in the state bit representation
9        for (int i = 0; i < rows; ++i) {
10            for (int j = 0; j < cols; ++j) {
11                if (grid[i][j]) {
12                    state |= (1 << (i * cols + j));
13                }
14            }
15        }
16
17        queue<int> q; // Queue for BFS (Breadth-First Search)
18        q.push(state); // Add initial state to the queue
19        unordered_set<int> visitedStates; // Set to keep track of visited states
20        visitedStates.insert(state); // Mark the initial state as visited
21        int steps = 0; // Counter for the number of steps taken to clear the grid
22
23        while (!q.empty()) {
24            // Process all states in the current level
25            for (int k = q.size(); k > 0; --k) {
26                state = q.front();
27                q.pop();
28
29                // If we reach a state where the grid is all zeros, return the number of steps taken
30                if (state == 0) return steps;
31
32                // Try flipping each row and column from each cell with a '1'
33                for (int i = 0; i < rows; ++i) {
34                    for (int j = 0; j < cols; ++j) {
35                        if ((state >> (i * cols + j)) & 1) { // Only proceed if the current cell is '1'
36                            int nextState = state;
37                            // Flip the entire row and column
38                            for (int r = 0; r < rows; ++r) nextState &= ~(1 << (r * cols + j));
39                            for (int c = 0; c < cols; ++c) nextState &= ~(1 << (i * cols + c));
40                          
41                            // If the resulting state has not been visited, add it to the queue
42                            if (!visitedStates.count(nextState)) {
43                                visitedStates.insert(nextState);
44                                q.push(nextState);
45                            }
46                        }
47                    }
48                }
49            }
50            ++steps; // Increment the step count after finishing a level of BFS
51        }
52
53        return -1; // If it's not possible to reach a state with all zeros, return -1
54    }
55};
56

Typescript Solution

1type Grid = number[][];
2
3// Helper function to get number of rows
4function getRows(grid: Grid): number {
5    return grid.length;
6}
7
8// Helper function to get number of columns
9function getCols(grid: Grid): number {
10    return grid[0].length;
11}
12
13// Function to generate the initial state of the grid as a bit representation
14function generateInitialState(grid: Grid): number {
15    let rows = getRows(grid);
16    let cols = getCols(grid);
17    let state = 0;
18  
19    for (let i = 0; i < rows; ++i) {
20        for (let j = 0; j < cols; ++j) {
21            if (grid[i][j]) {
22                state |= (1 << (i * cols + j));
23            }
24        }
25    }
26    return state;
27}
28
29// Remove Ones Function (Breadth-First Search to clear the grid)
30function removeOnes(grid: Grid): number {    
31    let rows = getRows(grid);
32    let cols = getCols(grid);
33    let state = generateInitialState(grid);
34  
35    let queue: number[] = []; // Queue for BFS
36    let visitedStates: Set<number> = new Set(); // Set to keep track of visited states
37
38    queue.push(state); // Add initial state to the queue
39    visitedStates.add(state); // Mark the initial state as visited
40    let steps = 0; // Counter for the number of steps taken to clear the grid
41  
42    while (queue.length > 0) {
43        // Process all states in the current level
44        let size = queue.length;
45        for (let k = 0; k < size; ++k) {
46            state = queue.shift() as number;
47
48            // If we reach a state where the grid is all zeros, return the number of steps taken
49            if (state === 0) return steps;
50          
51            // Try flipping each row and column from each cell with a '1'
52            for (let i = 0; i < rows; ++i) {
53                for (let j = 0; j < cols; ++j) {
54                    if ((state >> (i * cols + j)) & 1) { // Only proceed if the current cell is '1'
55                        let nextState = state;
56                        // Flip the entire row and column
57                        for (let r = 0; r < rows; ++r) nextState &= ~(1 << (r * cols + j));
58                        for (let c = 0; c < cols; ++c) nextState &= ~(1 << (i * cols + c));
59                      
60                        // If the resulting state has not been visited, add it to the queue
61                        if (!visitedStates.has(nextState)) {
62                            visitedStates.add(nextState);
63                            queue.push(nextState);
64                        }
65                    }
66                }
67            }
68        }
69        steps++; // Increment the step count after finishing a level of BFS
70    }
71
72    return -1; // If it's not possible to reach a state with all zeros, return -1
73}
74

Time and Space Complexity

The given Python code aims to find the minimum number of operations needed to convert a binary matrix to a matrix with all zeroes by flipping the elements of each row or column. The initial state of the binary matrix is represented by a single integer (state) using bit manipulation, where each bit of this integer corresponds to an element of the matrix.

Time Complexity:

The operation of flipping the elements in a row or column is equivalent to toggling bits in the state. The code uses Breadth-First Search (BFS) to explore all possible states generated by these operations. In the worst case, the algorithm will explore all possible states of the matrix.

  • The BFS will run at most 2^(m*n) iterations, since this is the maximum number of possible states, where m is the number of rows and n is the number of columns.
  • In each level of BFS, the algorithm iterates over m*n elements to check for the grid state, and then for each cell, if the cell in the original grid is 1, it performs bit manipulation across all rows and columns.
  • The bit manipulation runs in O(m+n) because we iterate over all rows for a given column and all columns for a given row.

Given the above, the upper bound on time complexity would be O((m*n) * 2^(m*n) * (m+n)).

However, because we quickly exhaust the search space due to the symmetry and constraints of the problem (since flipping a row followed by its corresponding column results in the same state as flipping the same column followed by the row), the real time complexity is generally less than this theoretical upper bound, but still exponential in terms of the size of the matrix.

Space Complexity:

The space complexity is determined by the storage of visited states and the BFS queue.

  • The vis set stores unique states to avoid revisiting the same configuration, which in the worst case will store all 2^(m*n) possible states.
  • The BFS queue could contain a large number of states at a given level. In the worst case, it can store all possible states that have not been visited.

This results in a space complexity of O(2^(m*n)), which is exponential with respect to the total number of elements in the matrix.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫