Given a binary matrix, we can flip one column or one row, the goal is to flip zero or more times such that the sum of the number represented by the rows are maximized.

Intuition

The leading 1s are always important than the trailing 1s. So we make sure that 1 appears before 0s.

Approach

The challenge is to determine when to flip the rows and flip the columns. From the intuition, we know that:

a row is flipped only if its first bit is 0, after flipping, the number becomes larger and cannot be flipped again.
a column is flipped only if the number of 1s are smaller than 0s.

So we flip the rows first and the columns second.

Complexity

Time complexity: iterate matrix twice. $$ O(mn) $$
Space complexity: no extra space needed. $$ O(1) $$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                // flip row
                for (int j = 0; j < n; ++j) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }

        // check column by column
        for (int j = 1; j < n; ++j) {
            int count = 0;
            for (int i = 0; i < m; ++i) {
                count += grid[i][j];
            }
            if (count < (m + 1) / 2) {
                // flip column
                for (int k = 0; k < m; ++k) {
                    grid[k][j] = 1 - grid[k][j];
                }
            }
        }

        int result = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0)    continue;
                result += (1 << (n - j - 1));
            }

        }

        return result;
    }
};

References

Leetcode

861. Score After Flipping Matrix

Flip column or row such that the sum of the rows is maximized.

Intuition

Approach

Complexity

Code

References