⚡Flashcard Drill➔
NeetCode #813LC-1072MediumGreedy
← Back to All Problems

#813 · #1072 · Flip Columns For Maximum Number of Equal Rows(按列翻转得到最大值等行数)

📌 Problem Statement & Constraints

You are given an m x n binary matrix. Choose any set of columns and flip every value in those columns. Return the maximum number of rows that can be made identical to each other after the flips. Constraints: 1 <= m, n <= 300, matrix[i][j] is 0 or 1.

💡 Core Algorithmic Approaches

  1. Two rows can be made equal by column flips if and only if they are equal or exact complements of each other.
  2. Normalise every row so it starts with 0: if a row begins with 1, conceptually flip it, replacing each bit v by v XOR row[0].
  3. Rows that normalise to the same pattern form a group that can be made identical simultaneously.
  4. The answer is the size of the largest group, because all rows in a group agree after the same column flips.

💻 Benchmark Python3 Implementation

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        from collections import Counter
        count = Counter()
        for row in matrix:
            base = row[0]
            # normalise so every row is compared in a form that starts with 0
            key = tuple(v ^ base for v in row)
            count[key] += 1
        return max(count.values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is touched once to build the normalised key.
💾 Space Complexity
O(m * n) for the counter keys in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing rows without normalisation: [0,1] and [1,0] are complements and can be made equal, but their raw forms differ.
  • Normalising with the wrong pivot: the pivot must be the row's own first bit, not a fixed column of the matrix.
  • Assuming only identical rows count: complements also belong to the same group, which is exactly what the XOR normalisation captures.
  • Forgetting that flipping columns is global: the same column set applies to all rows, so only rows that are identical after one shared flip set can be grouped -- which the normalisation test exactly characterises.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems