Algorithm

Problem Name: 1072. Flip Columns For Maximum Number of Equal Rows

Problem Link: https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
 

You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

Return the maximum number of rows that have all values equal after some number of flips.

 

Example 1:

Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is either 0 or 1.

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const maxEqualRowsAfterFlips = function(matrix) {
  let n = matrix.length,
    m = matrix[0].length;
  let ret = 0;
  for (let i = 0; i  <  n; i++) {
    let ct = 0;
    inner: for (let j = i; j  <  n; j++) {
      if (ae(matrix[i], matrix[j])) {
        ct++;
      } else {
        for (let k = 0; k  <  m; k++) {
          if (matrix[i][k] + matrix[j][k] !== 1) continue inner;
        }
        ct++;
      }
    }
    ret = Math.max(ret, ct);
  }
  return ret;
};

function ae(a1, a2) {
  if (a1.length !== a2.length) return false;
  for (let i = 0; i  <  a1.length; i++) {
    if (a1[i] !== a2[i]) return false;
  }
  return true;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
matrix = [[0,1],[1,1]]

Output

x
–
+
cmd
1

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        res = 0
        for row in matrix:
            inv = [1 - r for r in row]
            res = max(res, sum(row == r or inv == r for r in matrix))
        return res
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
matrix = [[0,1],[1,1]]

Output

x
–
+
cmd
1

#3 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCode
{
    public class _1072_FlipColumnsForMaximumNumberOfEqualRows
    {
        public int MaxEqualRowsAfterFlips(int[][] matrix)
        {
            int rows = matrix.Length;
            int cols = matrix[0].Length;

            var map = new Dictionary < string, int>();
            for (int r = 0; r  <  rows; r++)
            {
                var sb = new StringBuilder();
                int head = matrix[r][0];
                for (int c = 0; c  <  cols; c++)
                    sb.Append(head == matrix[r][c] ? '1' : '0');

                var str = sb.ToString();
                if (map.ContainsKey(str))
                    map[str]++;
                else
                    map[str] = 1;
            }

            return map.Values.Max();
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
matrix = [[0,1],[1,1]]

Output

x
–
+
cmd
1
Advertisements

Demonstration

Previous
#1071 Leetcode Greatest Common Divisor of Strings Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1073 Leetcode Adding Two Negabinary Numbers Solution in C, C++, Java, JavaScript, Python, C# Leetcode