Score After Flipping Matrix - Practice Coding Problems

Score After Flipping Matrix - Problem

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

Input & Output

Example 1 — Basic Matrix

$ Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]

› Output: 39

💡 Note: After optimal flips: flip row 0 to get [[1,1,0,0],[1,0,1,0],[1,1,0,0]], then flip column 1 to get [[1,0,0,0],[1,1,1,0],[1,0,0,0]]. Final score: 8+14+8=30. Actually, better solution gives 39.

Example 2 — Single Row

$ Input: grid = [[0]]

› Output: 1

💡 Note: Single cell matrix. Flip the row to change 0 to 1. Score becomes 1.

Example 3 — Already Optimal

$ Input: grid = [[1,1,1],[1,1,1]]

› Output: 14

💡 Note: Matrix is already optimal. Each row has value 7 (111 in binary), so total score is 7+7=14.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix where each row represents a binary number

Apply Flips

Strategically flip rows and columns to maximize score

Calculate Score

Sum the binary values of all rows

Key Takeaway

🎯 Key Insight: Prioritize leftmost columns first since they contribute exponentially more to the final score

Asked in

G Google 12 A Amazon 8 M Microsoft 6

The key insight is to use a greedy approach: first ensure all leftmost bits are 1 (highest value), then optimize each subsequent column. Best approach is greedy column optimization in O(mn) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^(m+n) × m × n)	O(1)	Try all possible combinations of row and column flips
Greedy - Optimize Column by Column	O(m × n)	O(1)	First ensure all rows start with 1, then optimize each column from left to right

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible combinations of rows and columns to flip
For each combination, simulate the flips and calculate score
Return the maximum score found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible row/column flip combinations

Apply Flips

For each combination, flip the specified rows and columns

Calculate Score

Convert each row to binary number and sum them

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    int maxScore = 0;
    
    // Try all combinations of row and column flips
    for (int rowMask = 0; rowMask < (1 << m); rowMask++) {
        for (int colMask = 0; colMask < (1 << n); colMask++) {
            // Create copy of grid
            int** temp = (int**)malloc(m * sizeof(int*));
            for (int i = 0; i < m; i++) {
                temp[i] = (int*)malloc(n * sizeof(int));
                memcpy(temp[i], grid[i], n * sizeof(int));
            }
            
            // Apply row flips
            for (int i = 0; i < m; i++) {
                if (rowMask & (1 << i)) {
                    for (int j = 0; j < n; j++) {
                        temp[i][j] = 1 - temp[i][j];
                    }
                }
            }
            
            // Apply column flips
            for (int j = 0; j < n; j++) {
                if (colMask & (1 << j)) {
                    for (int i = 0; i < m; i++) {
                        temp[i][j] = 1 - temp[i][j];
                    }
                }
            }
            
            // Calculate score
            int score = 0;
            for (int i = 0; i < m; i++) {
                int rowVal = 0;
                for (int j = 0; j < n; j++) {
                    rowVal = rowVal * 2 + temp[i][j];
                }
                score += rowVal;
            }
            
            if (score > maxScore) {
                maxScore = score;
            }
            
            // Free memory
            for (int i = 0; i < m; i++) {
                free(temp[i]);
            }
            free(temp);
        }
    }
    
    return maxScore;
}

int main() {
    // Simple parsing for small test cases
    int grid[4][4] = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    int colSizes[3] = {4, 4, 4};
    
    printf("%d\n", solution(gridPtr, 3, colSizes));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(m+n) × m × n)

2^(m+n) combinations, each requiring O(m×n) to calculate score

✓ Linear Growth

Space Complexity

O(1)

Only using variables for tracking current best score

✓ Linear Space

89.5K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler