You have an m x n binary matrix. A move flips an entire row or column (0 ↔ 1). Each row is interpreted as a binary number, and the score is the sum of those numbers. Return the maximum score achievable after any number of moves.

Engineering takeaway. Greedy feels risky until you notice the key property: the most significant bit dominates everything below it. Since one 1 in the leftmost column outweighs any combination of bits to its right, you can lock that decision first and never revisit it. Real systems rely on this "dominant constraint" reasoning constantly — optimize the biggest lever, then the next.

Intuition

The leftmost column is the most significant bit of every row. 1000 is bigger than 0111 — so:

  1. For rows: if a row starts with 0, flip the whole row so it starts with 1. This is always strictly better.
  2. For columns: after step 1, each row's first bit is fixed. For any other column j, the contribution to the score is 2^(n-1-j) per 1. To maximize, we want more 1s than 0s in that column — so if a column has fewer 1s than half the rows, flip it.

Steps 1 and 2 don't interfere: row flips happen first (fixing the leading bit), and column flips after that never change column counts in a way that requires revisiting step 1.

Approach

  1. Flip every row that starts with 0 (XOR with 1).
  2. For each column, count the 1s. If fewer than ceil(m / 2), flip the column.
  3. Convert each row to a binary string → decimal, and sum.
function matrixScore(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
 
  // Rows: guarantee the leading bit is 1
  for (let i = 0; i < m; i++) {
    if (grid[i][0] === 0) {
      grid[i] = grid[i].map((cell) => cell ^ 1);
    }
  }
 
  // Columns: maximize the number of 1s
  for (let j = 0; j < n; j++) {
    let ones = 0;
    for (let i = 0; i < m; i++) {
      if (grid[i][j] === 1) ones++;
    }
    if (ones < Math.ceil(m / 2)) {
      for (let i = 0; i < m; i++) {
        grid[i][j] = grid[i][j] ^ 1;
      }
    }
  }
 
  return grid.reduce(
    (sum, row) => sum + parseInt(row.join(""), 2),
    0,
  );
}

Complexity

  • Time: O(m * n) — each cell is examined a constant number of times.
  • Space: O(m) for the rebuilt rows in the final reduce (the grid itself is O(m * n)).

The lesson

Greedy is valid when a local decision can't be undone by later decisions. The leading-bit argument makes row flips unconditionally correct, and after that each column is independent. Nail down the dominant constraint first, then the rest often solves itself — one bit at a time.