Flip Columns For Maximum Number of Equal Rows

Flip Columns For Maximum Number of Equal Rows - Problem

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.

A row has all values equal if all cells in that row are either 0 or 1.

Input & Output

Example 1 — Basic Case

$ Input: matrix = [[0,1],[1,1]]

› Output: 1

💡 Note: We can flip column 0 to make row 1 become [1,1] (uniform), or flip column 1 to make row 1 become [0,0] (uniform). Either way, maximum 1 row can be uniform.

Example 2 — Multiple Uniform Rows

$ Input: matrix = [[0,1],[1,0]]

› Output: 2

💡 Note: Flipping column 0 makes both rows uniform: [1,1] and [0,0]. Both patterns [0,1] and [1,0] are complements, so they can both become uniform with the same flip.

Example 3 — Already Uniform

$ Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]

› Output: 2

💡 Note: Row 1 is already uniform. Flipping columns 0 and 2 makes rows 2 and 3 become [1,1,1] and [0,0,1]. We can make at most 2 rows uniform.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with rows that may have mixed 0s and 1s

Column Flips

Choose columns to flip (0→1, 1→0) to maximize uniform rows

Count Uniform

Count rows that become all 0s or all 1s

Key Takeaway

🎯 Key Insight: Rows with complementary bit patterns can both become uniform with the same column flips

Asked in

G Google 8 a Amazon 5

The key insight is that rows with complementary patterns (like [0,1,0] and [1,0,1]) can both be made uniform with the same column flips. The optimal approach uses pattern frequency counting with O(m×n) time and O(m×n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Pattern Frequency Counting	O(m × n)	O(m × n)	Group rows by pattern and count complementary patterns together
Brute Force - Try All Column Combinations	O(m × n × 2ⁿ)	O(1)	Try all possible combinations of column flips and count uniform rows

Hash Map - Pattern Frequency Counting — Algorithm Steps

Step 1: For each row, create a canonical pattern representation
Step 2: Count frequency of each unique pattern using a hash map
Step 3: For each pattern, also count its complement (flip all bits)
Step 4: The answer is the maximum frequency among all patterns

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Patterns

Each row represents a unique pattern

Find Complements

For each pattern, consider its bitwise complement

Count Groups

Count frequency of each canonical pattern

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PATTERNS 1000

typedef struct {
    char pattern[100];
    int count;
} PatternCount;

int solution(int** matrix, int m, int n) {
    PatternCount patterns[MAX_PATTERNS];
    int numPatterns = 0;
    
    for (int i = 0; i < m; i++) {
        // Create pattern and complement strings
        char pattern[100] = "", complement[100] = "";
        
        for (int j = 0; j < n; j++) {
            char temp[10];
            sprintf(temp, "%d,", matrix[i][j]);
            strcat(pattern, temp);
            sprintf(temp, "%d,", 1 - matrix[i][j]);
            strcat(complement, temp);
        }
        
        // Use lexicographically smaller as canonical
        char* canonical = (strcmp(pattern, complement) < 0) ? pattern : complement;
        
        // Find existing pattern or add new one
        int found = 0;
        for (int k = 0; k < numPatterns; k++) {
            if (strcmp(patterns[k].pattern, canonical) == 0) {
                patterns[k].count++;
                found = 1;
                break;
            }
        }
        
        if (!found) {
            strcpy(patterns[numPatterns].pattern, canonical);
            patterns[numPatterns].count = 1;
            numPatterns++;
        }
    }
    
    // Find maximum count
    int maxCount = 0;
    for (int i = 0; i < numPatterns; i++) {
        if (patterns[i].count > maxCount) {
            maxCount = patterns[i].count;
        }
    }
    
    return maxCount;
}

int main() {
    // Simple test case
    int matrix[10][10];
    int m = 2, n = 2;
    matrix[0][0] = 0; matrix[0][1] = 1;
    matrix[1][0] = 1; matrix[1][1] = 1;
    
    int* rows[10];
    for (int i = 0; i < m; i++) {
        rows[i] = matrix[i];
    }
    
    printf("%d\n", solution(rows, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Single pass through m rows, each with n columns to create pattern

✓ Linear Growth

Space Complexity

O(m × n)

Hash map stores up to m patterns, each of length n

⚡ Linearithmic Space

26.7K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Pattern Frequency Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler