861. Score After Flipping Matrix

[mah-shamim]

Topics: Array, Greedy, Bit Manipulation, Matrix

You are given an m x n binary matrix grid.

A move consists of choosing any row or column and toggling each value in that row or column (i.e., changing all 0's to 1's, and all 1's to 0's).

Every row of the matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score after making any number of moves (including zero moves).

Example 1:

• Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
• Output: 39
• Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Example 2:

• Input: grid = [[0]]
• Output: 1

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid[i][j] is either 0 or 1.

[basharul-siddike]

We need to maximize the matrix score by flipping rows or columns. The goal is to interpret each row as a binary number and get the highest possible sum from all the rows.

Approach:

1. Initial Observation:

   • To maximize the binary number from each row, the most significant bit (leftmost bit) in each row should be 1. This means we should first flip any row that starts with a 0.
   • After ensuring all rows start with 1, we need to maximize the remaining bits of each row. This can be done by flipping columns to have as many 1s as possible, especially for higher-bit positions.

2. Steps:

   • Flip any row that doesn't start with 1 to ensure the leftmost bit of every row is 1.
   • For each column from the second position onward, check if there are more 0s than 1s. If so, flip the column to maximize the number of 1s in that column.
   • Calculate the final score by interpreting each row as a binary number.

Let's implement this solution in PHP: 861. Score After Flipping Matrix

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function matrixScore($grid) {
    $m = count($grid); // Number of rows
    $n = count($grid[0]); // Number of columns

    // Step 1: Ensure all rows start with 1 by flipping rows if necessary
    for ($i = 0; $i < $m; $i++) {
        if ($grid[$i][0] == 0) {
            // Flip the entire row
            for ($j = 0; $j < $n; $j++) {
                $grid[$i][$j] = 1 - $grid[$i][$j];
            }
        }
    }

    // Step 2: Maximize the number of 1's in each column from the second column onwards
    for ($j = 1; $j < $n; $j++) {
        $onesCount = 0;
        for ($i = 0; $i < $m; $i++) {
            if ($grid[$i][$j] == 1) {
                $onesCount++;
            }
        }
        
        // If there are more 0's than 1's in this column, flip the column
        if ($onesCount < $m / 2) {
            for ($i = 0; $i < $m; $i++) {
                $grid[$i][$j] = 1 - $grid[$i][$j];
            }
        }
    }

    // Step 3: Calculate the final score by interpreting each row as a binary number
    $score = 0;
    for ($i = 0; $i < $m; $i++) {
        $rowValue = 0;
        for ($j = 0; $j < $n; $j++) {
            $rowValue = $rowValue * 2 + $grid[$i][$j];
        }
        $score += $rowValue;
    }

    return $score;
}

// Test cases
echo matrixScore([[0,0,1,1],[1,0,1,0],[1,1,0,0]]); // Output: 39
echo "\n";
echo matrixScore([[0]]); // Output: 1
?>

Explanation:

1. Row flipping to ensure the leftmost bit is 1:

   • For each row, if the first element (most significant bit) is 0, we flip the entire row. This guarantees that all rows start with 1, which maximizes the contribution of the most significant bit.

2. Column flipping to maximize 1s:

   • For each column starting from the second column, we count how many 1s there are.
   • If there are more 0s than 1s in a column, we flip the entire column to maximize the number of 1s in that column.

3. Score calculation:

   • After flipping rows and columns, we compute the score by treating each row as a binary number. Each row is converted from binary to decimal and added to the total score.

Time Complexity:

• Row Flipping: We iterate over all rows and columns once, so this takes O(m * n).
• Column Flipping: For each column, we count the number of 1s, which takes O(m * n).
• Score Calculation: Converting rows to binary numbers takes O(m * n).

Thus, the total time complexity is O(m * n), where m is the number of rows and n is the number of columns. Given the constraints (m, n <= 20), this is efficient enough.

Example Walkthrough:

For the input:

$grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]];

• After ensuring all rows start with 1:

  [[1,1,0,0],[1,0,1,0],[1,1,0,0]]
  

• After flipping columns to maximize 1s:

  [[1,1,1,1],[1,0,1,0],[1,1,1,1]]
  

• Final score:

  • Row 1: 1111 = 15
  • Row 2: 1001 = 9
  • Row 3: 1111 = 15
  • Total score = 15 + 9 + 15 = 39

This gives the correct output of 39.

[mah-shamim]

Thanks to solve the "Score After Flipping Matrix" problem

[basharul-siddike]

Thanks