Flip Columns For Maximum Number of Equal Rows solution and explanation
Google
9 more videos on this problem
Flip Columns For Maximum Number of Equal Rows - Leetcode 1072 - PythonNeetCodeIO · 11:58 · 12K views
Flip Columns For Maximum Number of Equal Rows | 2 Approaches | Leetcode 1072 | codestorywithMIKcodestorywithMIK · 30:05 · 8K views
Flip Columns For Maximum Number of Equal Rows | Leetcode 1072Techdose · 16:45 · 2K views
1072. Flip Columns For Maximum Number of Equal Rows | HashMap | StringsAryan Mittal · 15:38 · 2K views
1072. Flip Columns For Maximum Number of Equal Rows - Daily Leetcode (Day 24)yeetcode · 8:04 · 1K views
1072. Flip Columns For Maximum Number of Equal Rows | Leetcode Daily (POTD) 22 Nov 2024 | JavaAlgorithmHQ · 14:02 · 1K views
Daily Leetcode #1697: Nov 22, 2024 - 1072. Flip Columns For Maximum Number of Equal RowsProgramming Live with Larry · 11:05 · 402 views
LeetCode 1072 Flip Columns For Maximum Number of Equal Rows | Matrix | HashMapCode Harmony · 16:24 · 375 views
Flip Columns For Maximum Number of Equal Rows | Leetcode 1072 | 2 approaches| Java |Developer CoderDeveloper Coder · 26:17 · 77 views
Flip Columns For Maximum Number of Equal Rows - Leetcode 1072 - JavaCode Wizard · 19:54 · 35 views
The 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.
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.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]is either0or1.
Approach overview
Problem Overview: You are given a binary matrix. You can flip any column (change 0 → 1 and 1 → 0 for that column). The goal is to maximize the number of rows that become identical after any number of column flips.
The key observation: two rows can become equal if one row is exactly the same as the other, or if it is the complete inverse of the other. Flipping columns globally affects every row, so rows that share the same relative pattern will align after the same column operations.
Approach 1: Row Pattern Matching using HashMap (Time: O(m*n), Space: O(m*n))
Iterate through each row and convert it into a canonical pattern. If the first element of a row is 1, flip the entire logical representation of the row while building the pattern. This normalizes rows and their inverses into the same representation. Store the normalized pattern as a string or tuple in a hash map and count its frequency. Rows that map to the same pattern can all become identical after flipping the same set of columns. The maximum frequency in the hash map is the answer.
This works because column flips affect every row equally. Normalizing rows relative to the first element groups rows that differ only by a global column flip configuration. Hash lookups provide constant-time aggregation of identical patterns.
Approach 2: Row Pattern Counting with Initial Flip Consideration (Time: O(m*n), Space: O(m*n))
Another way to think about the same idea is to explicitly consider both the original row and its inverted form. For each row, build two patterns: the row itself and the row with all bits flipped. Insert both patterns into a frequency map and count how many rows can match either configuration. Rows that are complements of each other become identical once the correct columns are flipped.
This method is conceptually straightforward and highlights the symmetry between rows and their complements. However, it performs slightly more work per row because both patterns are generated.
The solution relies heavily on pattern grouping using a hash table. The matrix traversal is a simple nested loop over rows and columns using basic array operations, and the data structure being processed is a binary matrix.
Recommended for interviews: The row normalization hash map approach is what most interviewers expect. It demonstrates that you noticed the core invariant: rows and their complements behave the same under column flips. A brute-force simulation of flips would explode combinatorially, while the hash-based pattern grouping keeps the complexity linear in the size of the matrix.
Approach 1: Approach 1: Row Pattern Matching using HashMap
By considering identical or opposite binary patterns within rows, the task reduces to finding the maximum similar pattern. If row 'A' can be made equal to row 'B', they must have the same or opposite pattern for all columns.
from collections import defaultdict
def maxEqualRowsAfterFlips(matrix):
pattern_count = defaultdict(int)
for row in matrix:
pattern = tuple(val == row[0] for val in row)
pattern_count[pattern] += 1
return max(pattern_count.values())import java.util.HashMap;
public class MaxEqualRows {
public int maxEqualRowsAfterFlips(int[][] matrix) {
HashMap<String, Integer> patternCount = new HashMap<>();
for (int[] row : matrix) {
StringBuilder sb = new StringBuilder();
for (int val : row) {
sb.append(val == row[0] ? '0' : '1');
}
String pattern = sb.toString();
patternCount.put(pattern, patternCount.getOrDefault(pattern, 0) + 1);
}
int maxEqualRows = 0;
for (int count : patternCount.values()) {
maxEqualRows = Math.max(maxEqualRows, count);
}
return maxEqualRows;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string, int> patternCount;
for (auto& row : matrix) {
string base(row.size(), '0');
for (int j = 0; j < row.size(); ++j) {
base[j] = row[j] == row[0] ? '0' : '1';
}
patternCount[base]++;
}
int maxEqualRows = 0;
for (auto& [pattern, count] : patternCount) {
maxEqualRows = max(maxEqualRows, count);
}
return maxEqualRows;
}function maxEqualRowsAfterFlips(matrix) {
const patternCount = new Map();
for (const row of matrix) {
const base = row.map(val => val === row[0] ? '0' : '1').join('');
patternCount.set(base, (patternCount.get(base) || 0) + 1);
}
return Math.max(...patternCount.values());
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int transform(int* row, int* pattern, int n) {
int key[n];
for (int i = 0; i < n; ++i) {
key[i] = (row[i] == pattern[i]) ? 0 : 1;
}
return key;
}
int maxEqualRowsAfterFlips(int** matrix, int matrixSize, int* matrixColSize) {
int n = *matrixColSize;
int maxEqualRows = 0;
for (int i = 0; i < matrixSize; ++i) {
int* currPattern = matrix[i];
int count = 0;
for (int j = 0; j < matrixSize; ++j) {
int match = 1;
for (int k = 0; k < n; ++k) {
if ((matrix[j][k] == currPattern[k]) != (matrix[0][k] == currPattern[k])) {
match = 0;
break;
}
}
if (match) count++;
}
if (count > maxEqualRows) {
maxEqualRows = count;
}
}
return maxEqualRows;
}using System;
using System.Collections.Generic;
using System.Linq;
public class MaxEqualRows {
public int MaxEqualRowsAfterFlips(int[][] matrix) {
var patternCount = new Dictionary<string, int>();
foreach (var row in matrix) {
string pattern = string.Concat(row.Select(val => val == row[0] ? '0' : '1'));
if (!patternCount.ContainsKey(pattern))
patternCount[pattern] = 0;
patternCount[pattern]++;
}
return patternCount.Values.Max();
}
}The rows are transformed into boolean patterns and stored in a dictionary to track frequency. We return the maximum frequency pattern.
Time Complexity: O(m * n), Space Complexity: O(m * n) for representing patterns.
Approach 2: Approach 2: Row Pattern Counting with Initial Flip Consideration
This alternative method evaluates each row by considering both its native and entirely flipped transformations, tallying frequency counts using these dual patterns in order to discover the maximal frequency count of equivalent rows.
from collections import defaultdict
def maxEqualRowsAfterFlips(matrix):
pattern_count = defaultdict(int)
for row in matrix:
original = ''.join(str(x) for x in row)
flipped = ''.join('1' if x == 0 else '0' for x in row)
pattern_count[original] += 1
pattern_count[flipped] += 1
return max(pattern_count.values())import java.util.HashMap;
public class MatrixEquivalence {
public int maxEqualRowsAfterFlips(int[][] matrix) {
HashMap<String, Integer> patternCount = new HashMap<>();
for (int[] row : matrix) {
StringBuilder originalSb = new StringBuilder();
StringBuilder flippedSb = new StringBuilder();
for (int value : row) {
originalSb.append(value);
flippedSb.append(1 - value);
}
String originalPattern = originalSb.toString();
String flippedPattern = flippedSb.toString();
patternCount.put(originalPattern, patternCount.getOrDefault(originalPattern, 0) + 1);
patternCount.put(flippedPattern, patternCount.getOrDefault(flippedPattern, 0) + 1);
}
int maxEqualRows = 0;
for (int count : patternCount.values()) {
maxEqualRows = Math.max(maxEqualRows, count);
}
return maxEqualRows;
}
}#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string, int> patternCount;
for (auto& row : matrix) {
string original(row.size(), '0');
for (int j = 0; j < row.size(); j++)
original[j] = (row[j] == 1) ? '1' : '0';
patternCount[original]++;
string rev(row.size(), '0');
for (int j = 0; j < row.size(); j++)
rev[j] = (row[j] == 0) ? '1' : '0';
patternCount[rev]++;
}
int maxEqualRows = 0;
for (const auto& p : patternCount) {
maxEqualRows = max(maxEqualRows, p.second);
}
return maxEqualRows;
}function maxEqualRowsAfterFlips(matrix) {
const patternCount = new Map();
for (let row of matrix) {
const original = row.join('');
const flipped = row.map(x => 1 - x).join('');
patternCount.set(original, (patternCount.get(original) || 0) + 1);
patternCount.set(flipped, (patternCount.get(flipped) || 0) + 1);
}
return Math.max(...patternCount.values());
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 90000 // derived from 300 rows * 300 columns
int hashFunction(const char *key) {
unsigned long hash = 5381;
int c;
while ((c = *key++)) {
hash = ((hash << 5) + hash) + c;
}
return hash % MAX;
}
int maxEqualRowsAfterFlips(int** matrix, int matrixSize, int* matrixColSize) {
int n = *matrixColSize;
int hashCount[MAX] = {0};
for (int i = 0; i < matrixSize; i++) {
char original[n + 1];
char flipped[n + 1];
original[n] = flipped[n] = '\0';
for (int j = 0; j < n; j++) {
original[j] = matrix[i][j] + '0';
flipped[j] = 1 - matrix[i][j] + '0';
}
int origHash = hashFunction(original);
int flipHash = hashFunction(flipped);
hashCount[origHash]++;
hashCount[flipHash]++;
}
int maxEqualRows = 0;
for (int i = 0; i < MAX; i++) {
if (hashCount[i] > maxEqualRows) {
maxEqualRows = hashCount[i];
}
}
return maxEqualRows;
}using System;
using System.Collections.Generic;
using System.Linq;
public class MatrixEquivalence {
public int MaxEqualRowsAfterFlips(int[][] matrix) {
var patternCount = new Dictionary<string, int>();
foreach (var row in matrix) {
string original = string.Concat(row.Select(val => val.ToString()));
string flipped = string.Concat(row.Select(val => (1 - val).ToString()));
if (!patternCount.ContainsKey(original))
patternCount[original] = 0;
if (!patternCount.ContainsKey(flipped))
patternCount[flipped] = 0;
patternCount[original]++;
patternCount[flipped]++;
}
return patternCount.Values.Max();
}
}For each row, two manifestations are considered - native and alternative - serving through simple transformation and comparability. This pattern focus allows Python's effective storage and retrieval ability in dictionary mode to be used.
Time Complexity: O(m * n), Space Complexity: Modularized storage performance given by initialized aggregates.
Approach 3: Default Approach
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;
}func maxEqualRowsAfterFlips(matrix [][]int) (ans int) {
cnt := map[string]int{}
for _, row := range matrix {
s := []byte{}
for _, x := range row {
if row[0] == 1 {
x ^= 1
}
s = append(s, byte(x)+'0')
}
t := string(s)
cnt[t]++
ans = max(ans, cnt[t])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Row Pattern Matching using HashMap | Time Complexity: O(m * n), Space Complexity: O(m * n) for representing patterns. |
| Approach 2: Row Pattern Counting with Initial Flip Consideration | Time Complexity: O(m * n), Space Complexity: Modularized storage performance given by initialized aggregates. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Row Pattern Matching using HashMap | O(m*n) | O(m*n) | Best general solution. Normalizes rows to group identical flip outcomes efficiently. |
| Row Pattern Counting with Initial Flip Consideration | O(m*n) | O(m*n) | Useful when reasoning directly about row complements instead of normalization. |
Frequently asked questions
Is Flip Columns For Maximum Number of Equal Rows easy or hard?
Flip Columns For Maximum Number of Equal Rows is classified as a Medium difficulty problem. The challenge is identifying that rows and their complements behave the same after column flips. Once this insight is recognized, the implementation using hashing is straightforward.
Flip Columns For Maximum Number of Equal Rows Python/Java solution
Python and Java solutions typically build a normalized row pattern and store it in a dictionary or HashMap. Each row is converted into a string or tuple representation after adjusting for the first element. The maximum frequency of any stored pattern is returned as the result.
How to solve Flip Columns For Maximum Number of Equal Rows in O(n)?
The problem can be solved in linear time relative to the matrix size using row pattern hashing. Normalize each row so that rows and their inverses share the same representation, then store the pattern in a hash map. The highest frequency pattern represents the maximum number of rows that can become identical after column flips.
What is the best approach for Flip Columns For Maximum Number of Equal Rows?
The most effective approach is row pattern normalization using a HashMap. Convert each row into a canonical pattern by XORing values relative to the first element so rows and their complements become identical patterns. Counting these patterns in a hash map gives the maximum number of rows that can be made equal. The algorithm runs in O(m*n) time with O(m*n) space.
Is Flip Columns For Maximum Number of Equal Rows asked at Google/Amazon/Meta?
This problem follows common interview patterns used by companies like Google, Amazon, and Meta. It tests recognition of invariants, hashing techniques, and matrix processing. Variations of pattern grouping and row normalization frequently appear in coding interviews.
What data structure is used in Flip Columns For Maximum Number of Equal Rows?
The main data structure is a hash table (HashMap or dictionary). It stores normalized row patterns as keys and counts how many rows share the same pattern. Arrays or matrices are used for the input structure, while the hash table enables constant-time frequency updates.
What is the time complexity of Flip Columns For Maximum Number of Equal Rows?
The optimal solution runs in O(m*n) time, where m is the number of rows and n is the number of columns. Each row is scanned once to build a normalized pattern, and the pattern is stored in a hash map for frequency counting. Space complexity is also O(m*n) because patterns may be stored for each row.