Score After Flipping Matrix

Score After Flipping Matrix

What is this problem about?

The Score After Flipping Matrix interview question gives you a binary matrix. You can toggle (flip) any row or any column (changing all 0s to 1s and all 1s to 0s). After any number of such operations, maximize the total score, where the score is the sum of integer values of each row when read as a binary number (most significant bit on the left).

Why is this asked in interviews?

IIT Bombay, Amazon, Google, and Bloomberg ask this problem because it requires combining greedy decision-making with bit manipulation insights. It tests whether candidates can identify: (1) the leading bit of each row must be 1 (row flips), and (2) each column should have more 1s than 0s (column flips). Both are locally optimal decisions that compose into a global maximum — a clean greedy problem with mathematical depth.

Algorithmic pattern used

The pattern is greedy with bit manipulation. Step 1: ensure every row starts with a 1 (flip any row whose first element is 0 — this maximizes the most significant bit contribution). Step 2: for each column from index 1 onward, count the number of 1s. If 0s outnumber 1s, flip the column (making the majority 1s maximizes the column's contribution). Step 3: compute the total score by reading each row as a binary number.

Example explanation

Matrix:

0 0 1 1
1 0 1 0
1 1 0 0

Step 1 — Flip rows starting with 0 (row 0):

1 1 0 0
1 0 1 0
1 1 0 0

Step 2 — Check columns 1–3:

• Col 1: three 1s, zero 0s → no flip needed.
• Col 2: two 1s, one 0 → no flip.
• Col 3: zero 1s, three 0s → flip!

1 1 0 1
1 0 1 1
1 1 0 1

Step 3 — Row scores (binary → decimal):

• 1101 = 13.
• 1011 = 11.
• 1101 = 13.

Total: 37.

Common mistakes candidates make

• Not performing row flips before column flips — row flips must come first since the leading bit contributes the most.
• Flipping a column when 1s and 0s are equal — no benefit, skip it.
• Computing the score before all flips are applied.
• Not recognizing that the order of operations matters: row-first, then column.

Interview preparation tip

For the Score After Flipping Matrix coding problem, the greedy and bit manipulation interview pattern requires understanding why leading-bit maximization dominates all other bits combined. The leading bit of an n-bit row is worth more than all other bits combined (2^(n-1) > 2^(n-2) + ... + 1). Google interviewers appreciate when you state this mathematical justification explicitly before coding. Practice computing binary values of modified rows to verify your greedy strategy.