Score After Flipping Matrix Solution in C++

Explore Solutions in Other Languages

Problem Description

The “Score After Flipping Matrix” problem involves maximizing the score of a binary matrix by flipping its rows and columns. The goal is to ensure that the leading bits of the binary numbers represented by each row are as high as possible. This can be likened to arranging a buffet where you want to display the most appealing dishes first.

Code Solution


class Solution {
 public:
  int matrixScore(vector>& 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& row : grid)
      ans += binary(row);

    return ans;
  }

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

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

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

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

Approach Explanation

The solution begins by ensuring that all rows start with a 1. If a row begins with a 0, it is flipped. Next, each column is checked to see if the number of 1s is less than the number of 0s. If so, that column is flipped to maximize the number of 1s. Finally, each row is converted into its binary representation, and the total score is calculated.

Time and Space Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as we are using a constant amount of extra space.

Real-World Example

Imagine you are at a party with a tray of snacks. You want to arrange them to maximize their appeal to your guests. You might flip the tray to show the best snacks first (like flipping rows) and rearrange the snacks to ensure the most popular ones are at the front (like flipping columns). Ultimately, you want your guests to leave with a smile, just as you want to maximize the score in the matrix!