Leetcode 832. Flipping an Image
Problem Explanation:
Given a binary matrix A
, the objective of the problem is to perform two operations on A
:
-
Flip: Reverse each row of the matrix. For example, if a row in the matrix is
[1,1,0]
. After flipping the row, it should become[0,1,1]
. -
Invert: Replace each 0 with 1 and each 1 with 0. Using the previous example, after inverting
0,1,1
, the row should become1,0,0
.
In summary, given a binary matrix, we first flip the matrix horizontally and then invert each element.
Approach for the solution:
The problem can be solved using a nested loop to access each element of the matrix and perform the flip and invert operations. This solution works by iterating over half of each row and swapping the corresponding elements in each row, then inverting the elements (by using Bitwise XOR operation with 1).
For Example,
Let's take A
as [[1,1,0],[1,0,1],[0,0,0]]
. First, we will reverse each row:
- row 1 :
1,1,0
->0,1,1
- row 2 :
1,0,1
->1,0,1
- row 3:
0,0,0
->0,0,0
Then, let's invert the matrix:
- row 1 :
0,1,1
->1,0,0
- row 2 :
1,0,1
->0,1,0
- row 3 :
0,0,0
->1,1,1
Therefore, the output will be [[1,0,0],[0,1,0],[1,1,1]]
.
Python Solution:
Here is the Python solution:
1 2python 3class Solution: 4 def flipAndInvertImage(self, A): 5 n = len(A) 6 7 for i in range(n): 8 # Flip the row 9 A[i] = A[i][::-1] 10 11 # Invert the row 12 for j in range(n): 13 A[i][j] ^= 1 14 15 return A 16 17solution = Solution() 18print(solution.flipAndInvertImage([[1,1,0],[1,0,1],[0,0,0]])) # Returns [[1,0,0],[0,1,0],[1,1,1]]
In the Python solution, we are just using Python list's slicing technique to flip the row and using XOR operation to invert the binary values.
Java Solution:
Here is the Java solution:
1 2java 3class Solution { 4 public int[][] flipAndInvertImage(int[][] A) { 5 int n = A.length; 6 7 for (int i = 0; i < n; i++) { 8 for (int j = 0; j < (n+1)/2; j++) { 9 // temp is used to store to handle the swap and invert at the same time 10 int temp = A[i][j]; 11 A[i][j] = A[i][n-j-1] ^ 1; 12 A[i][n-j-1] = temp ^ 1; 13 } 14 } 15 16 return A; 17 } 18}
In the Java solution, we are traversing just half of each row and swapping the element with its corresponding element from end and while doing this we are also inverting the values. To avoid extra space, we are inverting and swapping the values in place using a temp variable.
Use above explanation and solution code to implement in other languages like JavaScript, C++, and C#.## JavaScript Solution:
Here is the JavaScript solution:
1 2javascript 3function flipAndInvertImage(A) { 4 return A.map((row) => { 5 return row.reverse().map((num) => num === 0 ? 1 : 0); 6 }); 7} 8 9console.log(flipAndInvertImage([[1,1,0],[1,0,1],[0,0,0]])); // Outputs [[1,0,0],[0,1,0],[1,1,1]]
In the JavaScript solution, we are using JavaScript's map function which creates a new array with the results of calling a provided function on every element in the array. The first map assist with reversing each array (i.e. flipping) and the nested map inverts the numbers in the array.
By using built-in JavaScript functions like map and reverse, we can solve the problem with a simple and clean solution.
C++ Solution:
Here is the C++ solution:
1
2c++
3#include <bits/stdc++.h>
4using namespace std;
5
6vector<vector<int> > flipAndInvertImage(vector<vector<int>>& A) {
7 for(int i=0;i<A.size();i++){
8 int start=0;
9 int end=A[i].size()-1;
10 // flipping and inverting the row
11 while(start<=end){
12 swap(A[i][start], A[i][end]);
13 A[i][start]=1-A[i][start];
14 if(start!=end)
15 A[i][end]=1-A[i][end];
16 start++;
17 end--;
18 }
19 }
20 return A;
21 }
This C++ solution flips and inverts each row at the same time, utilizing a swap function inside a while loop. The loop flips and inverts the image until the start index is greater than the end index, doing this for each row in the array. When starting index equals ending index (i.e., we're in the middle of the row), we only apply the inversion operation once, so that same element isn't inverted twice.
C# Solution:
Here is the C# solution:
1 2c# 3public class Solution { 4 public int[][] FlipAndInvertImage(int[][] A) { 5 for (int i = 0; i < A.Length; i++) { 6 for (int j = 0; j < (A[i].Length + 1) / 2; j++) { 7 var temp = A[i][j] ^ 1; 8 A[i][j] = A[i][A[i].Length - j - 1] ^ 1; 9 A[i][A[i].Length - j - 1] = temp; 10 } 11 } 12 return A; 13 } 14}
In this C# solution, we calculate the length of the array and loop through each row. The XOR operator (^) is used to invert the binary numbers. The temp variable is used to swap the numbers to perform the flip and invert operation simultaneously.
These solutions provide efficient approaches to solve the problem of flipping and inverting a given binary matrix in various programming languages like Python, Java, JavaScript, C++, and C#. All solutions use similar logic and vary in syntax and certain built-in functions based on the language used.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.