Flipping an Image

EASY

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.

Approaches

Checkout 3 different approaches to solve Flipping an Image. Click on different approaches to view the approach and algorithm in detail.

Two-Pass In-place Approach

This approach improves upon the first one by eliminating the need for an auxiliary matrix. It modifies the input matrix directly, thus saving space. The operations are still performed in two separate passes: first flipping all rows, then inverting all elements.

Algorithm

Iterate through each row of the image matrix.
For each row, reverse it in-place using two pointers, left and right.
- Initialize left = 0, right = n - 1.
- While left < right, swap image[row][left] with image[row][right], then increment left and decrement right.
After all rows are flipped, iterate through the entire image matrix again.
For each element image[i][j], update it to its inverted value: image[i][j] = image[i][j] ^ 1.
Return the modified image matrix.

To achieve the result with O(1) extra space, we can modify the input matrix directly. The first pass reverses each row of the image matrix in-place. For each row, we use a two-pointer technique. One pointer starts at the beginning of the row (left) and the other at the end (right). We swap the elements at these pointers and move them towards the center until they meet or cross. The second pass iterates through the now-flipped matrix and inverts every element using the XOR operator (^), which flips a bit (0 becomes 1, 1 becomes 0). The modified input image is then returned.

class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;

        // Step 1: Flip each row horizontally in-place
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = image[i][left];
                image[i][left] = image[i][right];
                image[i][right] = temp;
                left++;
                right--;
            }
        }

        // Step 2: Invert the image in-place
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                image[i][j] = image[i][j] ^ 1;
            }
        }

        return image;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the dimension of the matrix. The first pass for flipping takes O(N^2) time, and the second pass for inverting also takes O(N^2) time.Space Complexity: O(1), as we modify the matrix in-place and use only a constant amount of extra space for loop variables and temporary storage for swaps.

Pros and Cons

Pros:

Highly space-efficient, using only constant extra space.

Cons:

Requires two passes over the data, which might be slightly less performant than a single-pass solution due to cache effects.
Modifies the input matrix in-place, which might not be desirable in all scenarios.

Code Solutions

Checking out 4 solutions in different languages for Flipping an Image. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Flipping an Image

Patterns:

Two PointersBit Manipulation

Data Structures:

ArrayMatrix

Companies:

IBM |