algoadvance

Leetcode 861. Score After Flipping Matrix

Problem Statement

You are given an m x n binary matrix grid. You can perform two types of operations on the matrix:

  1. Flip a row: Change all 0s to 1s and all 1s to 0s in that row.
  2. Flip a column: Change all 0s to 1s and all 1s to 0s in that column.

Your goal is to maximize the sum of the matrix. The value of a matrix is the binary number represented by the row when each row is interpreted as a binary number. Return the highest possible sum of the matrix.

Clarifying Questions

  1. Is it possible to have an empty matrix?
    • No, the matrix will have at least one row and one column.
  2. How are the binary numbers in the matrix structured?
    • Each row of the matrix can be interpreted as a binary number where the leftmost element is the most significant bit.
  3. Are there any constraints on the size of the matrix?
    • The size of the matrix is not excessively large, so a brute-force O(m * n^2) or O(m^2 * n) solution might be feasible.
  4. What is the range of m and n?
    • Typically, constraints on LeetCode problems are such that m and n are both up to 20 or 100.

Strategy

  1. Ensure Leading Bit is 1:
    • To maximize the binary value, each row should start with 1. If the leading bit of any row is 0, flip that row.
  2. Maximize the Number of 1s in Each Column:
    • For each column, starting from the second column, check if more than half of the rows have 0 in that column. If so, flip the entire column to maximize the number of 1s because flipping the column would lead to a higher number of 1s, thereby increasing the total sum.

Code

#include <vector>
#include <cmath>

class Solution {
public:
    int matrixScore(std::vector<std::vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // Step 1: Ensure the first column has all 1s by flipping rows if needed
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                flipRow(grid, i);
            }
        }
        
        // Step 2: Maximize the number of 1s in each column from second to n-th
        for (int j = 1; j < n; j++) {
            int count0 = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 0) {
                    count0++;
                }
            }
            
            if (count0 > m / 2) {
                flipColumn(grid, j);
            }
        }
        
        // Step 3: Calculate the final sum
        int sum = 0;
        for (int i = 0; i < m; i++) {
            int row_value = 0;
            for (int j = 0; j < n; j++) {
                row_value = (row_value << 1) | grid[i][j];
            }
            sum += row_value;
        }
        
        return sum;
    }
    
private:
    void flipRow(std::vector<std::vector<int>>& grid, int row) {
        for (int j = 0; j < grid[0].size(); j++) {
            grid[row][j] ^= 1;
        }
    }
    
    void flipColumn(std::vector<std::vector<int>>& grid, int col) {
        for (int i = 0; i < grid.size(); i++) {
            grid[i][col] ^= 1;
        }
    }
};

Time Complexity

Therefore, the overall time complexity is (O(m \times n)), which is efficient for typical input size constraints.

Conclusion

The provided solution ensures that the matrix is manipulated in such a way that the resulting binary sum is maximized by focusing on flipping rows to ensure leading 1s and flipping columns to maximize the number of 1s per column.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI