Problem Description

You have a binary matrix (containing only 0s and 1s) with m rows and n columns. You can perform moves on this matrix where each move involves selecting either an entire row or an entire column and flipping all values in it (changing all 0s to 1s and all 1s to 0s).

Each row of the matrix represents a binary number. For example, if a row contains [1, 0, 1, 1], it represents the binary number 1011, which equals 11 in decimal. The score of the matrix is calculated by converting each row to its decimal value and summing all these values together.

Your goal is to find the maximum possible score you can achieve after performing any number of moves (including zero moves).

Example to clarify scoring:

• If you have a 2×3 matrix:

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

• Row 1: 101 in binary = 5 in decimal
• Row 2: 011 in binary = 3 in decimal
• Total score = 5 + 3 = 8

The solution uses a greedy strategy:

1. First, it ensures all rows start with 1 (since the leftmost bit has the highest value). If a row starts with 0, the entire row is flipped.
2. Then, for each column from left to right, it counts how many 1s are in that column. If there are fewer 1s than 0s, flipping that column would increase the score.
3. The final score is calculated by determining the contribution of each column position to the total, considering that column j contributes 2^(n-j-1) for each 1 in that position.

Intuition

To maximize the score, we need to think about how binary numbers work. The leftmost bit (most significant bit) has the highest value - it contributes 2^(n-1) to the decimal value, which is more than all other bits combined. For instance, in a 4-bit number, the leftmost bit contributes 8, while all other bits together can only contribute at most 7.

This gives us our first key insight: we want as many rows as possible to start with 1. Since we can flip entire rows, if any row starts with 0, we should flip that entire row to make it start with 1. This guarantees the maximum contribution from the most significant bit position.

After ensuring all rows start with 1, we can't flip rows anymore (as that would turn the leading 1 back to 0). Now we can only flip columns. For each remaining column position, we want to maximize the number of 1s in that column.

Here's the second insight: for each column, we want the majority value to be 1. If a column has more 0s than 1s, we should flip that column to convert the majority to 1s. If it already has more 1s, we leave it as is.

Why does this greedy approach work? Because each bit position has a fixed contribution value (2^(n-j-1) for position j), and the positions are independent after we've fixed the first column. We can make local optimal decisions for each column without affecting others.

The beauty of this solution is that we don't actually need to perform the flips explicitly for columns. We can just count how many 1s are in each column and take the maximum of that count or its complement (m - count), which represents the maximum number of 1s we could have in that column after optimal flipping.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a two-phase greedy strategy:

Phase 1: Ensure all rows start with 1

for i in range(m):
    if grid[i][0] == 0:
        for j in range(n):
            grid[i][j] ^= 1

We iterate through each row and check if the first element is 0. If it is, we flip the entire row using XOR operation (^= 1). The XOR with 1 effectively toggles the bit: 0 ^ 1 = 1 and 1 ^ 1 = 0. After this phase, all rows are guaranteed to start with 1, maximizing the contribution from the most significant bit position.

Phase 2: Optimize each column

ans = 0
for j in range(n):
    cnt = sum(grid[i][j] for i in range(m))
    ans += max(cnt, m - cnt) * (1 << (n - j - 1))

For each column j:

1. Count the number of 1s in the column: cnt = sum(grid[i][j] for i in range(m))
2. Determine the maximum number of 1s possible in this column:
   • If cnt >= m - cnt (more 1s than 0s), keep the column as is
   • If cnt < m - cnt (more 0s than 1s), we would flip the column
   • We use max(cnt, m - cnt) to get the optimal count without actually flipping
3. Calculate the contribution of this column to the total score:
   • Each 1 in column j contributes 2^(n-j-1) to its row's value
   • We use bit shifting (1 << (n - j - 1)) which is equivalent to 2^(n-j-1)
   • Multiply the optimal count by this positional value

The algorithm cleverly avoids actually performing the column flips by directly calculating what the optimal count would be. This makes the solution both elegant and efficient with O(m * n) time complexity for iterating through the matrix twice, and O(1) extra space as we modify the input matrix in place.

Example Walkthrough

Let's walk through a small example with a 3×3 matrix:

Initial matrix:
[0, 1, 1]
[1, 0, 1]
[0, 0, 0]

Phase 1: Ensure all rows start with 1

Row 0 starts with 0, so flip the entire row:

• [0, 1, 1] becomes [1, 0, 0]

Row 1 starts with 1, so leave it unchanged:

• [1, 0, 1] stays [1, 0, 1]

Row 2 starts with 0, so flip the entire row:

• [0, 0, 0] becomes [1, 1, 1]

After Phase 1:

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

Phase 2: Optimize each column

Column 0 (j=0): All three values are 1

• Count of 1s: 3
• max(3, 3-3) = max(3, 0) = 3
• Contribution: 3 × 2^(3-0-1) = 3 × 4 = 12

Column 1 (j=1): Values are [0, 0, 1]

• Count of 1s: 1
• max(1, 3-1) = max(1, 2) = 2 (flipping would give us 2 ones)
• Contribution: 2 × 2^(3-1-1) = 2 × 2 = 4

Column 2 (j=2): Values are [0, 1, 1]

• Count of 1s: 2
• max(2, 3-2) = max(2, 1) = 2 (keep as is)
• Contribution: 2 × 2^(3-2-1) = 2 × 1 = 2

Total Score: 12 + 4 + 2 = 18

To verify: If we actually flipped column 1 (which had more 0s than 1s), the final matrix would be:

[1, 1, 0]  → binary 110 = 6
[1, 1, 1]  → binary 111 = 7
[1, 0, 1]  → binary 101 = 5
Total: 6 + 7 + 5 = 18 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

• The first loop iterates through all m rows, and for each row that starts with 0, it flips all n elements in that row. In the worst case, all rows need flipping, resulting in O(m * n) operations.
• The second loop iterates through all n columns, and for each column, it sums up m elements to count the number of 1s. This results in O(n * m) operations.
• Overall time complexity: O(m * n) + O(n * m) = O(m * n)

Space Complexity: O(1)

• The algorithm modifies the input grid in-place and only uses a constant amount of extra space for variables (m, n, i, j, cnt, ans).
• No additional data structures are created that scale with the input size.
• The space complexity is constant, O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Modifying the Input Matrix Without Consideration

Issue: The solution modifies the input matrix directly during Phase 1. This can be problematic if:

• The original matrix needs to be preserved for other operations
• The interviewer expects the input to remain unchanged
• You need to debug or verify your solution against the original input

Example of the problem:

# Original matrix
grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
solution = Solution()
result = solution.matrixScore(grid)
print(grid)  # Grid has been modified! No longer the original input

Solution: Create a copy of the matrix or use a virtual flip tracking approach:

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
      
        # Track which rows need to be flipped without modifying the grid
        row_flipped = [grid[i][0] == 0 for i in range(m)]
      
        total_score = 0
        for j in range(n):
            ones_count = 0
            for i in range(m):
                # Get the actual value after considering row flip
                actual_val = grid[i][j] ^ row_flipped[i]
                ones_count += actual_val
          
            max_ones = max(ones_count, m - ones_count)
            total_score += max_ones * (1 << (n - j - 1))
      
        return total_score

Pitfall 2: Incorrect Bit Position Calculation

Issue: Confusing the bit position formula. It's easy to make off-by-one errors with (n - j - 1) when calculating 2^position.

Common mistakes:

# Wrong: Using n - j instead of n - j - 1
bit_weight = 1 << (n - j)  # This gives wrong positional values

# Wrong: Using j directly
bit_weight = 1 << j  # This reverses the bit significance

Solution: Remember that for a binary number with n bits:

• The leftmost bit (index 0) has weight 2^(n-1)
• The rightmost bit (index n-1) has weight 2^0
• For column j, the weight is 2^(n-j-1)

Test with a simple example to verify:

# For a 3-column matrix:
# Column 0: weight = 2^(3-0-1) = 2^2 = 4 ✓
# Column 1: weight = 2^(3-1-1) = 2^1 = 2 ✓
# Column 2: weight = 2^(3-2-1) = 2^0 = 1 ✓

Pitfall 3: Not Considering Edge Cases

Issue: The solution assumes the matrix is non-empty and has at least one column. This could cause errors with edge cases.

Potential problems:

# These could cause index errors or unexpected behavior:
grid = []        # Empty matrix
grid = [[]]      # Matrix with empty rows

Solution: Add input validation:

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
          
        m, n = len(grid), len(grid[0])
        # ... rest of the solution