LeetCode 0832. Flipping an Image Solution in Java, C++, Python & More | Explanation + Code

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

We can traverse the matrix, and for each row row, we use two pointers i and j pointing to the first and last elements of the row, respectively. If row[i] = row[j], swapping them will keep their values unchanged, so we only need to XOR invert row[i] and row[j], then move i and j one position towards the center until i ≥ j. If row[i] ≠ 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 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).

PythonJavaC++GoJavaScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

/** * @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; };(code-box)