Score After Flipping Matrix

medium array greedy bit manipulation matrix

Problem

Given a 0/1 matrix where each row encodes a binary number, you may toggle any whole row or column. Maximize the sum of the row values.

Inputgrid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]

Output39

Flip rows that begin with 0, then flip each column where 0s ≥ 1s.

grid (rows separated by ';')

def matrixScore(grid):
    m, n = len(grid), len(grid[0])
    total = m * (1 << (n - 1))  # leftmost column all 1s
    for j in range(1, n):
        ones = sum(1 for i in range(m) if grid[i][j] == grid[i][0])
        ones = max(ones, m - ones)
        total += ones * (1 << (n - 1 - j))
    return total

function matrixScore(grid) {
  const m = grid.length, n = grid[0].length;
  let total = m * (1 << (n - 1));
  for (let j = 1; j < n; j++) {
    let ones = 0;
    for (let i = 0; i < m; i++) if (grid[i][j] === grid[i][0]) ones++;
    ones = Math.max(ones, m - ones);
    total += ones * (1 << (n - 1 - j));
  }
  return total;
}

class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int total = m * (1 << (n - 1));
        for (int j = 1; j < n; j++) {
            int ones = 0;
            for (int i = 0; i < m; i++) if (grid[i][j] == grid[i][0]) ones++;
            ones = Math.max(ones, m - ones);
            total += ones * (1 << (n - 1 - j));
        }
        return total;
    }
}

int matrixScore(vector<vector<int>>& grid) {
    int m = (int)grid.size(), n = (int)grid[0].size();
    int total = m * (1 << (n - 1));
    for (int j = 1; j < n; j++) {
        int ones = 0;
        for (int i = 0; i < m; i++) if (grid[i][j] == grid[i][0]) ones++;
        ones = max(ones, m - ones);
        total += ones * (1 << (n - 1 - j));
    }
    return total;
}

Explanation

Each row is a binary number, and we can flip any whole row or column. To maximize the sum, we use a greedy insight: the leftmost column is worth the most, so it should be all ones.

A bit in column j (counting from the left, 0-indexed) is worth 2^(n-1-j). The leftmost column is so valuable that we always flip any row starting with 0 so that every row begins with 1. That contributes m * (1 << (n - 1)) immediately, where m is the number of rows.

For every other column, we are free to flip it (since the leading column is already locked in by row flips). For each such column we want as many ones as possible, so we count how many entries match the row's first bit and take max(ones, m - ones) — that is the best we can do by optionally flipping the column.

Each column then adds best_ones * 2^(n-1-j) to the total. We never actually mutate the grid; we just compute the contribution column by column.

Example: with grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]], the leftmost column gives 3 * 8 = 24, and summing the best counts for the remaining columns brings the total to 39.

Time: O(m · n) Space: O(1)