861. Score After Flipping Matrix LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 861. Score After Flipping Matrix LeetCode Solution with the best time and space complexity. The solution to Score After Flipping Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Score After Flipping Matrix solution in C++
Score After Flipping Matrix solution in Java
Score After Flipping Matrix solution in Python
Additional Resources

861. Score After Flipping Matrix LeetCode Solution image

Problem Statement of Score After Flipping Matrix

You are given an m x n binary matrix grid.
A move consists of choosing any row or column and toggling each value in that row or column (i.e., changing all 0’s to 1’s, and all 1’s to 0’s).
Every row of the matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
Return the highest possible score after making any number of moves (including zero moves).

Example 1:

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Example 2:

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

Constraints:

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

861. Score After Flipping Matrix LeetCode Solution in C++

class Solution {
 public:
  int matrixScore(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;

    // Flip the rows with a leading 0.
    for (auto& row : grid)
      if (row[0] == 0)
        flip(row);

    // Flip the columns with 1s < 0s.
    for (int j = 0; j < n; ++j)
      if (onesColCount(grid, j) * 2 < m)
        flipCol(grid, j);

    // Add a binary number for each row.
    for (const vector<int>& row : grid)
      ans += binary(row);

    return ans;
  }

 private:
  void flip(vector<int>& row) {
    for (int i = 0; i < row.size(); ++i)
      row[i] ^= 1;
  }

  int onesColCount(const vector<vector<int>>& grid, int j) {
    int ones = 0;
    for (int i = 0; i < grid.size(); ++i)
      ones += grid[i][j];
    return ones;
  }

  void flipCol(vector<vector<int>>& grid, int j) {
    for (int i = 0; i < grid.size(); ++i)
      grid[i][j] ^= 1;
  }

  int binary(const vector<int>& row) {
    int res = row[0];
    for (int j = 1; j < row.size(); ++j)
      res = res * 2 + row[j];
    return res;
  }
};
/* code provided by PROGIEZ */

861. Score After Flipping Matrix LeetCode Solution in Java

class Solution {
  public int matrixScore(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;

    // Flip the rows with a leading 0.
    for (int[] row : grid)
      if (row[0] == 0)
        flip(row);

    // Flip the columns with 1s < 0s.
    for (int j = 0; j < n; ++j)
      if (onesColCount(grid, j) * 2 < m)
        flipCol(grid, j);

    // Add a binary number for each row.
    for (int[] row : grid)
      ans += binary(row);

    return ans;
  }

  private void flip(int[] row) {
    for (int i = 0; i < row.length; ++i)
      row[i] ^= 1;
  }

  private int onesColCount(int[][] grid, int j) {
    int ones = 0;
    for (int i = 0; i < grid.length; ++i)
      ones += grid[i][j];
    return ones;
  }

  private void flipCol(int[][] grid, int j) {
    for (int i = 0; i < grid.length; ++i)
      grid[i][j] ^= 1;
  }

  private int binary(int[] row) {
    int res = row[0];
    for (int j = 1; j < row.length; ++j)
      res = res * 2 + row[j];
    return res;
  }
}
// code provided by PROGIEZ

861. Score After Flipping Matrix LeetCode Solution in Python

class Solution:
  def matrixScore(self, grid: list[list[int]]) -> int:
    # Flip the rows with a leading 0.
    for row in grid:
      if row[0] == 0:
        self._flip(row)

    # Flip the columns with 1s < 0s.
    for j, col in enumerate(list(zip(*grid))):
      if sum(col) * 2 < len(grid):
        self._flipCol(grid, j)

    # Add a binary number for each row.
    return sum(self._binary(row) for row in grid)

  def _flip(self, row: list[int]) -> None:
    for i in range(len(row)):
      row[i] ^= 1

  def _flipCol(self, grid: list[list[int]], j: int) -> None:
    for i in range(len(grid)):
      grid[i][j] ^= 1

  def _binary(self, row: list[int]) -> int:
    res = row[0]
    for j in range(1, len(row)):
      res = res * 2 + row[j]
    return res
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents