# Flipping an Image
**Difficulty:** EASY
[External](https://leetcode.com/problems/flipping-an-image)
Canonical: https://scaleengineer.com/dsa/problems/flipping-an-image
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Matrix
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
Given an `n x n` binary matrix `image`, flip the image **horizontally**, then invert it, and return _the resulting image_.

To flip an image horizontally means that each row of the image is reversed.

* For example, flipping `[1,1,0]` horizontally results in `[0,1,1]`.

To invert an image means that each `0` is replaced by `1`, and each `1` is replaced by `0`.

* For example, inverting `[0,1,1]` results in `[1,0,0]`.

**Example 1:**

**Input:** image = [[1,1,0],[1,0,1],[0,0,0]]
**Output:** [[1,0,0],[0,1,0],[1,1,1]]
**Explanation:** First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

**Example 2:**

**Input:** image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
**Output:** [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
**Explanation:** First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

**Constraints:**

* `n == image.length`
* `n == image[i].length`
* `1 <= n <= 20`
* `images[i][j]` is either `0` or `1`.

# Approaches
## Two-Pass Approach using an Auxiliary Matrix
This approach strictly follows the problem description by performing the two operations, horizontal flipping and inverting, in two separate steps. It uses an auxiliary matrix to store the result, leaving the original matrix unchanged.
**Time:** O(N^2), where N is the dimension of the matrix. We traverse the matrix twice: once for flipping (N*N operations) and once for inverting (N*N operations). · **Space:** O(N^2), where N is the dimension of the matrix. This is because we create a new `result` matrix of size `N x N`.
**Pros:** Simple to understand and implement.; It's a pure function as it does not modify the original input matrix.
**Cons:** Inefficient in terms of space complexity as it requires an auxiliary matrix of the same size as the input.
### Explanation
This method is the most straightforward. First, we create a new `n x n` matrix, say `result`, to store the final image. In the first pass, we iterate through each row of the input `image`. For each row, we reverse it and store the reversed row in the corresponding row of the `result` matrix. In the second pass, we iterate through the `result` matrix and invert each element. An element `0` becomes `1`, and `1` becomes `0`. This can be done using the XOR operation `element = element ^ 1`. Finally, we return the `result` matrix.

```java
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;
        int[][] result = new int[n][n];

        // Step 1: Flip each row horizontally and store in the new matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = image[i][n - 1 - j];
            }
        }

        // Step 2: Invert the new matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = result[i][j] ^ 1; // Invert the bit
            }
        }

        return result;
    }
}
```
### Algorithm
- Initialize a new `n x n` integer matrix `result`.
- Iterate through the input `image` from `i = 0` to `n-1` (rows).
- For each row `i`, iterate from `j = 0` to `n-1` (columns).
- In this inner loop, perform the horizontal flip: `result[i][j] = image[i][n - 1 - j]`.
- After the first pass, iterate through the `result` matrix from `i = 0` to `n-1` and `j = 0` to `n-1`.
- In this second pass, perform the inversion: `result[i][j] = result[i][j] ^ 1`.
- Return the `result` matrix.

## Two-Pass In-place Approach
This approach improves upon the first one by eliminating the need for an auxiliary matrix. It modifies the input matrix directly, thus saving space. The operations are still performed in two separate passes: first flipping all rows, then inverting all elements.
**Time:** O(N^2), where N is the dimension of the matrix. The first pass for flipping takes O(N^2) time, and the second pass for inverting also takes O(N^2) time. · **Space:** O(1), as we modify the matrix in-place and use only a constant amount of extra space for loop variables and temporary storage for swaps.
**Pros:** Highly space-efficient, using only constant extra space.
**Cons:** Requires two passes over the data, which might be slightly less performant than a single-pass solution due to cache effects.; Modifies the input matrix in-place, which might not be desirable in all scenarios.
### Explanation
To achieve the result with O(1) extra space, we can modify the input matrix directly. The first pass reverses each row of the `image` matrix in-place. For each row, we use a two-pointer technique. One pointer starts at the beginning of the row (`left`) and the other at the end (`right`). We swap the elements at these pointers and move them towards the center until they meet or cross. The second pass iterates through the now-flipped matrix and inverts every element using the XOR operator (`^`), which flips a bit (`0` becomes `1`, `1` becomes `0`). The modified input `image` is then returned.

```java
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;

        // Step 1: Flip each row horizontally in-place
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = image[i][left];
                image[i][left] = image[i][right];
                image[i][right] = temp;
                left++;
                right--;
            }
        }

        // Step 2: Invert the image in-place
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                image[i][j] = image[i][j] ^ 1;
            }
        }

        return image;
    }
}
```
### Algorithm
- Iterate through each row of the `image` matrix.
- For each row, reverse it in-place using two pointers, `left` and `right`.
  - Initialize `left = 0`, `right = n - 1`.
  - While `left < right`, swap `image[row][left]` with `image[row][right]`, then increment `left` and decrement `right`.
- After all rows are flipped, iterate through the entire `image` matrix again.
- For each element `image[i][j]`, update it to its inverted value: `image[i][j] = image[i][j] ^ 1`.
- Return the modified `image` matrix.

## Optimal Single-Pass In-place Approach
This is the most efficient approach. It combines the flipping and inverting operations into a single pass for each row. By analyzing the combined effect of the two operations, we can derive a more direct transformation that is both time and space optimal.
**Time:** O(N^2), where N is the dimension of the matrix. We iterate through each row, and for each row, we process up to its midpoint. This results in visiting each element effectively once. · **Space:** O(1), as all modifications are done in-place.
**Pros:** Most efficient in both time and space.; Combines operations into a single pass, which is elegant and can be faster in practice due to better data locality.
**Cons:** The logic is slightly more complex to derive than the straightforward two-pass approach.; Modifies the input matrix in-place.
### Explanation
We can process each row in a single pass using two pointers, `left` and `right`, moving from the ends towards the center. For each pair of elements `image[row][left]` and `image[row][right]`, we need to swap them and then invert them. A key observation simplifies this:
- If `image[row][left]` and `image[row][right]` are the same (e.g., `[1, ..., 1]`), flipping doesn't change their values relative to each other. Inverting them changes both (e.g., to `[0, ..., 0]`).
- If `image[row][left]` and `image[row][right]` are different (e.g., `[1, ..., 0]`), flipping swaps them (to `[0, ..., 1]`), and inverting swaps them back (to `[1, ..., 0]`). The net result is no change.
This logic allows us to update the row in a single pass. We iterate from `left = 0` and `right = n-1` inwards. If `image[row][left] == image[row][right]`, we invert both. If they are different, we do nothing. For rows with an odd number of elements, the middle element (`left == right`) is handled correctly by this logic, as it's compared with itself and gets inverted.

```java
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image[0].length;
        for (int[] row : image) {
            for (int i = 0; i * 2 < n; i++) {
                int j = n - 1 - i;
                // If the bits are different, flip and invert cancel out.
                // e.g., [1, 0] -> flip [0, 1] -> invert [1, 0]. No change.
                // If they are the same, they must be flipped.
                // e.g., [1, 1] -> flip [1, 1] -> invert [0, 0].
                if (row[i] == row[j]) {
                    row[i] = row[j] = row[i] ^ 1;
                }
            }
        }
        return image;
    }
}
```
### Algorithm
- Iterate through each `row` of the `image` matrix.
- Initialize two pointers for the current row: `left = 0` and `right = n - 1`.
- Loop while `left <= right`.
- Inside the loop, compare the values at the pointers: `image[row][left]` and `image[row][right]`.
- If `image[row][left] == image[row][right]`, invert the value at both pointers. (Note: for the middle element where `left == right`, this effectively inverts it once).
- If the values are different, the combined flip-and-invert operation results in no change, so we do nothing.
- Move the pointers inward: `left++`, `right--`.
- After processing all rows, return the modified `image` matrix.

# Solutions
### Java

```java
class Solution {
public
  int[][] flipAndInvertImage(int[][] image) {
    for (var row : image) {
      int i = 0, j = row.length - 1;
      for (; i < j; ++i, --j) {
        if (row[i] == row[j]) {
          row[i] ^= 1;
          row[j] ^= 1;
        }
      }
      if (i == j) {
        row[i] ^= 1;
      }
    }
    return image;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} image * @return {number[][]} */ var flipAndInvertImage =
  function (image) {
    for (const row of image) {
      let i = 0;
      let j = row.length - 1;
      for (; i < j; ++i, --j) {
        if (row[i] == row[j]) {
          row[i] ^= 1;
          row[j] ^= 1;
        }
      }
      if (i == j) {
        row[i] ^= 1;
      }
    }
    return image;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> flipAndInvertImage(vector<vector<int>> &image) {
    for (auto &row : image) {
      int i = 0, j = row.size() - 1;
      for (; i < j; ++i, --j) {
        if (row[i] == row[j]) {
          row[i] ^= 1;
          row[j] ^= 1;
        }
      }
      if (i == j) {
        row[i] ^= 1;
      }
    }
    return image;
  }
};

```

### Python

```python
class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]: n = len(image) for row in image: i, j = 0, n - 1 while i < j: if row[i] == row[j]: row[i] ^= 1 row[j] ^= 1 i, j = i + 1, j - 1 if i == j: row[i] ^= 1 return image

```