Remove All Ones With Row and Column Flips Leetcode Solution

Problem Statement:

Remove All Ones With Row and Column Flips Leetcode Solution – You are given an m x n binary matrix grid.

In one operation, you can choose any row or column and flip each value in that row or column (i.e., changing all 0‘s to 1‘s, and all 1‘s to 0‘s).

Return true if it is possible to remove all 1‘s from grid using any number of operations or false otherwise.

Example:

Example 1:

Input : 
grid = [[0,1,0],[1,0,1],[0,1,0]]

Output: true

Explanation:

One possible way to remove all 1’s from the grid is to:
– Flip the middle row
– Flip the middle column

Example 2:

Input: 
grid = [[1,1,0],[0,0,0],[0,0,0]]

Output: false

Explanation:

It is impossible to remove all 1’s from the grid.

Approach:

Idea:

1. First, traverse the columns of the given grid and check if the element of the first row of that column equals 1 or not, if it is 1 then flip the value of grid[j][i], which means if the value of grid[j][i] is 0 then make it 1 and if it is 1 then make it 0.
2. After that, we start to traverse from the second row and initialize a sum variable to 0 and then traverse all the columns and add the value of the grid to the sum variable.
3. After coming from the inner loop we check if the sum equals 0 or equals the number of columns then we return false.
4. Finally, if we didn’t return a false in the loop and successfully come out of the outer loop, then we return true.

Code:

C++ Program of Remove All Ones With Row and Column Flips :

class Solution {
public:
    bool removeOnes(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        for(int i=0; i<m; i++){
            if(grid[0][i] == 1){
                for(int j=0; j<n; j++){
                    grid[j][i] = 1-grid[j][i];
                }
            }
        }
    
        for(int i=1; i<n; i++){
            int sum = 0;
            for(int j=0; j<m; j++){
                sum += grid[i][j];
            }
            if(sum != 0 && sum != m){
                return false;
            }
        }
        
        return true;
    }
};

Java Program for  Remove All Ones With Row and Column Flips :

class Solution {
    public boolean removeOnes(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        
        for(int i=0; i<m; i++){
            if(grid[0][i] == 1){
                for(int j=0; j<n; j++){
                    grid[j][i] = 1-grid[j][i];
                }
            }
        }
    
        for(int i=1; i<n; i++){
            int sum = 0;
            for(int j=0; j<m; j++){
                sum += grid[i][j];
            }
            if(sum != 0 && sum != m){
                return false;
            }
        }
        
        return true;
    }
}

Complexity Analysis for Remove All Ones With Row and Column Flips Leetcode Solution:

Time Complexity:

The Time Complexity of the code is O(N*M ) as we need to traverse through the given grid.

Space Complexity:

The Space Complexity of the code is O(1) because we don’t need any extra space to solve this problem.

Matrix Interview Practice Questions:

https://tutorialcup.com/interview/matrix