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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Score After Flipping Matrix

Difficulty: Medium

Problem Description

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).

Key Insights

  • Flipping a row or column changes the binary representation of the rows in the matrix.
  • The most significant bit (leftmost) contributes the most to the score; hence, we should aim to maximize the number of 1s in that position.
  • For each column, we can decide to flip it or not based on the number of 0s and 1s.
  • The maximum score can be computed by treating each row as a binary number and maximizing each bit position from left to right.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Solution

To solve the problem, we use the following approach:

  1. For each row, determine the contribution to the score by evaluating each bit position.
  2. Start from the most significant bit (leftmost) and calculate its value based on the majority of 1s in that column.
  3. If there are more 0s than 1s in a column, consider flipping the column to maximize the number of 1s.
  4. Calculate the total score by summing the values of each row interpreted as binary numbers.

Code Solutions

def matrixScore(grid):
    m, n = len(grid), len(grid[0])
    
    # Step 1: Ensure the first column is all 1's
    for i in range(m):
        if grid[i][0] == 0:
            for j in range(n):
                grid[i][j] = 1 - grid[i][j]
    
    # Step 2: Process each column from the second column onwards
    for j in range(1, n):
        count_ones = sum(grid[i][j] for i in range(m))
        if count_ones < m / 2:
            for i in range(m):
                grid[i][j] = 1 - grid[i][j]
    
    # Step 3: Calculate the final score
    score = 0
    for i in range(m):
        row_value = 0
        for j in range(n):
            row_value = row_value * 2 + grid[i][j]
        score += row_value
    
    return score
← Back to All Questions