Problem Description

You are given an n x n binary matrix called image. Your task is to perform two operations on this matrix and return the result:

1. Flip the image horizontally: This means reversing each row of the matrix. For example, if a row is [1,1,0], after flipping horizontally it becomes [0,1,1].

2. Invert the image: After flipping, you need to invert all values in the matrix. This means changing every 0 to 1 and every 1 to 0. For example, if a row is [0,1,1] after flipping, inverting it results in [1,0,0].

The problem asks you to apply both operations in sequence (first flip, then invert) to the entire matrix and return the transformed matrix.

Example walkthrough:

• Original row: [1,1,0]
• After horizontal flip: [0,1,1]
• After inversion: [1,0,0]

The solution uses a clever optimization: instead of performing the flip and invert as two separate operations, it combines them using two pointers. When comparing elements from both ends of a row, if they are equal, flipping would make them swap positions but remain equal, and then inverting would change both values - this is equivalent to just inverting both values in place. If they are different, flipping would swap them and inverting would flip their values again, resulting in no net change to their values.

Intuition

Let's think about what happens to each element when we flip and then invert a row. Consider any row and look at two elements: one at position i from the left and another at position j from the right (where j = n-1-i).

After flipping horizontally, these two elements swap positions. Then after inverting, both values get flipped from 0 to 1 or from 1 to 0.

Now here's the key insight: instead of actually swapping and then inverting, let's analyze what the final result would be:

Case 1: When row[i] == row[j]

• Let's say both are 1. After flipping, they swap but remain 1 at their new positions. After inverting, both become 0.
• If both were 0, after flipping they're still 0 at swapped positions, then after inverting both become 1.
• Notice that in both scenarios, we end up with the opposite values at both positions. This is exactly what XOR with 1 does: value ^ 1.

Case 2: When row[i] != row[j]

• If row[i] = 1 and row[j] = 0, after flipping they become row[i] = 0 and row[j] = 1. After inverting, they become row[i] = 1 and row[j] = 0.
• The values remain exactly the same as before! The swap followed by inversion cancels out.

This observation leads to an elegant solution: we can use two pointers scanning from both ends toward the center. When the values are equal, we just invert both (using XOR with 1). When they're different, we do nothing. For the middle element (when n is odd), it stays in the same position after flipping, so we only need to invert it.

This way, we can transform the matrix in-place with a single pass through each row, avoiding the need to explicitly perform the flip operation.

Learn more about Two Pointers patterns.

Solution Approach

The solution implements a two-pointer technique to process each row of the matrix in-place.

Algorithm Steps:

1. Iterate through each row of the matrix independently.

2. For each row, initialize two pointers:

   • i starting at index 0 (leftmost element)
   • j starting at index n-1 (rightmost element)

3. Process elements while i < j:

   • Check if row[i] == row[j]:
     • If they are equal, apply XOR with 1 to both elements: row[i] ^= 1 and row[j] ^= 1
     • This inverts both values (0 becomes 1, 1 becomes 0)
   • If they are different, do nothing (as the flip and invert operations cancel out)
   • Move pointers toward center: i += 1 and j -= 1

4. Handle the middle element (when i == j):

   • This only occurs when the row has odd length
   • The middle element doesn't move during horizontal flip, so we only need to invert it: row[i] ^= 1

5. Return the modified matrix after processing all rows.

Key Implementation Details:

• The XOR operation (^=) with 1 is used for inversion: 0 ^ 1 = 1 and 1 ^ 1 = 0
• The solution modifies the input matrix in-place, achieving O(1) space complexity
• Time complexity is O(n²) where we visit each element exactly once
• No additional data structures are needed beyond the two pointer variables

This approach elegantly combines the flip and invert operations into a single pass, avoiding the need to explicitly reverse each row and then invert all values separately.

Example Walkthrough

Let's walk through the solution with a small 3x3 matrix to see how the two-pointer approach works:

Input matrix:

[[1, 1, 0],
 [1, 0, 1],
 [0, 0, 0]]

Processing Row 1: [1, 1, 0]

• Initialize pointers: i = 0 (pointing to 1), j = 2 (pointing to 0)
• Compare row[0] and row[2]: 1 ≠ 0 (different)
  • Since they're different, do nothing
  • Move pointers: i = 1, j = 1
• Now i == j (middle element)
  • Invert row[1]: 1 ^ 1 = 0
• Result: [1, 0, 0]

Processing Row 2: [1, 0, 1]

• Initialize pointers: i = 0 (pointing to 1), j = 2 (pointing to 1)
• Compare row[0] and row[2]: 1 == 1 (equal)
  • Invert both: row[0] = 1 ^ 1 = 0, row[2] = 1 ^ 1 = 0
  • Move pointers: i = 1, j = 1
• Now i == j (middle element)
  • Invert row[1]: 0 ^ 1 = 1
• Result: [0, 1, 0]

Processing Row 3: [0, 0, 0]

• Initialize pointers: i = 0 (pointing to 0), j = 2 (pointing to 0)
• Compare row[0] and row[2]: 0 == 0 (equal)
  • Invert both: row[0] = 0 ^ 1 = 1, row[2] = 0 ^ 1 = 1
  • Move pointers: i = 1, j = 1
• Now i == j (middle element)
  • Invert row[1]: 0 ^ 1 = 1
• Result: [1, 1, 1]

Final Output:

[[1, 0, 0],
 [0, 1, 0],
 [1, 1, 1]]

To verify this is correct, let's check row 1 using the traditional approach:

• Original: [1, 1, 0]
• After flip: [0, 1, 1]
• After invert: [1, 0, 0] ✓

The two-pointer approach achieves the same result in a single pass!

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the number of rows (or columns) in the matrix. The algorithm iterates through each of the n rows, and for each row, it processes approximately n/2 pairs of elements using the two-pointer approach (from index 0 to n-1). Even though each row only requires n/2 iterations due to the two-pointer technique, this still results in O(n) operations per row. With n rows total, the overall time complexity is O(n) × O(n) = O(n²).

The space complexity is O(1). The algorithm modifies the input matrix in-place without using any additional data structures that scale with the input size. Only a constant amount of extra space is used for the loop variables (i, j, and row), regardless of the matrix dimensions.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Middle Element Handling

The Pitfall: A common mistake is forgetting to handle the middle element in odd-length rows or incorrectly placing the middle element logic inside the while loop.

Incorrect Implementation:

while left <= right:  # Wrong condition!
    if row[left] == row[right]:
        row[left] ^= 1
        row[right] ^= 1
    left += 1
    right -= 1

Why it's wrong: Using left <= right causes the middle element to be processed twice when left == right, inverting it twice (which cancels out the inversion).

Correct Solution:

while left < right:
    if row[left] == row[right]:
        row[left] ^= 1
        row[right] ^= 1
    left += 1
    right -= 1

# Handle middle element separately
if left == right:
    row[left] ^= 1

2. Misunderstanding the Logic When Elements Are Different

The Pitfall: Explicitly swapping elements when they're different, not realizing that doing nothing achieves the correct result.

Incorrect Implementation:

if row[left] == row[right]:
    row[left] ^= 1
    row[right] ^= 1
else:
    # Unnecessary swap and invert
    row[left], row[right] = row[right], row[left]
    row[left] ^= 1
    row[right] ^= 1

Why it's wrong: When elements are different (e.g., left=0, right=1), flipping makes them (1, 0), then inverting makes them (0, 1). This is exactly what we started with, so no operation is needed.

Correct Solution: Simply do nothing when elements are different.

3. Using Row Index Instead of Column Index

The Pitfall: Using the wrong dimension for the right pointer initialization.

Incorrect Implementation:

for row in image:
    left = 0
    right = len(image) - 1  # Wrong! This is number of rows

Correct Solution:

for row in image:
    left = 0
    right = len(row) - 1  # Correct: use row length
    # OR
    right = len(image[0]) - 1  # Since it's an n x n matrix

4. Creating New Matrix Instead of In-Place Modification

The Pitfall: Creating a new matrix when the problem can be solved in-place, leading to unnecessary space complexity.

Less Optimal:

result = []
for row in image:
    new_row = []
    for i in range(len(row) - 1, -1, -1):
        new_row.append(row[i] ^ 1)
    result.append(new_row)
return result

Better Solution: Modify the input matrix directly as shown in the original solution, achieving O(1) space complexity.