1072. Flip Columns For Maximum Number of Equal Rows - Detailed Explanation

Brute Force Implementation (Conceptual Example in Python)

Below is a conceptual Python implementation for brute force. This code is only practical for very small n (like n <= 10) to demonstrate the idea. It enumerates flips using bit masks for subsets of columns. (Do not use this for large inputs!)

def max_equal_rows_after_flips_bruteforce(matrix):
    m, n = len(matrix), len(matrix[0])
    max_count = 0
    # Iterate through all subsets of columns represented by bit masks 0 to 2^n - 1
    for mask in range(1 << n):  # 1<<n is 2^n
        count = 0
        # Check each row against this mask
        for row in matrix:
            # Determine if this row becomes all 0s or all 1s with this flip mask.
            # We apply the mask: if a bit in mask is 1, that column is flipped.
            # Simulate flipping: if mask has a 1 at j, take 1-row[j], else row[j] as is.
            flipped_row = [(1 - val) if (mask >> j) & 1 else val for j, val in enumerate(row)]
            # Check if flipped_row is uniform (all 0s or all 1s)
            if all(x == flipped_row[0] for x in flipped_row):
                count += 1
        max_count = max(max_count, count)
    return max_count

# Example usage (small matrix):
print(max_equal_rows_after_flips_bruteforce([[0,1],[1,0]]))  # Output: 2

This brute force approach correctly finds the result for small examples, but it will not scale to larger inputs due to the exponential number of combinations.

Approach 2: Using Patterns and Hash Map (Optimized Solution)

Explanation

The key observation is that we don't actually need to test every combination of flips. Instead, we can identify groups of rows that will always behave the same under any set of column flips. If two rows are identical, then any set of column flips will affect them in the same way, meaning they will either both become uniform or both not become uniform under that flips set. Similarly, if two rows are complements of each other (one is the exact inverse of the other, i.e., wherever one has 0 the other has 1, and vice versa), then any set of flips that makes one row all 0s will make the other all 1s, and vice versa. In other words, identical or complementary rows are tied together in terms of the flip outcomes. This suggests we should group rows into clusters where each cluster contains rows that are all identical or complementary to each other.

Within one such cluster, we can find a single flip strategy that makes all those rows uniform simultaneously:

• If the rows are identical originally, flipping the columns where those rows have 1s will turn all of them into all-0s (uniform). Alternatively, flipping the columns where those rows have 0s will turn them into all-1s – either yields uniform rows.

• If the rows are complements of each other, one flip strategy can make one row all 0s and at the same time make its complement all 1s. For example, if Row A = [0,1,0,1] and Row B = [1,0,1,0] (which is the complement of A), flipping the appropriate set of columns (columns where Row A has 1s) will result in Row A becoming all 0s and Row B becoming all 1s – both uniform.

Therefore, the maximum number of uniform rows we can achieve is simply the size of the largest group of rows that are all identical to each other or are complements of each other . We don't need to actually simulate flips; we just need to identify these groups.

How to group rows efficiently? We can use a hash map (dictionary) to count occurrences of each "row pattern" where we treat each row as equivalent to its complement:

• We choose a canonical representation for each row such that a row and its complement map to the same representation. For instance, we can define the canonical form as follows: if a row's first element is 0, we represent the row as-is; if a row's first element is 1, we represent the row by its bitwise complement (flip all 0s to 1s and vice versa). This way, the first bit of the canonical form is always 0 (or always 1 – either consistent choice works as long as it's consistent for all rows). Rows that are complements of each other will end up with the same canonical representation.
• We then use a hash map to count how many rows map to each canonical pattern. The answer will be the largest count in this map, because that represents the largest set of rows that are identical or complementary (all mapped to the same canonical form).

Why this works

By normalizing rows in this way, we essentially assume a particular flip strategy without actually flipping: we treat any row that starts with 1 as if we have flipped all bits in that row. This is equivalent to saying we plan to flip every column where that row has a 1 in the first position (to make that first position 0). Applying this consistently, two originally complementary rows will both normalize to the same pattern. Two identical rows will either both stay the same or both get flipped (if they start with 1) under this rule, so they too normalize to the same pattern. Thus, identical rows share a canonical form, and complementary rows share a canonical form. No other distinct rows will share a canonical form, because if two rows are neither identical nor opposites, one of them cannot be turned into the other by flipping all columns – hence their normalized patterns will differ.

Once we have these groups (by counting canonical patterns), the largest group size is the maximum uniform rows possible, because we can choose the flip strategy corresponding to that canonical pattern to make all those rows uniform. That flip strategy is essentially: if the canonical form was the row as-is, flip the columns where that pattern has 1s (to make them all 0s); if the canonical form was obtained by flipping (meaning the original row started with 1), then the flip strategy corresponds to flipping the opposite set. In either case, all rows in that group will end up either all 0s or all 1s.

Algorithm Steps (Optimized)

1. Normalize Each Row: For each row in the matrix, create a normalized pattern:

   • Check the first element of the row (or any fixed reference bit, but the first is convenient).

   • If the first element is 0, use the row as the pattern (e.g., row = [0,1,0,1] -> pattern = 0101).

   • If the first element is 1, flip all bits in the row to get the pattern (e.g., row = [1,0,1,0] -> flipped to [0,1,0,1] -> pattern = 0101). This ensures that if two rows were [0,1,0,1] and [1,0,1,0] (complements), they both produce the same pattern "0101".

2. Count Patterns: Use a hash map (dictionary) to count how many times each normalized pattern occurs.
3. Find Max Group: Scan the counts in the hash map to find the largest value. This value represents the maximum number of rows that share an identical/complement pattern group.
4. Return that maximum count. (We do not need to actually output which rows or what flips, just the number.)

Walkthrough Example (Optimized Approach)

Let's walk through the algorithm with the matrix from Example 3:

matrix = [
  [0,0,0],
  [0,0,1],
  [1,1,0]
]

We will normalize each row (using the rule "if first element is 1, flip the row; if first element is 0, leave it") and then count patterns:

Now we count the occurrences of each pattern key:

• Pattern "000" occurs 1 time (from Row 0).
• Pattern "001" occurs 2 times (from Row 1 and Row 2).

The largest count is 2 for pattern "001". This tells us the maximum uniform rows we can get is 2. Indeed, as the example showed, by flipping the first two columns we achieved 2 uniform rows. In our normalized view, pattern "001" corresponds to treating [0,0,1] as the base pattern (which was row1 unchanged and row2 flipped). The flip strategy that makes pattern "001" all zeros (for instance) will make both original Row 1 and Row 2 uniform.

Another quick verification: Rows 1 and 2 of the original matrix are complements of each other ([0,0,1] vs [1,1,0]), which is why they ended up in the same group. Row 0 ([0,0,0]) did not pair with any other, so it could at best be made uniform by itself (hence only count 1).

Complexity (Optimized)

• Time Complexity: O(m * n). We iterate through each of the m rows and perform an O(n) operation to build the normalized pattern (flipping if needed and creating a key). Inserting into the hash map and counting is O(1) average per row. Thus total time ~ m*n, which for m,n up to 300 is at most 90,000 operations, very efficient.

• Space Complexity: O(m * n) in the worst case. In the hash map we may store up to m pattern keys, each of length n (in the form of a string or tuple of length n). In the worst case (e.g., all rows different and no complements), we store m distinct keys of length n, which is O(mn) space. However, this at most would be 300300 = 90,000 characters/entries, which is fine for modern memory. In practice, the space is often less due to grouping. Additional space is used for the pattern generation (which could be done in-place to reduce overhead).

The optimized approach is efficient and will comfortably run within the problem's constraints.

Optimized Approach Implementation (Core Logic in Python)

Here is a Python function implementing the above logic. We will provide full implementations in Python and Java in the next section, including example runs.

def max_equal_rows_after_flips(matrix):
    from collections import defaultdict
    pattern_counts = defaultdict(int)
    for row in matrix:
        # Determine normalized pattern
        if row[0] == 1:
            # Flip the row for canonical pattern
            pattern = tuple(1 - x for x in row)
        else:
            # Keep the row as is
            pattern = tuple(row)
        pattern_counts[pattern] += 1
    # Find the maximum count among all patterns
    return max(pattern_counts.values())

This function creates a dictionary of pattern frequencies. Note that we use a tuple to represent the row pattern (immutable and hashable), but we could also use a string of '0'/'1'. If the first element is 1, we flip each bit (using 1 - x) to form the pattern; if first element is 0, we use the row as is. Finally, we return the largest frequency found in the dictionary, which is the answer.

Step-by-Step Walkthrough of Optimal Approach

Let's break down the optimal approach with another example and illustrate each step clearly using a table.

Consider a matrix:

matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [0, 1, 0, 0]
]

This matrix has 3 rows and 4 columns. We will go through normalization and grouping:

Step 1: Choose a Normalization Rule.
We'll use the rule: if a row's first value is 1, flip the entire row; if it's 0, leave it. This will make every normalized pattern start with 0.

Step 2: Normalize each row:

• Row0 = [0, 1, 1, 0] – First value is 0, so we do not flip. Normalized pattern = [0, 1, 1, 0] (as a string, "0110").
• Row1 = [1, 0, 0, 1] – First value is 1, so flip all bits. Flipped row becomes [0, 1, 1, 0]. Normalized pattern = [0, 1, 1, 0] ("0110").
• Row2 = [0, 1, 0, 0] – First value is 0, no flip. Normalized pattern = [0, 1, 0, 0] ("0100").

We can tabulate this:

Step 3: Group by Pattern and Count Frequencies.
From the table:

• Pattern "0110" appears for Row0 and Row1.
• Pattern "0100" appears for Row2.

Count them:

• "0110": 2 occurrences (Rows 0 and 1).
• "0100": 1 occurrence (Row 2).

Step 4: Identify the Largest Group.
The largest group is pattern "0110" with count 2. This means there are 2 rows that are identical/complement under flips.

Interpretation: Rows 0 and 1 of the original matrix turned out to have the same normalized pattern "0110". This implies Row0 and Row1 are complements of each other originally (we can verify: Row0 was [0,1,1,0], Row1 was [1,0,0,1], indeed one is the inverse of the other). So with the right flips, we can make both of those rows uniform. Row2 did not match these patterns, so at best it could be uniform by itself. Therefore, the answer for this matrix would be 2 (by choosing the flip strategy that targets the pattern of Row0/Row1).

To confirm, let's apply the flip strategy for pattern "0110": The pattern "0110" in normalized form corresponds to original Row0 (since Row0 was already "0110") and original Row1 (which was flipped to become "0110"). For normalized "0110", the flip rule was "first bit 0 means we didn't flip those rows individually", which suggests the flip set is columns where this pattern has 1 (to make them all zeros, for example). Pattern "0110" has 1s in columns 1 and 2 (0-indexed). If we flip columns 1 and 2 in the original matrix:

• Original matrix [0 1 1 0; 1 0 0 1; 0 1 0 0] (rows separated by semicolons)
• Flip col1 and col2 → New matrix: [0 0 0 0; 1 1 1 1; 0 0 1 0].
  Now Row0 = [0,0,0,0] (uniform), Row1 = [1,1,1,1] (uniform), Row2 = [0,0,1,0] (not uniform). We got 2 uniform rows, matching our computation.

This step-by-step process shows how the grouping method works on a concrete example without brute force searching. We identified the largest complement/identical group via patterns, and that directly gave us the answer.

Implementation

Below are implementations of the optimal solution in both Python and Java. Each implementation includes a simple example test to demonstrate usage.

Python Implementation