Flipping an Image

Flipping an Image

1. What is this problem about?

The Flipping an Image interview question is a two-step matrix manipulation task. You are given an $n imes n$ binary matrix representing an image. For each row:

1. Flip horizontally: Reverse the order of elements in the row.
2. Invert: Replace 0 with 1 and 1 with 0. The goal is to return the resulting matrix.

2. Why is this asked in interviews?

Companies like Google and Bloomberg ask the Flipping an Image coding problem as an introductory exercise. It tests basic 2D array manipulation and pointer logic. It evaluation if you can combine two operations into a single pass to optimize performance. It’s an essential Matrix interview pattern.

3. Algorithmic pattern used

This problem follows the Two-Pointer Matrix Manipulation pattern.

• Combined Logic: When flipping a row with left and right pointers:
  • If row[left] == row[right], they both need to be inverted. After flipping and inverting, they will still be the same value but flipped (e.g., [0, 0] becomes [1, 1]).
  • If row[left] != row[right], after flipping and inverting, they remain the same as their original values (e.g., [0, 1] flipped is [1, 0], then inverted is [0, 1]).
• Bitwise Inversion: Use val ^ 1 or 1 - val to invert the bit.

4. Example explanation

Row: [1, 1, 0]

1. Flip: [0, 1, 1]
2. Invert: [1, 0, 0] Result: [1, 0, 0]. Using the pointer trick:

• left=0 (1), right=2 (0): Different. No change.
• left=1 (1), right=1 (1): Same. Invert to 0.
• Result: [1, 0, 0].

5. Common mistakes candidates make

• Two passes: Flipping the whole row and then iterating again to invert. While $O(N)$, it's less elegant than doing it in one pass.
• Middle element: Forgetting to invert the middle element in an odd-length row.
• Matrix boundaries: Mistakes in the nested loop indices.

6. Interview preparation tip

Get comfortable with In-place array reversals. Being able to reverse a sequence using two pointers is a foundational skill for all Array interview patterns.