# LeetCode 832: Flipping an Image

## Problem Restatement

We are given an `n x n` binary matrix `image`.

Each cell is either:

| Value | Meaning |
|---|---|
| `0` | White pixel |
| `1` | Black pixel |

We need to do two operations:

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

Flipping horizontally means reversing each row.

For example:

```python
[1, 1, 0] -> [0, 1, 1]
```

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

For example:

```python
[0, 1, 1] -> [1, 0, 0]
```

Return the final image.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` binary matrix `image` |
| Output | The matrix after horizontal flip and inversion |
| Flip | Reverse each row |
| Invert | Replace `0` with `1`, and `1` with `0` |
| Constraint | `1 <= n <= 20` |

Function shape:

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

## Examples

Example 1:

```python
image = [
    [1, 1, 0],
    [1, 0, 1],
    [0, 0, 0],
]
```

First reverse each row:

```python
[
    [0, 1, 1],
    [1, 0, 1],
    [0, 0, 0],
]
```

Then invert each bit:

```python
[
    [1, 0, 0],
    [0, 1, 0],
    [1, 1, 1],
]
```

So the answer is:

```python
[
    [1, 0, 0],
    [0, 1, 0],
    [1, 1, 1],
]
```

Example 2:

```python
image = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 1, 1, 1],
    [1, 0, 1, 0],
]
```

The result is:

```python
[
    [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.

```python
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:

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

After flip and invert:

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

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

```python
1 - value
```

or:

```python
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:

```python
row = [1, 1, 0]
```

Start:

```python
left = 0
right = 2
```

The left value is `1`.

The right value is `0`.

After flip and invert:

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

The row is still:

```python
[1, 1, 0]
```

Move inward:

```python
left = 1
right = 1
```

This is the middle value.

Invert it:

```python
1 -> 0
```

Final row:

```python
[1, 0, 0]
```

This matches reversing first and inverting after:

```python
[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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Every cell is processed once |
| Space | `O(1)` | The matrix is modified in place |

## Implementation

```python
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:

```python
for row in image:
```

The two pointers start at both ends:

```python
left = 0
right = n - 1
```

We continue while the pointers have not crossed:

```python
while left <= right:
```

Before overwriting `row[left]`, we save it:

```python
old_left = row[left]
```

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

```python
row[left] = row[right] ^ 1
```

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

```python
row[right] = old_left ^ 1
```

Finally, we move inward:

```python
left += 1
right -= 1
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `3 x 3` matrix | Confirms odd row length and middle inversion |
| `4 x 4` matrix | Confirms even row length |
| `[[1]]` | Single-cell one becomes zero |
| `[[0]]` | Single-cell zero becomes one |
| Symmetric `2 x 2` case | Confirms flip and invert can leave a row unchanged |