Flipping an Image - Video Solutions

Problem Overview: You are given a binary matrix. For every row, first flip it horizontally (reverse the row), then invert each bit (0 becomes 1 and 1 becomes 0). The goal is to transform the image in-place and return the updated matrix.

Approach 1: Two-Pass Method - Flip then Invert (Time: O(n*m), Space: O(1))

The straightforward approach performs the two required operations separately. First iterate through each row of the array and reverse it using two pointers from both ends. This horizontal flip swaps row[left] with row[right] until the pointers meet. After the row is reversed, iterate through it again and invert every bit using bit = 1 - bit or a conditional toggle.

This method is easy to reason about because it mirrors the problem statement exactly: flip first, then invert. Each cell is processed twice—once during the reversal and once during inversion—resulting in O(n*m) time complexity for an n by m matrix. Space complexity remains O(1) because the transformation happens in-place.

Approach 2: Single-Pass Optimization (Time: O(n*m), Space: O(1))

The optimized approach combines the flip and invert steps into a single pass. Use the two pointers technique on each row. While swapping elements from both ends, invert them at the same time. When swapping row[left] and row[right], assign the inverted values directly using a bit manipulation trick such as value ^ 1 to toggle the bit.

If both elements are the same, the swap would normally leave them unchanged after inversion. Handling the inversion during the swap avoids doing a second pass. For odd-length rows, the middle element just needs a single inversion when left == right.

This approach still processes each cell once, giving O(n*m) time complexity, but it reduces redundant work and keeps the implementation concise. The matrix is updated in-place, so the space complexity stays O(1).

Recommended for interviews: Interviewers typically expect the single-pass solution. The two-pass method demonstrates that you understand the problem transformation clearly, but combining the operations using two pointers and bit inversion shows stronger algorithmic thinking and optimization skills.