Problem Description

You are given an m x n binary matrix grid. You can perform two types of operations any number of times:

• Flip any row (turn every 0 into 1 and every 1 into 0 in that row)
• Flip any column (turn every 0 into 1 and every 1 into 0 in that column)

After performing any number of these operations, the score of the matrix is calculated by interpreting each row as a binary number and summing them all up. For example, the row [1,0,1] is treated as binary 101, which is 5 in decimal.

Your task is to return the highest possible score you can achieve after performing any number of flips.

Constraints:

• 1 ≤ m, n ≤ 20
• grid[i][j] is 0 or 1

Thought Process

At first glance, it seems we could try all possible combinations of row and column flips to maximize the sum. However, with up to 20 rows and 20 columns, this brute-force approach would be far too slow, as there are 2^(m+n) possible flip combinations.

To optimize, we need to recognize patterns that maximize the binary value of each row. Since the leftmost bit in binary contributes the most to the number's value, we should prioritize making the first column all 1s. Once the first column is set, we can consider each subsequent column and decide if flipping it increases the total score.

The key insight is: For each row, we can always flip it so its first element is 1. Then, for each column, we can flip it if doing so increases the count of 1s in that column.

Solution Approach

• Step 1: For each row, check if the first element is 0. If so, flip the entire row. This ensures the first column is all 1s, maximizing the highest binary digit in every row.
• Step 2: For each column (except the first), count how many 1s there are. If the number of 0s is greater than 1s, flip the column. This maximizes the number of 1s in each column, maximizing the total score.
• Step 3: After all flips, interpret each row as a binary number and sum them up for the final score.

This approach ensures that every bit position in every row is maximized, starting from the most significant bit (leftmost column) to the least significant.

Example Walkthrough

Input:
grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]

1. Step 1: Flip rows so first column is all 1s
   Row 0: [0,0,1,1] → flip → [1,1,0,0]
   Row 1: [1,0,1,0] (already 1, no need to flip)
   Row 2: [1,1,0,0] (already 1, no need to flip)
   Matrix now:
   [1,1,0,0]
   [1,0,1,0]
   [1,1,0,0]
2. Step 2: For each column (except first), flip if more 0s than 1s
   Col 1: 1,0,1 → 2 ones, 1 zero (no flip)
   Col 2: 0,1,0 → 1 one, 2 zeros (flip)
   Col 3: 0,0,0 → all zeros (flip)
   After flipping col 2: becomes 1,0,1
   After flipping col 3: becomes 1,1,1
   Matrix now:
   [1,1,1,1]
   [1,0,0,1]
   [1,1,1,1]
3. Step 3: Calculate score
   [1,1,1,1] = 15
   [1,0,0,1] = 9
   [1,1,1,1] = 15
   Total = 15 + 9 + 15 = 39

Time and Space Complexity

• Brute-force Approach:
  Trying all possible combinations of row and column flips gives O(2^{m+n} \cdot m \cdot n) time, which is infeasible for large m and n.
• Optimized Approach:
  - Flipping rows: O(m \cdot n)
  - Checking and flipping columns: O(n \cdot m)
  - Calculating score: O(m \cdot n)
  Total: O(m \cdot n)
  Space complexity is O(1) if we modify in place, or O(m \cdot n) if we use a copy.

Summary

The optimal strategy for maximizing the score after flipping a binary matrix is to:

• Ensure the first column is all 1s by flipping rows as needed
• For each other column, flip it if doing so increases the number of 1s
• Sum the binary values of the resulting rows for the final score

Code Implementation

class Solution:
    def matrixScore(self, grid):
        m, n = len(grid), len(grid[0])
        # Step 1: Flip rows so first column is all 1s
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] ^= 1
        # Step 2: For each column, flip if more 0s than 1s
        for j in range(1, n):
            ones = sum(grid[i][j] for i in range(m))
            if ones < m - ones:
                for i in range(m):
                    grid[i][j] ^= 1
        # Step 3: Calculate total score
        score = 0
        for row in grid:
            num = 0
            for bit in row:
                num = (num << 1) | bit
            score += num
        return score
      

class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // Step 1: Flip rows so first column is all 1s
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        // Step 2: For each column, flip if more 0s than 1s
        for (int j = 1; j < n; ++j) {
            int ones = 0;
            for (int i = 0; i < m; ++i) {
                ones += grid[i][j];
            }
            if (ones < m - ones) {
                for (int i = 0; i < m; ++i) {
                    grid[i][j] ^= 1;
                }
            }
        }
        // Step 3: Calculate total score
        int score = 0;
        for (int i = 0; i < m; ++i) {
            int num = 0;
            for (int j = 0; j < n; ++j) {
                num = (num << 1) | grid[i][j];
            }
            score += num;
        }
        return score;
    }
};
      

class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // Step 1: Flip rows so first column is all 1s
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        // Step 2: For each column, flip if more 0s than 1s
        for (int j = 1; j < n; ++j) {
            int ones = 0;
            for (int i = 0; i < m; ++i) {
                ones += grid[i][j];
            }
            if (ones < m - ones) {
                for (int i = 0; i < m; ++i) {
                    grid[i][j] ^= 1;
                }
            }
        }
        // Step 3: Calculate total score
        int score = 0;
        for (int i = 0; i < m; ++i) {
            int num = 0;
            for (int j = 0; j < n; ++j) {
                num = (num << 1) | grid[i][j];
            }
            score += num;
        }
        return score;
    }
}
      

var matrixScore = function(grid) {
    const m = grid.length, n = grid[0].length;
    // Step 1: Flip rows so first column is all 1s
    for (let i = 0; i < m; ++i) {
        if (grid[i][0] === 0) {
            for (let j = 0; j < n; ++j) {
                grid[i][j] ^= 1;
            }
        }
    }
    // Step 2: For each column, flip if more 0s than 1s
    for (let j = 1; j < n; ++j) {
        let ones = 0;
        for (let i = 0; i < m; ++i) {
            ones += grid[i][j];
        }
        if (ones < m - ones) {
            for (let i = 0; i < m; ++i) {
                grid[i][j] ^= 1;
            }
        }
    }
    // Step 3: Calculate total score
    let score = 0;
    for (let i = 0; i < m; ++i) {
        let num = 0;
        for (let j = 0; j < n; ++j) {
            num = (num << 1) | grid[i][j];
        }
        score += num;
    }
    return score;
};