text: Open in App
  Not now
  
  # Maximize count of rows consisting of equal elements by flipping columns of a Matrix
  
  • Difficulty Level : Hard
  • Last Updated : 24 Mar, 2023
  
  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:
  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:
  
  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:
  
  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 ` `using` `namespace` `std; ` ` `  `// Function to find the maximum number ` `// of rows containing all equal elements ` `int` `maxEqrows(vector >& mat, ` `              ``int` `N, ``int` `M) ` `{ ` ` `  `    ``// Store each row of the matrix ` `    ``map, ``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 > 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> mat, ` `                       ``int` `N, ``int` `M)  ` `  ``{  ` ` `  `    ``// Store each row of the matrix  ` `    ``HashMap, 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 onesCompRow = ``new` `Vector(); ` `      ``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> mat = ``new` `Vector>(); ` `    ``mat.add(``new` `Vector()); ` `    ``mat.add(``new` `Vector()); ` `    ``mat.add(``new` `Vector()); ` `    ``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> mat, ``int` `N, ``int` `M)  ` `  ``{  ` ` `  `    ``// Store each row of the matrix  ` `    ``Dictionary, ``int``> mp = ``new` `Dictionary, ``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> mat = ``new` `List>(); ` `    ``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)
  
  My Personal Notes arrow_drop_up
  Related Articles
explanation: The provided text is a detailed explanation and implementation of an algorithm to solve a specific problem related to binary matrices. The problem is to maximize the count of rows consisting of equal elements by flipping columns of a matrix. The text includes:
  
  - A clear problem statement with examples.
  - A naive approach with its time and space complexity.
  - An efficient approach with a step-by-step explanation.
  - Implementations of the efficient approach in multiple programming languages (C++, Java, Python, C#, and JavaScript).
  
  The text does not contain a direct question or a question-and-answer format. It is primarily a technical explanation and code implementation.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: Open in App
  Not now
  
  # Maximize count of rows consisting of equal elements by flipping columns of a Matrix
  
  • Difficulty Level : Hard
  • Last Updated : 24 Mar, 2023
  
  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:
  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:
  
  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:
  
  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 ` `using` `namespace` `std; ` ` `  `// Function to find the maximum number ` `// of rows containing all equal elements ` `int` `maxEqrows(vector >& mat, ` `              ``int` `N, ``int` `M) ` `{ ` ` `  `    ``// Store each row of the matrix ` `    ``map, ``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 > 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> mat, ` `                       ``int` `N, ``int` `M)  ` `  ``{  ` ` `  `    ``// Store each row of the matrix  ` `    ``HashMap, 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 onesCompRow = ``new` `Vector(); ` `      ``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> mat = ``new` `Vector>(); ` `    ``mat.add(``new` `Vector()); ` `    ``mat.add(``new` `Vector()); ` `    ``mat.add(``new` `Vector()); ` `    ``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> mat, ``int` `N, ``int` `M)  ` `  ``{  ` ` `  `    ``// Store each row of the matrix  ` `    ``Dictionary, ``int``> mp = ``new` `Dictionary, ``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> mat = ``new` `List>(); ` `    ``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)
  
  My Personal Notes arrow_drop_up
  Related Articles
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a detailed explanation and implementation of an algorithm to solve a specific problem related to binary matrices. The problem is to maximize the count of rows consisting of equal elements by flipping columns of a matrix. The text includes:
  
  - A clear problem statement with examples.
  - A naive approach with its time and space complexity.
  - An efficient approach with a step-by-step explanation.
  - Implementations of the efficient approach in multiple programming languages (C++, Java, Python, C#, and JavaScript).
  
  The text does not contain a direct question or a question-and-answer format. It is primarily a technical explanation and code implementation.
  
  Label: no-question