DEV Community

Cover image for 1072. Flip Columns For Maximum Number of Equal Rows
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1072. Flip Columns For Maximum Number of Equal Rows

1072. Flip Columns For Maximum Number of Equal Rows

Difficulty: Medium

Topics: Array, Hash Table, Matrix

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.

Hint:

  1. Flipping a subset of columns is like doing a bitwise XOR of some number K onto each row. We want rows X with X ^ K = all 0s or all 1s. This is the same as X = X^K ^K = (all 0s or all 1s) ^ K, so we want to count rows that have opposite bits set. For example, if K = 1, then we count rows X = (00000...001, or 1111....110).

Solution:

We can utilize a hash map to group rows that can be made identical by flipping certain columns. Rows that can be made identical have either the same pattern or a complementary pattern (bitwise negation).

Here’s the step-by-step solution:

Algorithm:

  1. For each row, calculate its pattern and complementary pattern:
    • The pattern is the row as it is.
    • The complementary pattern is the result of flipping all bits in the row.
  2. Use a hash map to count occurrences of patterns and their complements.
  3. The maximum count for any single pattern or its complement gives the result.

Let's implement this solution in PHP: 1072. Flip Columns For Maximum Number of Equal Rows

<?php
/**
 * @param Integer[][] $matrix
 * @return Integer
 */
function maxEqualRowsAfterFlips($matrix) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$matrix1 = [[0, 1], [1, 1]];
$matrix2 = [[0, 1], [1, 0]];
$matrix3 = [[0, 0, 0], [0, 0, 1], [1, 1, 0]];

echo maxEqualRowsAfterFlips($matrix1) . "\n"; // Output: 1
echo maxEqualRowsAfterFlips($matrix2) . "\n"; // Output: 2
echo maxEqualRowsAfterFlips($matrix3) . "\n"; // Output: 2
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Pattern and Complement:
    • For each row, the pattern is the concatenated row (e.g., 010).
    • The complement flips all bits of the row (e.g., 101).
  2. Hash Map: Count the occurrences of each pattern and its complement. This helps group rows that can be made identical.
  3. Max Count: Find the maximum count of a single pattern or its complement to determine how many rows can be made identical.

Complexity:

  • Time Complexity: O(m x n), where m is the number of rows and n is the number of columns.
  • Space Complexity: O(m x n), for storing patterns in the hash map.

This solution adheres to the constraints and is efficient for the problem size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Challenge Submission: SpeechCraft - AI-Powered Speech Analysis for Better Communication

SpeechCraft is an advanced real-time speech analytics platform that transforms spoken words into actionable insights. Using cutting-edge AI technology from AssemblyAI, it provides instant transcription while analyzing multiple dimensions of speech performance.

Read full post

Top comments (0)

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay