Skip to main content
Talentd

Flip Columns For Maximum Number of Equal Rows - Solution & Explanation

MediumArrayHash TableMatrix12 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is either 0 or 1.

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.

Transform each row into a consistent pattern using a reference row and check for identical transformations. The transformation involves flipping columns only when required to match the pattern.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the transformation key.

Try this approach in the editor →

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.

This approach introduces a hashing mechanism to efficiently count the occurrences of different row patterns. Two interpretations, original and flipped, are hashed for each row, then comparison pairs are reduced via a single pass lookup.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), Space Complexity: Usage is reduced because of the hash bucket with a distant hash-field.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Row Pattern Matching using HashMap

Time Complexity: O(m * m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the transformation key.

Approach 2: Row Pattern Counting with Initial Flip Consideration

Time Complexity: O(m * n), Space Complexity: Usage is reduced because of the hash bucket with a distant hash-field.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Row Pattern Matching using HashMapO(m*n)O(m*n)Best general solution. Normalizes rows to group identical flip outcomes efficiently.
Row Pattern Counting with Initial Flip ConsiderationO(m*n)O(m*n)Useful when reasoning directly about row complements instead of normalization.

Video Solution

Flip Columns For Maximum Number of Equal Rows - Leetcode 1072 - Python • NeetCodeIO • 12,579 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Flip Columns For Maximum Number of Equal Rows with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays