Given a binary matrix, mat[][] of dimensions N * M, the task is to maximize the count of rows consisting only of equal elements by selecting any column of the matrix and flipping all the elements of that column in each operation. Print the maximum number of rows that can be made to form equal elements.
Examples:
Input: mat[][] = { { 0, 1, 0, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 1, 0 } }Â
Output: 2Â
Explanation:Â
Select the 2nd column and flip all the elements of that column to modify mat[][] to { { 0, 0, 0, 0, 1 }, { 1, 0, 0, 1, 1 }, { 1, 1, 1, 1, 0 } }Â
Select the 5th column and flip all the elements of that column to modify mat[][] to { { 0, 0, 0, 0, 0 }, { 1, 0, 0, 1, 0 }, { 1, 1, 1, 1, 1 } }Â
Since all elements of the 1st row and the 3rd row of the matrix are equal and is also the maximum number of rows that can be made to contain equal elements only, the required output is 2.
Input: mat[][] = { {0, 0}, {0, 1} }Â
Output: 1Â
Â
Naive Approach: The simplest approach to solve this problem is to count the number of rows which contains equal elements only, for every possible way of selecting a combination of columns and flipping its elements. Finally, print the maximum count obtained for any of the above combinations.Â
Time Complexity: O(N * M * 2M)Â
Auxiliary Space: O(N * M)
Efficient Approach: To optimize the above approach, the idea is based on the fact that, if one row is 1‘s complement of the other row or both rows are the same, then only both the rows will contain equal elements only by performing the given operations.
Illustration:
Let us consider the following matrix:
Â
1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 In the above matrix, 1st and 2nd rows are 1’s complement of each other, and the 5th and 4th rows are 1’s complement of each other.Â
Â
Follow the steps below to solve the problem:
- Initialize a variable, say cntMaxRows, to store the maximum count of rows consisting of equal elements only.
- Initialize a Map, say mp, to store all possible rows of the matrix.
- Traverse each row of the matrix and store it in the Map.
- Traverse each row of the matrix using variable row. Calculate 1‘s complement of row and update cntMaxRows = max(cntMaxRows, mp[row] + mp[1’s_comp_row])Â
 - Finally, print the value of cntMaxRows.
Below is the implementation of our approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std;   // Function to find the maximum number // of rows containing all equal elements int maxEqrows(vector<vector<int> >& mat,               int N, int M) {       // Store each row of the matrix     map<vector<int>, int> mp;       // Traverse each row of the matrix     for (int i = 0; i < N; i++) {           // Update frequency of         // current row         mp[(mat[i])]++;     }       // Stores maximum count of rows     // containing all equal elements     int cntMaxRows = 0;       // Traverse each row of the matrix     for (int i = 0; i < N; i++) {           // Stores 1's complement         // of the current row         vector<int> onesCompRow(M, 0);           // Traverse current row         // of the given matrix         for (int j = 0; j < M; j++) {               // Stores 1s complement of             // mat[i][j]             onesCompRow[j]                 = (mat[i][j] ^ 1);         }           // Update cntMaxRows         cntMaxRows = max(cntMaxRows,                          mp[(mat[i])] + mp[onesCompRow]);     }       return cntMaxRows; }   // Driver Code int main() {     vector<vector<int> > mat         = { { 0, 1, 0, 0, 1 },             { 1, 1, 0, 1, 1 },             { 1, 0, 1, 1, 0 } };       // Stores count of rows     int N = mat.size();       // Stores count of columns     int M = mat[0].size();       cout << maxEqrows(mat, N, M); } |
Java
// Java program to implement import java.util.*; class GFG {   // Function to find the maximum number   // of rows containing all equal elements   static int maxEqrows(Vector<Vector<Integer>> mat,                        int N, int M)   {       // Store each row of the matrix     HashMap<Vector<Integer>, Integer> mp = new HashMap<>();       // Traverse each row of the matrix     for (int i = 0; i < N; i++)     {         // Update frequency of       // current row       if(mp.containsKey(mat.get(i)))       {         mp.put(mat.get(i), mp.get(mat.get(i)) + 1);       }       else      {         mp.put(mat.get(i), 1);       }     }       // Stores maximum count of rows     // containing all equal elements     int cntMaxRows = 0;       // Traverse each row of the matrix     for (int i = 0; i < N; i++)     {         // Stores 1's complement       // of the current row       Vector<Integer> onesCompRow = new Vector<Integer>();       for(int j = 0; j < M; j++)       {         onesCompRow.add(0);       }         // Traverse current row       // of the given matrix       for (int j = 0; j < M; j++)       {           // Stores 1s complement of         // mat[i][j]         onesCompRow.set(j, mat.get(i).get(j) ^ 1);       }         // Update cntMaxRows       if(!mp.containsKey(mat.get(i)))       {         cntMaxRows = Math.max(cntMaxRows, mp.get(onesCompRow));       }       else if(!mp.containsKey(onesCompRow))       {         cntMaxRows = Math.max(cntMaxRows, mp.get(mat.get(i)));       }       else      {         cntMaxRows = Math.max(cntMaxRows, mp.get(mat.get(i)) +                               mp.get(onesCompRow));       }     }     return cntMaxRows;   }     // Driver code   public static void main(String[] args)   {     Vector<Vector<Integer>> mat = new Vector<Vector<Integer>>();     mat.add(new Vector<Integer>());     mat.add(new Vector<Integer>());     mat.add(new Vector<Integer>());     mat.get(0).add(0);     mat.get(0).add(1);     mat.get(0).add(0);     mat.get(0).add(0);     mat.get(0).add(1);            mat.get(1).add(1);     mat.get(1).add(1);     mat.get(1).add(0);     mat.get(1).add(1);     mat.get(1).add(1);     mat.get(2).add(1);     mat.get(2).add(0);     mat.get(2).add(1);     mat.get(2).add(1);     mat.get(2).add(0);       // Stores count of rows     int N = mat.size();       // Stores count of columns     int M = mat.get(0).size();         System.out.println(maxEqrows(mat, N, M));   } }   // This code is contributed by divyesh072019 |
Python3
# Python3 program to implement # the above approach from collections import defaultdict   # Function to find the maximum number # of rows containing all equal elements def maxEqrows(mat, N, M):         # Store each row of the matrix     mp = defaultdict(lambda : 0)       # Traverse each row of the matrix     for i in range(N):           # Update frequency of         # current row         key = tuple(mat[i])         mp[key] += 1;               # Stores maximum count of rows     # containing all equal elements     cntMaxRows = 0;       # Traverse each row of the matrix     for i in range(N):           # Stores 1's complement         # of the current row         onesCompRow = []           # Traverse current row         # of the given matrix         for j in range(M):               # Stores 1s complement of             # mat[i][j]             onesCompRow.append(mat[i][j] ^ 1);                   # Update cntMaxRows         key = tuple(mat[i])         cntMaxRows = max(cntMaxRows, mp[key] + mp[tuple(onesCompRow)]);       return cntMaxRows;     # Driver code   mat = [] mat.append([ 0, 1, 0, 0, 1 ]); mat.append([ 1, 1, 0, 1, 1 ]); mat.append([ 1, 0, 1, 1, 0 ]);   # Stores count of rows N = len(mat);   # Stores count of columns M = len(mat[0]);   print(maxEqrows(mat, N, M));   # This code is contributed by phasing17 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic;  class GFG {     // Function to find the maximum number   // of rows containing all equal elements   static int maxEqrows(List<List<int>> mat, int N, int M)   {       // Store each row of the matrix     Dictionary<List<int>, int> mp = new Dictionary<List<int>, int>();       // Traverse each row of the matrix     for (int i = 0; i < N; i++) {         // Update frequency of       // current row       if(mp.ContainsKey(mat[i]))       {         mp[(mat[i])]++;       }       else{         mp[(mat[i])] = 1;       }     }       // Stores maximum count of rows     // containing all equal elements     int cntMaxRows = 0;       // Traverse each row of the matrix     for (int i = 0; i < N; i++) {         // Stores 1's complement       // of the current row       List<int> onesCompRow = new List<int>();       for(int j = 0; j < M; j++)       {         onesCompRow.Add(0);       }         // Traverse current row       // of the given matrix       for (int j = 0; j < M; j++) {           // Stores 1s complement of         // mat[i][j]         onesCompRow[j] = (mat[i][j] ^ 1);       }         // Update cntMaxRows       if(!mp.ContainsKey(mat[i]))       {         cntMaxRows = Math.Max(cntMaxRows, mp[onesCompRow] + 1);       }       else if(!mp.ContainsKey(onesCompRow))       {         cntMaxRows = Math.Max(cntMaxRows, mp[(mat[i])] + 1);       }       else{         cntMaxRows = Math.Max(cntMaxRows, mp[(mat[i])] + mp[onesCompRow] + 1);       }     }       return cntMaxRows;   }     // Driver code   static void Main() {     List<List<int>> mat = new List<List<int>>();     mat.Add(new List<int> { 0, 1, 0, 0, 1 });     mat.Add(new List<int> { 1, 1, 0, 1, 1 });     mat.Add(new List<int> { 1, 0, 1, 1, 0 });       // Stores count of rows     int N = mat.Count;       // Stores count of columns     int M = mat[0].Count;       Console.WriteLine(maxEqrows(mat, N, M));   } }   // This code is contributed by divyeshrabadiya07 |
Javascript
// JS program to implement // the above approach   // Function to find the maximum number // of rows containing all equal elements function maxEqrows(mat, N, M) {       // Store each row of the matrix     let mp = {}       // Traverse each row of the matrix     for (let i = 0; i < N; i++)     {           // Update frequency of         // current row         let key = mat[i].join("#")         if (mp.hasOwnProperty(key)) {             mp[key] += 1;         }         else {             mp[key] = 1;         }     }             // Stores maximum count of rows     // containing all equal elements     let cntMaxRows = 0;       // Traverse each row of the matrix     for (let i = 0; i < N; i++) {           // Stores 1's complement         // of the current row         let onesCompRow = []           // Traverse current row         // of the given matrix         for (let j = 0; j < M; j++) {               // Stores 1s complement of             // mat[i][j]             onesCompRow.push(mat[i][j] ^ 1);                   }                               // Update cntMaxRows         let key = mat[i].join("#")         if (!mp.hasOwnProperty(key)) {             cntMaxRows                 = Math.max(cntMaxRows, mp[onesCompRow] + 1);         }         else if (!mp.hasOwnProperty(onesCompRow)) {             cntMaxRows                 = Math.max(cntMaxRows, mp[key] + 1);         }         else {             cntMaxRows = Math.max(                 cntMaxRows,                 mp[(mat[i])] + mp[onesCompRow] + 1);         }     }       return cntMaxRows; }   // Driver code   let mat = [] mat.push([ 0, 1, 0, 0, 1 ]); mat.push([ 1, 1, 0, 1, 1 ]); mat.push([ 1, 0, 1, 1, 0 ]);   // Stores count of rows let N = mat.length;   // Stores count of columns let M = mat[0].length;   console.log(maxEqrows(mat, N, M));   // This code is contributed by phasing17 |
Output:Â
2
Â
Time Complexity: O(N * M)Â
Auxiliary Space: O(M)
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!
