Flipping an Image LeetCode Solution

Difficulty Level Easy
Frequently asked in Facebook Google YahooViews 4607

Problem Statement

Flipping an Image LeetCode Solution – We are given a matrix of size n. We need to perform 2 tasks-

  1. flip the image horizontally: it means each row of the given matrix is reversed
  2. invert the image: make all 0’s to 1’s & vice versa

Return the resulting matrix.

Given matrix contains only 0 or 1 and size of image is ≤ 20.

Examples & Explanations

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]]

Approach

After reviewing some examples you will notice the following patterns:
1) Look at the first and last value of the row. If they are the same (1,1 or 0,0), they will be flipped in the output.
If they are different (1,0 or 0,1), they do not change. Work your way inward to the middle of the list
applying this rule.
2) If the row has an odd number of entries, the middle value always flips. For example if len(row) = 5,
then row[2] must change values.

Bitwise XOR –> 0^1 = 1, 1^1 =0

Let i be the index at the beginning of the row, and j be the index at the end of the row. If the values at
these indices (row[i] and row[j]) are equal, flip their values using XOR ^. If the values are not equal, do
nothing and move i and j closer to the middle. When i == j , the code still executes as it should.

The question has 2 parts-

  1. Flipping the image: we can simply use another array or vector to store matrix[i] and reverse it for all rows and store the answer in another matrix res
  2. Inverting the image: this is an easy task, simply check the value of res[i][j] and change the value

This approach requires us to declare another matrix of size n x n. Can we do better?

We can achieve flipping in place by swapping the elements by pivoting the middle element of every row in the image. For each row, keep the middle element in place and swap the ith element with the (n-1-i)th element. We will use XOR to invert the elements.

We know that 1^1 = 0 & 1^0 = 1

Code

C++ code for Flipping an Image

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
        int n = image.size();
        for(auto &row: image) {
            for(int i=0; i<(n+1)/2; i++) {
                int temp = row[i];
                row[i] = row[n-1-i]^1;
                row[n-1-i] = temp^1;
            }
        }
        return image;
    }
};

Java code for Flipping an Image

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int n = A.length;
        for(int[] row: A) {
            for(int i=0; i< (n+1)/2; i++) {
                int temp = row[i];
                row[i] = row[n-1-i]^1;
                row[n-1-i] = temp^1;
            }
        }
        return A;
    }
}

Time Complexity for Flipping an Image LeetCode Solution:

Translate »