Definition
- Flip – reversing each row horizontally, swapping elements from both ends toward the middle.
- Invert – replacing each 0 with 1 and each 1 with 0, which is exactly XOR with 1.
- Fused pass – walk each row from both ends inward, placing
row[hi] ^ 1at the left androw[lo] ^ 1at the right in one step. - Odd-length middle – when
lo == hi, the single middle element is inverted but not swapped. - Complexity – O(rows * cols) time and O(1) extra space, modifying in place.
At the National Bank of India, a cheque-scanning module stores each scanned line as a row of zeros and ones. A legacy reader needs every line mirrored left-to-right and with its ink bits inverted. Rajesh walks each line from both ends toward the middle, flipping each bit by XOR-ing with one and swapping as he goes.
Understanding the Concepts
What is the Flip and Invert Image problem?
Given a binary matrix (containing only 0s and 1s), produce a matrix where each row is first reversed horizontally and then each bit is inverted (0 becomes 1, 1 becomes 0). The two operations can be fused into a single pass per row.
package com.bank.service;
public class FlipAndInvert {
public int[][] flipAndInvertImage(int[][] image) {
for (int[] row : image) {
int lo = 0, hi = row.length - 1;
while (lo <= hi) {
if (lo == hi) {
row[lo] ^= 1;
} else {
int temp = row[lo] ^ 1;
row[lo] = row[hi] ^ 1;
row[hi] = temp;
}
lo++;
hi--;
}
}
return image;
}
}
Why does XOR with 1 invert a bit?
XOR with 1 flips a bit because of how XOR works: 0 XOR 1 = 1 (flips 0 to 1) and 1 XOR 1 = 0 (flips 1 to 0). This eliminates the need for a conditional check when inverting.
package com.bank.service;
public class XORInvertDemo {
public static void main(String[] args) {
System.out.println("0 ^ 1 = " + (0 ^ 1)); // 1
System.out.println("1 ^ 1 = " + (1 ^ 1)); // 0
// No conditional needed:
int bit = 0;
bit ^= 1; // now 1
System.out.println("After invert: " + bit);
bit ^= 1; // now 0
System.out.println("After invert again: " + bit);
}
}
0 ^ 1 = 1
1 ^ 1 = 0
After invert: 1
After invert again: 0
How do you fuse reverse and invert into one pass?
Instead of reversing the row first and then inverting in a second pass, we walk from both ends inward with two pointers. At each step, we place the inverted right value on the left and the inverted left value on the right. This does both operations simultaneously.
package com.bank.service;
public class FusedPassDemo {
public static void main(String[] args) {
int[] row = {1, 1, 0, 0};
System.out.println("Before: " + java.util.Arrays.toString(row));
int lo = 0, hi = row.length - 1;
while (lo <= hi) {
if (lo == hi) {
row[lo] ^= 1;
} else {
int temp = row[lo] ^ 1;
row[lo] = row[hi] ^ 1;
row[hi] = temp;
}
lo++; hi--;
}
System.out.println("After: " + java.util.Arrays.toString(row));
// Reverse of [1,1,0,0] is [0,0,1,1]
// Invert: [1,1,0,0] -> that is the result
}
}
Before: [1, 1, 0, 0]
After: [1, 1, 0, 0]
How do you handle the middle element of an odd-length row?
When the row has an odd number of elements, the two pointers meet at the middle. This element does not need to be swapped with anything; it only needs to be inverted.
package com.bank.service;
public class OddLengthMiddle {
public static void main(String[] args) {
int[] row = {1, 0, 1}; // odd length
int lo = 0, hi = 2;
// Step 1: lo=0, hi=2 -> swap inverted
int temp = row[0] ^ 1; // 0
row[0] = row[2] ^ 1; // 0
row[2] = temp; // 0
// Step 2: lo=1, hi=1 -> middle, just invert
row[1] ^= 1; // 0 -> 1
System.out.println(java.util.Arrays.toString(row));
// [0, 1, 0]
}
}
[0, 1, 0]
What is the time and space complexity?
The fused approach visits each cell exactly once across all rows. No temporary matrix is needed because the operations are done in place.
- Time complexity – O(rows * cols), visiting each cell once.
- Space complexity – O(1) extra space beyond the input matrix.
- Comparison – a naive two-pass approach (reverse then invert) visits each cell twice and may allocate a temporary row.
// Fused: one pass per row, O(1) extra space
for (int[] row : image) {
int lo = 0, hi = row.length - 1;
while (lo <= hi) { /* fused reverse + invert */ }
}
// Naive: two passes per row
for (int[] row : image) {
Collections.reverse(row); // pass 1
for (int j = 0; j < row.length; j++) row[j] ^= 1; // pass 2
}
What are common mistakes?
The most common mistake is not handling the odd-length middle element, causing it to be either double-inverted (returning to original) or not inverted at all. Another mistake is creating a temporary matrix when one is not needed.
// WRONG: middle element double-processed
while (lo < hi) {
// this skips the middle element entirely!
int temp = row[lo] ^ 1;
row[lo] = row[hi] ^ 1;
row[hi] = temp;
lo++; hi--;
}
// Middle element at lo==hi is never inverted!
// CORRECT: include lo == hi case
while (lo <= hi) {
if (lo == hi) {
row[lo] ^= 1; // only invert, no swap
} else {
int temp = row[lo] ^ 1;
row[lo] = row[hi] ^ 1;
row[hi] = temp;
}
lo++; hi--;
}
How is this different from a simple matrix transpose?
Flip and Invert operates within each row independently (horizontal flip + invert). A matrix transpose swaps rows and columns across the entire matrix. They are fundamentally different operations.
| Aspect | Flip and Invert | Matrix Transpose |
|---|---|---|
| Scope | Per-row operation | Whole-matrix operation |
| Reverse direction | Horizontal (left-right) | Rows become columns |
| Inversion | Yes (XOR with 1) | No |
| Matrix shape | Rows unchanged | Rows and cols swap |
// Flip and Invert: per row
for (int[] row : matrix) { /* reverse and invert row */ }
// Transpose: swap matrix[i][j] and matrix[j][i]
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
How would you apply this in a banking system?
At the National Bank of India, a cheque-scanning module stores each scanned line as a binary row. A legacy reader expects every line mirrored and inverted. The fused reverse-and-invert pass processes large scan batches without allocating a second matrix.
package com.bank.service;
public class ChequeScanProcessor {
public int[][] processForLegacyReader(int[][] scanLines) {
for (int[] line : scanLines) {
int lo = 0, hi = line.length - 1;
while (lo <= hi) {
if (lo == hi) {
line[lo] ^= 1;
} else {
int temp = line[lo] ^ 1;
line[lo] = line[hi] ^ 1;
line[hi] = temp;
}
lo++; hi--;
}
}
return scanLines;
}
}
What should a senior engineer know?
A senior engineer should recognise that reverse and invert are commutative cell-wise: reversing then inverting gives the same result as inverting then reversing. This commutativity is what allows fusing them into one pass. They should also note that when lo != hi and row[lo] == row[hi], the swap-then-invert has no net effect (both values stay the same), which could be used as a minor optimisation.
// Optimisation: if row[lo] == row[hi], the fused op is a no-op
if (lo != hi && row[lo] == row[hi]) {
// reverse swaps them, then invert flips both -> net effect: no change
lo++; hi--;
continue;
}
// Otherwise, do the full fused swap-and-invert
Visual Overview
Row: [1, 1, 0] Step 1: lo=0, hi=2 row[0] = row[2] ^ 1 = 0 ^ 1 = 1 row[2] = row[0] ^ 1 = 1 ^ 1 = 0 (using temp for proper swap) → [1, 1, 0] (wait, let me trace carefully) temp = row[0] ^ 1 = 1 ^ 1 = 0 row[0] = row[2] ^ 1 = 0 ^ 1 = 1 row[2] = temp = 0 Row: [1, 1, 0] Step 2: lo=1, hi=1 (middle) row[1] ^= 1 → 1 ^ 1 = 0 Row: [1, 0, 0] Verification: Original: [1, 1, 0] Reversed: [0, 1, 1] Inverted: [1, 0, 0] ✓ ┌─────────────────────────────┐ │ Original: 1 1 0 │ │ Reverse: 0 1 1 │ │ Invert: 1 0 0 │ │ Fused: 1 0 0 ✓ │ └─────────────────────────────┘
Key Takeaway
Flip and Invert an Image combines two row operations on a binary matrix: flip each row horizontally (reverse its order) and invert each bit (turn zeros into ones and ones into zeros). The bit-level insight is that inverting a single bit is exactly XOR with one, because 0 XOR 1 = 1 and 1 XOR 1 = 0, so the inversion needs no conditional.
The optimisation I reach for is fusing the two operations. Instead of reversing the row and then inverting in a second pass, I walk each row from both ends toward the middle with two pointers. At each step, I place the inverted right value on the left and the inverted left value on the right. When the pointers meet at the middle of an odd-length row, that single element is inverted once without a swap.
This touches every cell exactly once and works in place with no temporary matrix. The common mistake is not handling the odd-length middle element, which gets either double-inverted or skipped. A senior engineer recognises that reverse and invert commute cell-wise, which is why fusing them is valid.
At the National Bank of India, I used this in a cheque-scanning module where each scanned line was stored as a binary row and a legacy reader expected every line mirrored and inverted. The fused pass avoided a second matrix and halved the work on large scan batches.
Remember one sentence: XOR with one inverts a bit, so fuse the reverse and the invert into a single two-pointer pass per row.
---