Score After Flipping Matrix

Medium
1455.

Score After Flipping Matrix

Score After Flipping Matrix is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Google interviews.

You are given an m x n binary matrix grid. A move picks one whole row or one whole column and toggles every cell in it (0 becomes 1, 1 becomes 0). You may make any number of moves.

Afterwards each row is read as a binary number, most significant bit on the left, and the score is the sum of these numbers.

Return the highest score you can reach.

Example 1

Input
grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output
39
Explanation
Flip row 0, then columns 2 and 3: rows read 1111, 1001, 1111 = 15 + 9 + 15.

Example 2

Input
grid = [[1,0,1],[0,1,1]]
Output
13

Example 3

Input
grid = [[0]]
Output
1

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 20
  • grid[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var matrixScore = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Score After Flipping Matrix — Solution in Python, Java & C++

Score After Flipping Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Score After Flipping Matrix is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Google interviews.

Problem statement

You are given an m x n binary matrix grid. A move picks one whole row or one whole column and toggles every cell in it (0 becomes 1, 1 becomes 0). You may make any number of moves.

Afterwards each row is read as a binary number, most significant bit on the left, and the score is the sum of these numbers.

Return the highest score you can reach.

Example 1

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: Flip row 0, then columns 2 and 3: rows read 1111, 1001, 1111 = 15 + 9 + 15.

Example 2

Input: grid = [[1,0,1],[0,1,1]]
Output: 13

Example 3

Input: grid = [[0]]
Output: 1

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 20
  • grid[i][j] is 0 or 1

Hints for Score After Flipping Matrix

  1. Hint 1

    The leftmost bit of a row is worth more than all the other bits of that row combined.

  2. Hint 2

    So every row should start with a 1 — flip the rows that start with 0.

  3. Hint 3

    After that, columns are independent: flip a column whenever it has more zeros than ones.

How to solve Score After Flipping Matrix

The leading bit dominates: 2^(n-1) exceeds the sum of all lower bits. So first make every row start with 1 using row flips, then choose each remaining column's flip by majority.

Approach

  1. Conceptually flip every row whose first cell is 0. A cell (i, j) then holds 1 exactly when grid[i][j] == grid[i][0].
  2. For each column j, count ones under that rule and take max(ones, m - ones) — flipping the column if zeros are the majority.
  3. Add max(ones, m - ones) · 2^(n - 1 - j) to the score.

Why it works

Any row with a leading 0 loses 2^(n-1), more than it can gain from the rest of its bits, so an optimal answer has every leading bit 1 (column 0 is never flipped afterwards). Once the row flips are fixed, column flips do not interact: each column contributes its count of ones times its place value, and flipping it swaps ones for m - ones.

Complexity

  • Time — O(m · n)
  • Space — O(1)

Pitfalls

  • Do not flip column 0 after fixing the rows — it is already all ones.
  • Count a cell as 1 after the row flip, i.e. compare it to the row's first cell rather than reading the raw value.
  • With n <= 20 the score stays below 20 · 2^20, so 32-bit integers suffice.

Reference solution

Python

from typing import List

def matrixScore(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    total = 0
    for j in range(n):
        ones = sum(1 for i in range(m) if grid[i][j] == grid[i][0])
        total += max(ones, m - ones) << (n - 1 - j)
    return total

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms