LeetCode 832: Flipping an Image

Problem Restatement

We are given an n x n binary matrix image.

Each cell is either:

We need to do two operations:

1. Flip the image horizontally.
2. Invert the image.

Flipping horizontally means reversing each row.

For example:

[1, 1, 0] -> [0, 1, 1]

Inverting means changing every 0 to 1 and every 1 to 0.

For example:

[0, 1, 1] -> [1, 0, 0]

Return the final image.

Input and Output

Function shape:

class Solution:
    def flipAndInvertImage(self, image: list[list[int]]) -> list[list[int]]:
        ...

Examples

Example 1:

image = [
    [1, 1, 0],
    [1, 0, 1],
    [0, 0, 0],
]

First reverse each row:

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

Then invert each bit:

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

So the answer is:

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

Example 2:

image = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 1, 1, 1],
    [1, 0, 1, 0],
]

The result is:

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

First Thought: Build a New Matrix

The direct way is to create a new matrix.

For each row:

1. Read the row from right to left.
2. Invert each value.
3. Append the inverted value to a new row.

class Solution:
    def flipAndInvertImage(self, image: list[list[int]]) -> list[list[int]]:
        result = []

        for row in image:
            new_row = []

            for value in reversed(row):
                new_row.append(1 - value)

            result.append(new_row)

        return result

This is simple and correct.

Problem With Extra Matrix

The new-matrix solution uses extra memory for the whole result.

Since the operation can be done directly inside image, we can reduce auxiliary space.

We can reverse and invert at the same time using two pointers on each row.

Key Insight

For each row, the value at the left side should move to the right side, and the value at the right side should move to the left side.

But after moving, both values must also be inverted.

So for a pair:

left_value = row[left]
right_value = row[right]

After flip and invert:

row[left] = 1 - right_value
row[right] = 1 - left_value

Since values are only 0 and 1, we can invert with either:

1 - value

or:

value ^ 1

The ^ 1 form flips a binary bit.

Algorithm

For each row:

1. Set left = 0.
2. Set right = n - 1.
3. While left <= right:
   1. Save row[left].
   2. Set row[left] to the inverted old value from row[right].
   3. Set row[right] to the inverted old value from saved row[left].
   4. Move left rightward.
   5. Move right leftward.

The condition left <= right handles odd-length rows.

When left == right, the middle element must only be inverted once.

Walkthrough

Use one row:

row = [1, 1, 0]

Start:

left = 0
right = 2

The left value is 1.

The right value is 0.

After flip and invert:

row[0] = 1 - 0 = 1
row[2] = 1 - 1 = 0

The row is still:

[1, 1, 0]

Move inward:

left = 1
right = 1

This is the middle value.

Invert it:

1 -> 0

Final row:

[1, 0, 0]

This matches reversing first and inverting after:

[1, 1, 0] -> [0, 1, 1] -> [1, 0, 0]

Correctness

Consider any row and any pair of mirrored positions left and right.

In the final flipped row, the value at left must come from the original value at right.

Since the image is also inverted, the final value at left must be the inverse of the original value at right.

The algorithm assigns exactly that:

row[left] = 1 - old_row[right]

Similarly, the final value at right must be the inverse of the original value at left.

The algorithm assigns:

row[right] = 1 - old_row[left]

The saved temporary value preserves the original left value before it is overwritten.

For odd-length rows, when left == right, the middle element maps to itself after the flip, so it only needs inversion. The same formula correctly changes it from 0 to 1 or from 1 to 0.

Every row is processed this way, so every cell receives exactly the value it should have after horizontal flip and inversion.

Therefore, the algorithm returns the correct transformed image.

Complexity

Implementation

class Solution:
    def flipAndInvertImage(self, image: list[list[int]]) -> list[list[int]]:
        n = len(image)

        for row in image:
            left = 0
            right = n - 1

            while left <= right:
                old_left = row[left]

                row[left] = row[right] ^ 1
                row[right] = old_left ^ 1

                left += 1
                right -= 1

        return image

Code Explanation

We process each row independently:

for row in image:

The two pointers start at both ends:

left = 0
right = n - 1

We continue while the pointers have not crossed:

while left <= right:

Before overwriting row[left], we save it:

old_left = row[left]

Then we move the right value to the left side and invert it:

row[left] = row[right] ^ 1

Then we move the saved left value to the right side and invert it:

row[right] = old_left ^ 1

Finally, we move inward:

left += 1
right -= 1

When all rows are processed, the matrix has already been transformed in place.

Testing

def run_tests():
    s = Solution()

    assert s.flipAndInvertImage([
        [1, 1, 0],
        [1, 0, 1],
        [0, 0, 0],
    ]) == [
        [1, 0, 0],
        [0, 1, 0],
        [1, 1, 1],
    ]

    assert s.flipAndInvertImage([
        [1, 1, 0, 0],
        [1, 0, 0, 1],
        [0, 1, 1, 1],
        [1, 0, 1, 0],
    ]) == [
        [1, 1, 0, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 1],
        [1, 0, 1, 0],
    ]

    assert s.flipAndInvertImage([[1]]) == [[0]]
    assert s.flipAndInvertImage([[0]]) == [[1]]
    assert s.flipAndInvertImage([[1, 0], [0, 1]]) == [[1, 0], [0, 1]]

    print("all tests passed")

run_tests()

Test meaning: