Domain 2MediumMEDIUM

Score After Flipping Matrix

LeetCode problem 861: Score After Flipping Matrix (medium).

Domain: medium•Updated: 2026-09-02
#Greedy

Problem Breakdown

We are given a binary matrix A of size m×nm \times n. We can perform any number of operations where an operation consists of flipping all bits (0↔1) in either a specific row or column. The goal is to maximize the total score, which is defined as the sum of each row interpreted as a decimal integer based on its binary representation.

Inputs:

  • A: A list of lists containing integers 0 and 1.
  • Dimensions: mm rows (A.lengthA.length), nn columns (A[0].lengthA[0].length). Both between 1 and 20.

Outputs:

  • An integer representing the maximum possible score.

Implicit Constraints & Edge Cases:

  • MSB Dominance: The leftmost column (index 0) has a weight of 2n−12^{n-1}. This is greater than the sum of all lower bit weights combined (∑i=0n−22i=2n−2<2n−1\sum_{i=0}^{n-2} 2^i = 2^n - 2 < 2^{n-1}). Therefore, maximizing bits in column 0 is strictly more important.
  • Single Row/Column: If m=1m=1 or n=1n=1, the logic still holds (e.g., if n=1n=1, only one bit exists per row; we just maximize that single bit for every row).
  • Input Modification: The problem allows modifying A in place to save space, which is acceptable unless specified otherwise.

Intuition

Initially, a brute-force approach might suggest trying all combinations of flips (2m+n2^{m+n} possibilities), but this is computationally impossible given the constraints and logic depth (exponential time).

Key Insight: The problem can be solved greedily because operations on rows are independent regarding their most significant bit.

  1. Row Optimization: To maximize a binary number, we want its Most Significant Bit (MSB) to be 1. Since column 0 contributes 2n−12^{n-1} per row, every single row should start with a 1 at index 0. If any row starts with 0, the optimal move is to flip that specific row immediately. This decision does not negatively impact other rows’ MSBs because we can always choose to flip just one row without affecting others.
  2. Column Optimization: Once all rows start with a 1 (MSB fixed), we look at remaining columns j>0j > 0. For any column, the bits are independent of each other’s values in terms of flipping constraints (we can still flip this specific column). To maximize the sum for column jj, if there are more 0s than 1s currently present after row flips, we should conceptually flip that entire column. If there are fewer 0s, we leave it as is.
  3. Calculation: Instead of physically flipping columns in a second pass (which adds complexity), we can simply count the number of 1s and take max⁡(count(1),m−count(1))\max(\text{count}(1), \text{m} - \text{count}(1)) for each column’s contribution to the total score, weighted by its bit position.

Approach

  1. Fix MSBs: Iterate through every row ii. If A[i][0] is 0, toggle all elements in that row (conceptually or physically). This ensures every row contributes a positive value for the highest weight column (2n−12^{n-1}).
    • In Python, we can update the list reference directly: A[i] = [x ^ 1 for x in A[i]].
  2. Calculate Score: Iterate through each column jj from 00 to n−1n-1.
    • Count how many rows have a 1 at index jj (let this be ones).
    • The number of zeros is m - ones.
    • We want the maximum contribution, so we take max⁡(ones,zeros)\max(\text{ones}, \text{zeros}).
  3. Accumulate: Add the weighted value to a running total: count * (1 << (n - 1 - j)).

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n). We iterate through each row once for step 1, and then visit every cell again in column loops. Since we process the matrix linearly, this is optimal as we must inspect at least one bit per cell to determine its state relative to flips.
  • Space Complexity: O(1)O(1) auxiliary space (excluding input storage). We modify A in place or use constant extra variables for counters and sums.

Solution

class Solution:
    def matrixScore(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        m = len(A)
        n = len(A[0])
        
        # Step 1: Ensure every row starts with a '1' (MSB optimization).
        # If the first element is 0, flip the entire row.
        for i in range(m):
            if A[i][0] == 0:
                # Toggle all bits in this row using XOR or list comprehension
                A[i] = [x ^ 1 for x in A[i]]
        
        score = 0
        
        # Step 2: Calculate contribution of each column.
        # For any column, we can choose to flip it if zeros > ones.
        # Contribution is max(ones_count, m - ones_count) * bit_weight.
        for j in range(n):
            # Count current '1's in this column across all rows
            ones = sum(row[j] for row in A)
            
            # Determine how many effective '1's we can have (either keep or flip col)
            count_ones_for_score = max(ones, m - ones)
            
            # Add weighted value to total score. 
            # Bit weight decreases from left to right: 2^(n-1-j).
            score += count_ones_for_score * (1 << (n - 1 - j))
        
        return score

Edge Cases Handled

  • Single Row/Column (m=1m=1 or n=1n=1): The loops handle ranges correctly. If n=1n=1, the bit weight is (1≪0)=1(1 \ll 0) = 1. Logic holds as we maximize that single bit per row (which becomes max(ones, zeros)).
  • All Zeros Initially: Step 1 flips every row to start with 1. Step 2 counts remaining bits and optimizes columns. Correctly maximizes score.
  • Already Optimal Matrix: If MSBs are already 1 and column distributions favor 1s, the code simply sums them up without unnecessary toggles (though logic remains valid).