Skip to content

832. Flipping an Image

Description

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.

Solutions

Solution 1: Two Pointers

Thinking

Each row is reversed then inverted. \(n\le 20\), so two pointers can do both steps in place.

Equal ends stay equal after reverse, so both bits flip. Unequal ends swap under reverse-and-invert, so they need no write. A middle cell is inverted alone.

We can traverse the matrix, and for each row \(\textit{row}\), we use two pointers \(i\) and \(j\) pointing to the first and last elements of the row, respectively. If \(\textit{row}[i] = \textit{row}[j]\), swapping them will keep their values unchanged, so we only need to XOR invert \(\textit{row}[i]\) and \(\textit{row}[j]\), then move \(i\) and \(j\) one position towards the center until \(i \geq j\). If \(\textit{row}[i] \neq \textit{row}[j]\), swapping and then inverting their values will also keep them unchanged, so no operation is needed.

Finally, if \(i = j\), we directly invert \(\textit{row}[i]\).

The time complexity is \(O(n^2)\), where \(n\) is the number of rows or columns in the matrix. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func flipAndInvertImage(image [][]int) [][]int {
    for _, row := range image {
        i, j := 0, len(row)-1
        for ; i < j; i, j = i+1, j-1 {
            if row[i] == row[j] {
                row[i] ^= 1
                row[j] ^= 1
            }
        }
        if i == j {
            row[i] ^= 1
        }
    }
    return image
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @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;
};

Comments