LeetCode 861: Score After Flipping Matrix

Explanation

To solve this problem, we need to understand that toggling a row or a column will affect the score in a specific way. We should aim to maximize the score by strategically choosing which rows and columns to toggle.

The key observation is that we should try to maximize the number of leading ones in each column. To achieve this, we can iterate through each column. If the number of ones in that column is less than the number of zeros, we should toggle that column. Otherwise, we leave it as it is.

After maximizing the leading ones in each column, we can calculate the final score by converting each row to a decimal number and summing them up.

Algorithm:

1. Initialize a variable result to store the final score.
2. Iterate through each column:
   • Count the number of ones and zeros in the column.
   • If the number of ones is less than the number of zeros, toggle the column.
3. Calculate the final score by converting each row to a decimal number and summing them up.

Time Complexity:

The time complexity of this algorithm is O(m*n), where m is the number of rows and n is the number of columns in the grid.

Space Complexity:

The space complexity of this algorithm is O(1) as we are not using any extra space apart from a few variables.

class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int result = 0;
        
        for (int j = 0; j < n; j++) {
            int ones = 0;
            for (int i = 0; i < m; i++) {
                ones += grid[i][j] == 1 ? 1 : 0;
            }
            if (ones < m - ones) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            int rowVal = 0;
            for (int j = 0; j < n; j++) {
                rowVal = rowVal * 2 + grid[i][j];
            }
            result += rowVal;
        }
        
        return result;
    }
}