Given a binary matrix. The task is to flip the matrix horizontally(find the image of the matrix), then invert it.
Note:
- To flip a matrix horizontally means reversing each row of the matrix. For example, flipping [1, 1, 0, 0] horizontally results in [0, 0, 1, 1].
- To invert a matrix means replacing each 0 by 1 and vice-versa. For example, inverting [0, 0, 1] results in [1, 1, 0].
Examples:
Input: mat[][] = [[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]]
Input: mat[][] = [[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]]
Approach: We can do this in place. On observing carefully, it can be deduced that in each row in the final matrix, the i-th value from the left is equal to the inverse of the i-th value from the right of the input binary matrix. Thus, we use (Column + 1) / 2 (with floor division) to iterate over all indexes
in the first half of the row, including the centre and updating the answer accordingly.
Below is the implementation of the above approach:
C++14
// c++ implementation of above approach
// Function to return final Image
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> flipped_Invert_Image(vector<vector<int>>& mat){
vector<vector<int>> ans;
for(auto row : mat){
for(int i=0;i<=(mat[0].size() + 1) / 2;i++){
row[i] = row[row.size() - 1 - i] ^ 1;
row[row.size() - 1 - i] = row[i] ^ 1;
}
ans.push_back(row);
}
// return Flipped and Inverted image
return ans;
}
// Driver code
int main(){
vector<vector<int>> mat = {{1, 1, 0, 0}, {1, 0, 0, 1}, {0, 1, 1, 1}, {1, 0, 1, 0}};
vector<vector<int>> ans = flipped_Invert_Image(mat);
for(int i=0; i<ans.size(); i++)
{
for(int j=0; j<ans[0].size(); j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
}
Java
// java implementation of above approach
// Function to return final Image
import java.io.*;
import java.util.Arrays;
class GFG {
public static void main(String[] args)
{
// Driver code
int[][] mat = { { 1, 1, 0, 0 },
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 } };
int[][] matrix = flipped_Invert_Image(mat);
for (int[] matele : matrix) {
System.out.print(Arrays.toString(matele));
}
}
public static int[][] flipped_Invert_Image(int[][] mat)
{
for (int[] row : mat) {
for (int i = 0; i < (mat[0].length + 1) / 2; i++)
{
// swap
int temp = row[i] ^ 1;
row[i] = row[(mat[0].length - 1 - i)] ^ 1;
row[(mat[0].length - 1 - i)] = temp;
}
}
// return Flipped and Inverted image
return mat;
}
}
// This code is contributed by devendra salunke
Python3
# Python3 implementation of above approach
# Function to return final Image
def flipped_Invert_Image(mat):
for row in mat:
for i in range((len(row) + 1) // 2):
row[i] = row[len(row) - 1 - i] ^ 1
row[len(row) - 1 - i] = row[i] ^ 1
# return Flipped and Inverted image
return mat
# Driver code
mat = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0]]
print(flipped_Invert_Image(mat))
C#
// C# implementation of above approach
// Function to return final Image
using System;
using System.Collections.Generic;
public class GFG {
public static int[, ] flipped_Invert_Image(int[, ] mat)
{
for (int j = 0; j < mat.GetLength(0); j++) {
for (int i = 0; i < (mat.GetLength(1) + 1) / 2;
i++) {
// swap
int temp = mat[j, i] ^ 1;
mat[j, i]
= mat[j, mat.GetLength(1) - 1 - i] ^ 1;
mat[j, mat.GetLength(1) - 1 - i] = temp;
}
}
return mat;
}
public static void Main(string[] args)
{
// Driver code
int[, ] mat = { { 1, 1, 0, 0 },
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 } };
int[, ] matrix = flipped_Invert_Image(mat);
//Printing the formatted array
Console.Write("[");
for (int j = 0; j < matrix.GetLength(0); j++) {
Console.Write("[");
for (int i = 0; i < matrix.GetLength(1); i++) {
Console.Write(matrix[j, i]);
if (i != matrix.GetLength(1) - 1)
Console.Write(", ");
}
Console.Write("]");
if (j != matrix.GetLength(0) - 1)
Console.Write(", ");
}
Console.Write("]");
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript implementation of above approach
// Function to return final Image
function flipped_Invert_Image(mat){
for(let row of mat){
for(let i=0;i<Math.floor((row.length + 1) / 2);i++){
row[i] = row[row.length - 1 - i] ^ 1
row[row.length - 1 - i] = row[i] ^ 1
}
}
// return Flipped and Inverted image
return mat
}
// Driver code
let mat = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0]]
document.write(flipped_Invert_Image(mat))
// This code is contributed by shinjanpatra
</script>
Output
[[1, 1, 0, 0], [0, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 0]]
Time Complexity: O(N*M), where N is the number of rows and M is the number of columns in the given binary matrix.
Auxiliary Space: O(1), since no extra space has been taken.
C++14
//c++ program to flip the binary image horizontally
#include<bits/stdc++.h>
using namespace std;
//function to flip the matrix using two pointer technique
vector<vector<int>> flip_matrix(vector<vector<int>>matrix)
{
for(int i=0;i<matrix.size();i++)
{
int left = 0;
int right = matrix[i].size()-1;
while( left <= right )
{
//conditions executes if compared elements are not equal
if(matrix[i][left] == matrix[i][right])
{
// if element is 0 it becomes 1 if not it becomes 0
matrix[i][left] = 1-matrix[i][left];
matrix[i][right] = matrix[i][left];
}
left++;
right--;
}
}
//return matrix
return matrix;
}
//Drive code
int main()
{
vector<vector<int>>matrix={{1,1,0},{1,0,1},{0,0,0}};
vector<vector<int>>v=flip_matrix(matrix);
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[i].size();j++)
{
cout<<v[i][j]<<" ";
}
cout<<'\n';
}
}
Java
// Java program to flip the binary image horizontally
import java.io.*;
class GFG {
public static void main(String[] args)
{
int[][] matrix
= { { 1, 1, 0 }, { 1, 0, 1 }, { 0, 0, 0 } };
int[][] v = flip_matrix(matrix);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
}
// function to flip the matrix using two pointer
// technique
public static int[][] flip_matrix(int[][] matrix)
{
for (int i = 0; i < matrix.length; i++) {
int left = 0;
int right = matrix[i].length - 1;
while (left <= right) {
// conditions executes if compared elements
// are not equal
if (matrix[i][left] == matrix[i][right]) {
// if element is 0 it becomes 1 if not
// it becomes 0
matrix[i][left] = 1 - matrix[i][left];
matrix[i][right] = matrix[i][left];
}
left++;
right--;
}
}
// return matrix
return matrix;
}
}
// This code is contributed by devendra salunke
Python3
# Python program to flip the binary image horizontally
# function to flip the matrix using two pointer technique
def flip_matrix(matrix):
for i in range(len(matrix)):
left,right = 0,len(matrix[i])-1
while(left <= right):
# conditions executes if compared elements are not equal
if(matrix[i][left] == matrix[i][right]):
# if element is 0 it becomes 1 if not it becomes 0
matrix[i][left] = 1-matrix[i][left]
matrix[i][right] = matrix[i][left]
left += 1
right -= 1
# return matrix
return matrix
# Drive code
matrix = [[1, 1, 0], [1, 0, 1], [0, 0, 0]]
v = flip_matrix(matrix)
for i in range(len(matrix)):
for j in range(len(matrix[i])):
print(v[i][j],end = " ")
print()
# This code is contributed by shinjanpatra
C#
// C# program to flip the binary image horizontally
using System;
class GFG {
// Driver code
public static void Main(string[] args)
{
int[][] matrix
= { new[] { 1, 1, 0 }, new[] { 1, 0, 1 },
new[] { 0, 0, 0 } };
int[][] v = flip_matrix(matrix);
for (int i = 0; i < matrix.Length; i++) {
for (int j = 0; j < matrix[i].Length; j++) {
Console.Write(v[i][j] + " ");
}
Console.WriteLine();
}
}
// function to flip the matrix using two pointer
// technique
public static int[][] flip_matrix(int[][] matrix)
{
for (int i = 0; i < matrix.Length; i++) {
int left = 0;
int right = matrix[i].Length - 1;
while (left <= right) {
// conditions executes if compared elements
// are not equal
if (matrix[i][left] == matrix[i][right]) {
// if element is 0 it becomes 1 if not
// it becomes 0
matrix[i][left] = 1 - matrix[i][left];
matrix[i][right] = matrix[i][left];
}
left++;
right--;
}
}
// return matrix
return matrix;
}
}
// This code is contributed by devendra salunke
Javascript
<script>
// JavaScript implementation of above approach
// function to flip the matrix using two pointer technique
function flip_matrix(matrix)
{
for(let i = 0; i < matrix.length; i++)
{
let left = 0;
let right = matrix[i].length-1;
while( left <= right )
{
// conditions executes if compared elements are not equal
if(matrix[i][left] == matrix[i][right])
{
// if element is 0 it becomes 1 if not it becomes 0
matrix[i][left] = 1-matrix[i][left];
matrix[i][right] = matrix[i][left];
}
left++;
right--;
}
}
// return matrix
return matrix;
}
// Drive code
let matrix = [[1,1,0],[1,0,1],[0,0,0]];
let v = flip_matrix(matrix);
for(let i = 0 ; i < matrix.length; i++)
{
for(let j = 0; j < matrix[i].length; j++)
{
document.write(v[i][j]," ");
}
document.write("</br>");
}
// This code is contributed by shinjanpatra
</script>
Output
1 0 0 0 1 0 1 1 1
Time Complexity: O(N*M) where N and M are the dimensions of the matrix.,
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!
- DSA in C++
- DSA in Java
- DSA in Python
- DSA in JavaScript
Commit to GfG's Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.
Last Updated : 07 Jan, 2024
Like Article
Save Article
Previous
Check if a number can be expressed as a sum of consecutive numbers
Next
Sum and product of k smallest and k largest composite numbers in the array
Share your thoughts in the comments
