LeetCode 861 - Score After Flipping Matrix

The problem provides an m x n binary matrix, grid, where each element is either 0 or 1. You are allowed to perform a move, which consists of selecting any row or column and flipping all its values - turning every 0 into a 1 and every 1 into a 0.

leetcodemediumarraygreedybit-manipulationmatrix

LeetCode Problem 861

Difficulty: 🟡 Medium
Topics: Array, Greedy, Bit Manipulation, Matrix

Solution

Problem Understanding

The problem provides an m x n binary matrix, grid, where each element is either 0 or 1. You are allowed to perform a move, which consists of selecting any row or column and flipping all its values - turning every 0 into a 1 and every 1 into a 0. The goal is to maximize the score of the matrix. Each row in the matrix is interpreted as a binary number, with the leftmost element being the most significant bit. The total score is the sum of all row values interpreted this way.

The input guarantees that the matrix dimensions are small (1 <= m, n <= 20) and all entries are valid binary values. The constraints suggest that exhaustive approaches could be feasible in some sense, but the exponential growth of possible row/column flips (2^(m+n)) makes naive brute force inefficient.

Important edge cases include matrices with a single element, matrices where all elements are 0 or all 1, and matrices with a single row or column. The problem guarantees at least one row and one column, so no empty matrix handling is required.

In essence, we want a strategy that maximizes the binary representation of each row through clever row and column flips.

Approaches

The brute-force approach would involve exploring every combination of row and column flips. For each combination, you would compute the resulting matrix, interpret each row as a binary number, and sum the total score. This guarantees correctness because it literally tests all possibilities, but the time complexity is O(2^(m+n) * m * n) - far too large for m, n <= 20.

The optimal approach relies on two key observations. First, the leftmost bit in a row contributes the most to the row’s numeric value. Therefore, we should flip rows where the first element is 0 to ensure the highest-order bit is 1. Second, after ensuring the first column is all 1s, we can maximize the remaining bits column by column. For each column, if the number of 0s exceeds the number of 1s, we flip that column. This greedy approach works because flipping a column only affects the number of 1s and 0s, and we always choose the arrangement that maximizes each bit’s contribution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n) * m * n) O(m*n) Tries all row/column flip combinations
Optimal O(m*n) O(1) Greedy flipping based on most significant bits and column majority

Algorithm Walkthrough

  1. Ensure first column is all ones. Iterate through each row. If the first element of a row is 0, flip the entire row. This guarantees that the most significant bit of every row contributes maximally.
  2. Maximize remaining columns. For each column from the second to the last, count the number of 1s. If the number of 0s exceeds the number of 1s, flip the column to increase the total score.
  3. Compute the total score. For each row, interpret it as a binary number and sum the results.

Why it works: Flipping rows ensures the most significant bit is maximized for all rows. Flipping columns greedily ensures that every remaining bit contributes maximally without violating the already established first column. Each decision is local and independent because flipping a column does not affect the leftmost column after step 1, which guarantees optimality.

Python Solution

from typing import List

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # Step 1: Ensure first column is all ones
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] ^= 1  # Flip the row
        
        # Step 2: Maximize remaining columns
        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  # Flip the column
        
        # Step 3: Compute total score
        total_score = 0
        for row in grid:
            value = 0
            for bit in row:
                value = (value << 1) | bit
            total_score += value
        
        return total_score

This implementation starts by flipping any row with a leading 0 to ensure the most significant bit is 1. Then it iterates over each column, flipping it if it has more 0s than 1s to maximize the total sum. Finally, it calculates each row’s binary value using bit shifts, summing the total for the final score.

Go Solution

func matrixScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    
    // Step 1: Ensure first column is all ones
    for i := 0; i < m; i++ {
        if grid[i][0] == 0 {
            for j := 0; j < n; j++ {
                grid[i][j] ^= 1
            }
        }
    }
    
    // Step 2: Maximize remaining columns
    for j := 1; j < n; j++ {
        ones := 0
        for i := 0; i < m; i++ {
            ones += grid[i][j]
        }
        if ones < m - ones {
            for i := 0; i < m; i++ {
                grid[i][j] ^= 1
            }
        }
    }
    
    // Step 3: Compute total score
    total := 0
    for i := 0; i < m; i++ {
        value := 0
        for j := 0; j < n; j++ {
            value = (value << 1) | grid[i][j]
        }
        total += value
    }
    
    return total
}

The Go solution mirrors the Python logic, using integer arithmetic and bitwise XOR for flipping. Unlike Python, Go requires explicit indexing in loops, and sum must be manually computed.

Worked Examples

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

After step 1 (flip rows with leading 0):

Row Binary
[1,1,0,0] 12
[1,0,1,0] 10
[1,1,0,0] 12

Step 2 (maximize columns):

  • Column 1 already all ones.
  • Column 2: ones=2, zeros=1 → keep
  • Column 3: ones=1, zeros=2 → flip → column becomes [1,0,1]
  • Column 4: ones=1, zeros=2 → flip → column becomes [1,1,1]

Final matrix:

Row Binary
[1,1,1,1] 15
[1,0,0,1] 9
[1,1,1,1] 15

Total = 15+9+15 = 39

Example 2: grid = [[0]]

  • Flip row → [1] → score = 1

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) Step 1 flips rows (O(m_n)), step 2 counts and flips columns (O(m_n)), step 3 computes score (O(m*n))
Space O(1) In-place flipping; no extra structures used

Because m and n are ≤ 20, this algorithm is extremely efficient and scalable within the problem constraints.

Test Cases

# test cases
solution = Solution()

# Provided examples
assert solution.matrixScore([[0,0,1,1],[1,0,1,0],[1,1,0,0]]) == 39  # Example 1
assert solution.matrixScore([[0]]) == 1  # Example 2

# Single row
assert solution.matrixScore([[0,1,0]]) == 7  # Row flip yields [1,0,1] → 5

# Single column
assert solution.matrixScore([[0],[1],[0]]) == 3  # Column flip gives [1,1,1] → sum=3

# All ones
assert solution.matrixScore([[1,1],[1,1]]) == 6  # Already maximal

# All zeros
assert solution.matrixScore([[0,0],[0,0]]) == 6  # Flip all rows → [[1,1],[1,1]] → 6

# Mixed small
assert solution.matrixScore([[0,1],[1,0]]) == 6  # Flip first row → [[1,0],[1,0]] → flip column 2 → [[1,1],[1,1]] → 6
Test Why
Example 1 Validates row and column flips with mixed input
Example 2 Minimal input edge case
Single row Ensures row flipping works