Given a matrix arr[][] of size N * M, the task is to print the matrix after removing all rows and columns from the matrix which consists of 0s only.
Examples:
Input: arr[][] ={ { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1}, { 0, 1, 0, 1 } }
Output:
111
111
011
Explanation:
Initially, the matrix is as follows:
arr[][] = { { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } }
Removing the 2nd row modifies the matrix to:
arr[][] = { { 1, 1, 0, 1 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } }
Removing the 3rd column modifies the matrix to:
arr[][] = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 0, 1, 1 } }Input: arr={{0, 1}, {0, 1}}
Output:
1
1
Approach: The idea is to count the number of 0s in all the rows and columns of the matrix and check if any rows or columns consist only of 0s or not. If found to be true, then remove those rows or the columns of the matrix. Follow the steps below to solve the problem:
- Traverse the matrix and count 1s in rows and columns.
- Now, traverse over the loop again and check for the following:
- If the count of 1s is found to be 0 for any row, skip that row.
- If the count of 1s is found to be greater than 0 for any column, print that element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to remove the rows or columns from // the matrix which contains all 0s elements void removeZeroRowCol(vector<vector<int> >& arr) { // Stores count of rows int n = arr.size(); // col[i]: Stores count of 0s // in current column int col[n + 1] = { 0 }; // row[i]: Stores count of 0s // in current row int row[n + 1] = { 0 }; // Traverse the matrix for (int i = 0; i < n; ++i) { // Stores count of 0s // in current row int count = 0; for (int j = 0; j < n; ++j) { // Update col[j] col[j] += (arr[i][j] == 1); // Update count count += (arr[i][j] == 1); } // Update row[i] row[i] = count; } // Traverse the matrix for (int i = 0; i < n; ++i) { // If all elements of // current row is 0 if (row[i] == 0) { continue; } for (int j = 0; j < n; ++j) { // If all elements of // current column is 0 if (col[j] != 0) cout << arr[i][j]; } cout << "\n"; } } // Driver Code int main() { vector<vector<int> > arr = { { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } }; // Function Call removeZeroRowCol(arr); return 0; } |
Java
// Java program for the above approach import java.io.*;class GFG{ // Function to remove the rows or columns from // the matrix which contains all 0s elements static void removeZeroRowCol(int arr[][]) { // Stores count of rows int n = arr.length; // col[i]: Stores count of 0s // in current column int col[] = new int[n + 1]; // row[i]: Stores count of 0s // in current row int row[] = new int[n + 1]; // Traverse the matrix for(int i = 0; i < n; ++i) { // Stores count of 0s // in current row int count = 0; for(int j = 0; j < n; ++j) { if (arr[i][j] == 1) // Update col[j] col[j] += 1; else col[j] += 0; if (arr[i][j] == 1) // Update count count += 1; else count += 0; } // Update row[i] row[i] = count; } // Traverse the matrix for(int i = 0; i < n; ++i) { // If all elements of // current row is 0 if (row[i] == 0) { continue; } for(int j = 0; j < n; ++j) { // If all elements of // current column is 0 if (col[j] != 0) System.out.print(arr[i][j]); } System.out.println(); } } // Driver Code public static void main (String[] args) { int arr[][] = { { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } }; // Function Call removeZeroRowCol(arr); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach # Function to remove the rows or columns from # the matrix which contains all 0s elements def removeZeroRowCol(arr) : # Stores count of rows n = len(arr) # col[i]: Stores count of 0s # in current column col = [0] * (n + 1) # row[i]: Stores count of 0s # in current row row = [0] * (n + 1) # Traverse the matrix for i in range(n) : # Stores count of 0s # in current row count = 0 for j in range(n) : # Update col[j] col[j] += (arr[i][j] == 1) # Update count count += (arr[i][j] == 1) # Update row[i] row[i] = count # Traverse the matrix for i in range(n) : # If all elements of # current row is 0 if (row[i] == 0) : continue for j in range(n) : # If all elements of # current column is 0 if (col[j] != 0) : print(arr[i][j], end = "") print() arr = [ [ 1, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 1, 1, 0, 1 ], [ 0, 1, 0, 1 ] ] # Function Call removeZeroRowCol(arr)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approach using System;class GFG{ // Function to remove the rows or columns from // the matrix which contains all 0s elements static void removeZeroRowCol(int[,] arr) { // Stores count of rows int n = arr.GetLength(0); // col[i]: Stores count of 0s // in current column int[] col = new int[n + 1]; // row[i]: Stores count of 0s // in current row int[] row = new int[n + 1]; // Traverse the matrix for(int i = 0; i < n ; ++i) { // Stores count of 0s // in current row int count = 0; for(int j = 0; j < n ; ++j) { if (arr[i, j] == 1) // Update col[j] col[j] += 1; else col[j] += 0; if (arr[i, j] == 1) // Update count count += 1; else count += 0; } // Update row[i] row[i] = count; } // Traverse the matrix for(int i = 0; i < n; ++i) { // If all elements of // current row is 0 if (row[i] == 0) { continue; } for(int j = 0; j < n; ++j) { // If all elements of // current column is 0 if (col[j] != 0) Console.Write(arr[i, j]); } Console.WriteLine(); } } // Driver Code public static void Main (String[] args) { int[,] arr = { { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } }; // Function Call removeZeroRowCol(arr); }}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program to implement// the above approach// Function to remove the rows or columns from // the matrix which contains all 0s elements function removeZeroRowCol(arr) { // Stores count of rows let n = arr.length; // col[i]: Stores count of 0s // in current column let col = Array.from({length: n+1}, (_, i) => 0); // row[i]: Stores count of 0s // in current row let row = Array.from({length: n+1}, (_, i) => 0); // Traverse the matrix for(let i = 0; i < n; ++i) { // Stores count of 0s // in current row let count = 0; for(let j = 0; j < n; ++j) { if (arr[i][j] == 1) // Update col[j] col[j] += 1; else col[j] += 0; if (arr[i][j] == 1) // Update count count += 1; else count += 0; } // Update row[i] row[i] = count; } // Traverse the matrix for(let i = 0; i < n; ++i) { // If all elements of // current row is 0 if (row[i] == 0) { continue; } for(let j = 0; j < n; ++j) { // If all elements of // current column is 0 if (col[j] != 0) document.write(arr[i][j]); } document.write("<br/>"); } } // Driver Code let arr = [[ 1, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 1, 1, 0, 1 ], [ 0, 1, 0, 1 ]]; // Function Call removeZeroRowCol(arr); // This code is contributed by souravghosh0416.</script> |
Output
111 111 011
Time complexity: O(N*M)
Auxiliary Space: O(N+M)
Another efficient approach: The idea is to mark all rows and columns that contain all zeros with some other special integer (a value that is not present in the matrix) to identify that we do not need that particular row or column and whenever we reach While iterating over the matrix on that particular integer we skip that cell because we assume that the cell has been removed while deletion of the row or column which has all zeros.
Follow the below steps to implement the idea:
- Iterate over all rows one by one and check if that particular row contains all zeros or not.
If, particular row contains all zeros then fill special integer to mark that row containing all zeros. - Iterate over all columns one by one and check if that particular column contains all zeros or not.
If, particular column contains all zeros then fill special integer to mark that column containing all zeros. - Iterate over the matrix and check if any particular cell is marked with special integer.
If yes, then skip that cell.
Otherwise, print that cell.
Below is the implementation of above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to mark all row and column// to special integer which contains all zerosvoid removeZeroRowCol(vector<vector<int> >& A){ int i, j, m, n; m = A.size(); if (m != 0) n = A[0].size(); // Traversing by row for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete row do // not contain only zeros if (A[i][j] == 1) break; } // If found that the complete row // contain zero if (j == n) { for (j = 0; j < n; j++) A[i][j] = -1; } } // Traversing by column for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete column // do not contain all zeros if (A[j][i] == 1) break; } // If found that the complete column // contain only zeros if (j == n) { for (j = 0; j < n; j++) A[j][i] = -1; } }}// Function to print the matrixvoid print(vector<vector<int> >& A){ int i, j, m, n; m = A.size(); if (m != 0) n = A[0].size(); // Taking a flag which helps us in printing // the matrix because if we found that the above // row is contain only zero then we won't go to next // line otherwise there will be space between // two consecutive rows bool flag = false; // Iterating over matrix for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { if (A[i][j] != -1) { cout << A[i][j]; // Making flag true if row get // printed flag = true; } } // If row got printed then moving to the // next line if (flag) { cout << endl; flag = !flag; } }}// Driver codeint main(){ // Initializing matrix vector<vector<int> > arr{ { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } }; // Function calling removeZeroRowCol(arr); // Function to print the matrix print(arr); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Java code to implement the above approach // Function to mark all row and column // to special integer which contains all zeros static void removeZeroRowCol(int[][] A) { int i = 0, j = 0, m = A.length, n = 0; if (m != 0) n = A[0].length; // Traversing by row for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete row do // not contain only zeros if (A[i][j] == 1) break; } // If found that the complete row // contain zero if (j == n) { for (j = 0; j < n; j++) A[i][j] = -1; } } // Traversing by column for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete column // do not contain all zeros if (A[j][i] == 1) break; } // If found that the complete column // contain only zeros if (j == n) { for (j = 0; j < n; j++) A[j][i] = -1; } } } private static void e() { } // Function to print the matrix static void print(int[][] A) { int i = 0, j = 0, m = 0, n = 0; m = A.length; if (m != 0) n = A[0].length; // Taking a flag which helps us in printing // the matrix because if we found that the above // row is contain only zero then we won't go to next // line otherwise there will be space between // two consecutive rows boolean flag = false; // Iterating over matrix for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { if (A[i][j] != -1) { System.out.print(A[i][j]); // Making flag true if row get // printed flag = true; } } // If row got printed then moving to the // next line if (flag) { System.out.println(); flag = !flag; } } } // Driver Code public static void main(String args[]) { // Initializing matrix int[][] arr = { { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } }; // Function calling removeZeroRowCol(arr); // Function to print the matrix print(arr); }}// This code is contributed by shinjanpatra |
Python3
# Python code to implement the above approach# Function to mark all row and column# to special integer which contains all zerosdef removeZeroRowCol(A): m = len(A) if (m != 0): n = len(A[0]) i,j = 0,0 # Traversing by row for i in range(m): for j in range(n): # If found that the complete row do # not contain only zeros if (A[i][j] == 1): break # If found that the complete row # contain zero if (j == n-1): for j in range(n): A[i][j] = -1 # Traversing by column for i in range(m): for j in range(n): # If found that the complete column # do not contain all zeros if (A[j][i] == 1): break # If found that the complete column # contain only zeros if (j == n-1): for j in range(n): A[j][i] = -1 # Function to print the matrixdef Print(A): m = len(A) if (m != 0): n = len(A[0]) # Taking a flag which helps us in printing # the matrix because if we found that the above # row is contain only zero then we won't go to next # line otherwise there will be space between # two consecutive rows flag = False # Iterating over matrix for i in range(m): for j in range(n): if (A[i][j] != -1): print(A[i][j],end="") # Making flag true if row get # printed flag = True # If row got printed then moving to the # next line if (flag): print() flag = False if (flag == True) else True # Driver code# Initializing matrixarr = [ [ 1, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 1, 1, 0, 1 ], [ 0, 1, 0, 1 ] ]# Function callingremoveZeroRowCol(arr)# Function to print the matrixPrint(arr)# This code is contributed by shinjanpatra |
C#
using System;using System.Collections.Generic;class GFG { // Java code to implement the above approach // Function to mark all row and column // to special integer which contains all zeros static void removeZeroRowCol(int[,] A) { int i = 0, j = 0, m = A.GetLength(0), n = 0; if (m != 0) n = A.GetLength(1); // Traversing by row for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete row do // not contain only zeros if (A[i,j] == 1) break; } // If found that the complete row // contain zero if (j == n) { for (j = 0; j < n; j++) A[i,j] = -1; } } // Traversing by column for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete column // do not contain all zeros if (A[j,i] == 1) break; } // If found that the complete column // contain only zeros if (j == n) { for (j = 0; j < n; j++) A[j,i] = -1; } } } private static void e() { } // Function to print the matrix static void print(int[,] A) { int i = 0, j = 0, m = 0, n = 0; m = A.GetLength(0); if (m != 0) n = A.GetLength(1); // Taking a flag which helps us in printing // the matrix because if we found that the above // row is contain only zero then we won't go to next // line otherwise there will be space between // two consecutive rows bool flag = false; // Iterating over matrix for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { if (A[i,j] != -1) { Console.Write(A[i,j]); // Making flag true if row get // printed flag = true; } } // If row got printed then moving to the // next line if (flag) { Console.WriteLine(); flag = !flag; } } } // Driver Code public static void Main(string[] args) { // Initializing matrix int[,] arr = { { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } }; // Function calling removeZeroRowCol(arr); // Function to print the matrix print(arr); }}// This code is contributed by phasing17 |
Javascript
// JS code to implement the above approach// Function to mark all row and column// to special integer which contains all zerosfunction removeZeroRowCol(A){ let m = A.length if (m != 0) n = A[0].length let i = 0, j = 0 // Traversing by row for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete row do // not contain only zeros if (A[i][j] == 1) break } // If found that the complete row // contain zero if (j == n-1) for (j = 0; j < n; j++) A[i][j] = -1 } // Traversing by column for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { // If found that the complete column // do not contain all zeros if (A[j][i] == 1) break } // If found that the complete column // contain only zeros if (j == n-1) for (j = 0; j < n; j++) A[j][i] = -1 }} // Function to print the matrixfunction Print(A){ let m = A.length if (m != 0) n = A[0].length // Taking a flag which helps us in printing // the matrix because if we found that the above // row is contain only zero then we won't go to next // line otherwise there will be space between // two consecutive rows flag = false // Iterating over matrix for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { if (A[i][j] != -1) { process.stdout.write(A[i][j] + "") // Making flag true if row get // printed flag = true } } // If row got printed then moving to the // next line if (flag) { console.log() flag = !flag } }}// Driver code// Initializing matrixlet arr = [ [ 1, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 1, 1, 0, 1 ], [ 0, 1, 0, 1 ] ]// Function callingremoveZeroRowCol(arr)// Function to print the matrixPrint(arr)// This code is contributed by phasing17 |
Output
111 111 011
Time complexity: O(N*M)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
