We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Score After Flipping Matrix

Number: 891

Difficulty: Medium

Paid? No

Companies: Google, IIT Bombay

Problem Description

Given an m x n binary matrix, you are allowed to perform any number of moves. A move consists of toggling all the values of any row or any column (0 becomes 1 and 1 becomes 0). Every row of the matrix is interpreted as a binary number. Your goal is to maximize the sum of these binary numbers (the final score). Return the highest possible score after any number of moves.

Key Insights

  • The leftmost bit (most significant bit) of each row has the highest weight. To maximize the score, ensure it is always 1.
  • Toggling an entire row may be needed so that the first element becomes 1.
  • For each column (after ensuring the first column is all 1’s), decide whether to toggle the column based on maximizing the number of 1’s. Specifically, choose the toggle that results in the maximum count of 1’s for that column.
  • The contribution of each column to the overall score is determined by its weight, which is 2^(n-col_index-1).

Space and Time Complexity

Time Complexity: O(m * n) because we iterate over each element of the matrix multiple times. Space Complexity: O(1) extra space (in-place modifications or constant extra variables), not counting the input matrix.

Solution

The solution uses a greedy algorithm. First, ensure each row’s most significant bit (the first column) is 1 by toggling the row if necessary. Then, for each column, determine whether to toggle it by comparing the count of 1’s versus 0’s (keeping in mind that flipping a column will swap these counts). Finally, compute the score by treating each row as a binary number based on the optimized bits. The main data structure used is the matrix itself, and we simply iterate through rows and columns, making decisions to maximize the score based on bit weights.

Code Solutions

# Python solution for Score After Flipping Matrix
class Solution:
    def matrixScore(self, grid):
        # Number of rows and columns in the grid.
        m, n = len(grid), len(grid[0])
        
        # Step 1: Ensure the first column of each row is 1.
        # If the first element is 0, toggle the entire row.
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] = 1 - grid[i][j]
        
        # Step 2: For each column, count the ones.
        total_score = 0
        for j in range(n):
            ones_count = 0
            for i in range(m):
                # If the row was toggled in step 1, the effective value is grid[i][j],
                # because we already made the first column 1.
                ones_count += grid[i][j]
            # For column j, the maximum 1's possible is the higher of ones_count and zeros_count (m - ones_count).
            max_ones = max(ones_count, m - ones_count)
            # Calculate the column's contribution to the total score.
            # The weight is determined by its position.
            total_score += max_ones * (1 << (n - j - 1))
        return total_score

# Example usage:
# sol = Solution()
# print(sol.matrixScore([[0,0,1,1],[1,0,1,0],[1,1,0,0]]))
← Back to All Questions