Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1072.html

1072. Flip Columns For Maximum Number of Equal Rows (Medium)

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column.  Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: [[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.

 

Note:

  1. 1 <= matrix.length <= 300
  2. 1 <= matrix[i].length <= 300
  3. All matrix[i].length's are equal
  4. matrix[i][j] is 0 or 1

Solution 1.

  1. For each row, if the first element is not 0, flip the row.
  2. Find the maximum count of the rows having the same content.

Why does this work?

Let’s say “an array a is clean” if all the elements in a are the same.

If two rows a and b can become clean after flips, their xor result must also be clean.

For example, the following two arrays can be clean after flips

a:   0 1 0
b:   1 0 1
xor: 1 1 1

The following two can’t be both clean however you flip them.

a:   0 1 0
b:   1 1 1
xor: 1 0 1

If xor of row a and b is clean, then either a == b (a and b are identical) or a == ^b (a and b are inverted).

For a == ^b case, we can simply flip row b to make a == b'.

So to make sure all the arrays are aligned, we flip the arrays not starting with 0. And we can easily get the result by finding the maximum count of rows identical.

// OJ: https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int M = matrix.size(), N = matrix[0].size(), ans = 0;
        unordered_map<string, int> cnt;
        for (int i = 0; i < M; ++i) {
            string s;
            bool flip = matrix[i][0] == 1;
            for (int j = 0; j < N; ++j) s += flip ? ('1' - matrix[i][j]) : ('0' + matrix[i][j]);
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }
};

  • class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> patternCountMap = new HashMap<String, Integer>();
        for (int[] row : matrix) {
            int[] newArray = getRow(row);
            String rowStr = Arrays.toString(newArray);
            int count = patternCountMap.getOrDefault(rowStr, 0) + 1;
            patternCountMap.put(rowStr, count);
        }
        int maxCount = 0;
        Set<String> keySet = patternCountMap.keySet();
        for (String rowStr : keySet) {
            int count = patternCountMap.getOrDefault(rowStr, 0);
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    public int[] getRow(int[] row) {
        int length = row.length;
        int[] newArray = new int[length];
        if (row[0] == 0) {
            for (int i = 0; i < length; i++)
                newArray[i] = row[i];
        } else {
            for (int i = 0; i < length; i++)
                newArray[i] = 1 - row[i];
        }
        return newArray;
    }
}

############

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> map = new HashMap<>();
        for (int[] row : matrix) {
            if (row[0] == 1) {
                for (int i = 0; i < row.length; ++i) {
                    row[i] ^= 1;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int x : row) {
                sb.append(x);
            }
            String s = sb.toString();
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        return map.values().stream().max(Integer::compareTo).get();
    }
}


  • // OJ: https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& A) {
        int N = A[0].size(), ans = 0;
        unordered_map<string, int> cnt;
        for (auto &row : A) {
            bool flip = row[0] == 0;
            string s;
            for (int i = 0; i < N; ++i) s += '0' + (row[i] ^ flip);
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }
};

  • class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnt = Counter()
        for row in matrix:
            t = []
            for v in row:
                if row[0] == 1:
                    v ^= 1
                t.append(str(v))
            s = ''.join(t)
            cnt[s] += 1
        return max(cnt.values())

############

# 1072. Flip Columns For Maximum Number of Equal Rows
# https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        mp = collections.defaultdict(int)
        
        for r in matrix:
            A = []
            for c in r:
                A.append(r[0] ^ c)
            
            mp[tuple(A)] += 1
        
        return max(mp.values())


  • func maxEqualRowsAfterFlips(matrix [][]int) int {
	ans := 0
	cnt := map[string]int{}
	for _, row := range matrix {
		s := []byte{}
		for _, v := range row {
			if row[0] == 1 {
				v ^= 1
			}
			s = append(s, byte(v+'0'))
		}
		t := string(s)
		cnt[t]++
		ans = max(ans, cnt[t])
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

  • function maxEqualRowsAfterFlips(matrix: number[][]): number {
    const cnt = new Map<string, number>();
    let ans = 0;
    for (const row of matrix) {
        if (row[0] === 1) {
            for (let i = 0; i < row.length; i++) {
                row[i] ^= 1;
            }
        }
        const s = row.join('');
        cnt.set(s, (cnt.get(s) || 0) + 1);
        ans = Math.max(ans, cnt.get(s)!);
    }
    return ans;
}

All Problems

All Solutions