Leetcode — 861. Score After Flipping Matrix

The link to the problem: https://leetcode.com/problems/score-after-flipping-matrix/

We have a two-dimensional matrix A where each value is 0 or 1.
A move consists of choosing any row or column and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

Conditions:

  1. 1 <= A.length <= 20
  2. 1 <= A[0].length <= 20
  3. A[i][j] is 0 or 1.

Thoughts:

The problem looks hard and it’s kind of clueless to decide which row or which column we should flip. It’s fine, don’t panic! Let’s carefully read our goal —return the highest possible score. Since the final score is the aggregation of the scores in each row, it means that if we want to get the highest score, the score in each row must be as high as possible first.

Since we know that we are going to form a binary number row by row, our first priority is to make the first column of each row 1. Even if the original row is [0,1,1,1…1], the binary number it represents will still less than the row like [1,0,0,….0].

Hence, we will flip all the rows that don’t start with 1. After that, then we can start to add up all the numbers represented by each row. But wait, are we sure that the current sum will be our highest score?

For example, we have a grid that looks like

After flipping specific rows —

You can see that we only flip the last row since we know that we can’t get a bigger number if we flip the first 2 rows.

If we just look at the above matrix, it is obvious that we should flip some columns to make the final score higher. Hence, our second task is to flip the columns if the 0s are too many in that column. or if we say it more accurately, we will flip the columns in which 0 is the majority.

Based on the above idea, we can come up with the code below —

The above code runs O(m*n+n) time complexity (when we have m rows and n columns). It runs 1ms and beats 37% of submitted codes on Leetcode.

Is it possible that we can improve our current code?

Code Logic:

The reason why we have an extra O(n) time in the above code is that we cannot decide should we flip column j before we traverse all the elements on the column. Since we always traverse each column on each row, we can only know which number (0 or 1) is the majority on a certain column after we traverse all the rows.

However, if we traverse col by col, then we can immediately know whether we need to flip the column before we switch to the next column. We don’t actually need to first traverse the row first since we know the rule of whether flip the row or not depends on the first element in each row.

⚠️The reason why we traverse from the last column to the first column is that we always need to decide whether to flip the current row i depends on the value of A[i][0]. If we traverse from the first column, we will flip the first element of the row and we will need an extra boolean array to record whether we need to flip row i.

Below is the 0ms code that beats 100% —

Click here to view all the stories posted on this blog: https://anj910.medium.com/bookmark-c95e4c52cf44