{x}
blog image

Flipping an Image

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.

Solution Explanation for Flipping an Image

This problem requires flipping a binary matrix horizontally and then inverting it. Let's break down the optimal solution and its complexity analysis.

Approach: In-place Two-Pointer Swapping and Inversion

The most efficient approach involves using two pointers for each row and performing both operations (flipping and inverting) simultaneously in-place. This avoids creating extra arrays, optimizing space usage.

Steps:

  1. Iterate through rows: The outer loop iterates through each row of the input image.

  2. Two-pointer swapping and inversion: For each row, we use two pointers, i (starting at the beginning of the row) and j (starting at the end of the row). We perform the following in each inner loop iteration:

    • Compare row[i] and row[j]: If they are equal, swapping them wouldn't change their values. We simply invert both using the XOR operator (^= 1). This toggles 0 to 1 and 1 to 0.

    • If row[i] and row[j] are different: Swapping and inverting wouldn't change their values; hence no operation is needed.

    • Move pointers: Increment i and decrement j to move towards the center of the row.

  3. Handle middle element (odd length rows): If the row has an odd number of elements, after the loop, i and j will be equal, pointing to the middle element. We invert this middle element using row[i] ^= 1;

Why XOR is efficient: Using the XOR operator (^) for inversion is concise and efficient. x ^= 1 is equivalent to x = 1 - x but is faster.

Code Examples (Python, Java, C++, Go, JavaScript)

The provided code examples demonstrate this approach. All examples follow the same logic with minor syntax differences based on the programming language. Note that the code modifies the input matrix directly, performing the operation in-place.

Time and Space Complexity Analysis

  • Time Complexity: O(n*m), where n is the number of rows and m is the number of columns in the matrix. We iterate through each element of the matrix once. In the case of a square matrix, this simplifies to O(n²).

  • Space Complexity: O(1). The algorithm operates in-place; we don't use any extra space that scales with the input size. The space used is constant regardless of the size of the input matrix.