Flipping an Image

Difficulty: Easy | Acceptance: 83.70% | Paid: No Topics: Array, Two Pointers, Bit Manipulation, Matrix, Simulation

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

• Examples
• Constraints
• Approach 1: Brute Force (Reverse then Invert)
• Approach 2: In-Place Two Pointers

Examples

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,1,0],[0,1,0,1],[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,1,0],[0,1,0,1],[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.

Approach 1: Brute Force (Reverse then Invert)

Intuition We can solve this problem by performing the two required operations sequentially. First, we reverse each row of the matrix. Then, we iterate through the matrix again to invert every bit (changing 0 to 1 and 1 to 0).

Steps

• Iterate through each row of the image matrix.
• Reverse the elements of the current row.
• Iterate through each element of the reversed row.
• Invert the element by subtracting it from 1 (or using XOR 1).
• Return the modified image.

class Solution:
    def flipAndInvertImage(self, image: list[list[int]]) -> list[list[int]]:
        for row in image:
            row.reverse()
            for i in range(len(row)):
                row[i] = 1 - row[i]
        return image

Complexity

• Time: O(n²) — We visit every element in the matrix a constant number of times.
• Space: O(1) — We perform operations in-place without allocating extra space proportional to the input size.
• Notes: This approach is straightforward and easy to implement using built-in reverse functions.

Approach 2: In-Place Two Pointers

Intuition We can optimize the process by combining the flipping and inverting steps. Using two pointers, one at the start and one at the end of each row, we can swap elements while simultaneously inverting them. If the pointers meet at the same element (odd length rows), we simply invert that single element.

Steps

• Iterate through each row of the image.
• Initialize two pointers, left at 0 and right at n - 1.
• While left is less than or equal to right:
  • Swap the values at left and right.
  • Invert the value at the new left position.
  • If left is not equal to right, invert the value at the new right position.
  • Move the left pointer forward and the right pointer backward.
• Return the modified image.

class Solution:
    def flipAndInvertImage(self, image: list[list[int]]) -> list[list[int]]:
        n = len(image)
        for row in image:
            left, right = 0, n - 1
            while left <= right:
                if left == right:
                    row[left] = 1 - row[left]
                else:
                    row[left], row[right] = 1 - row[right], 1 - row[left]
                left += 1
                right -= 1
        return image

Complexity

• Time: O(n²) — We traverse each row once, performing constant work per element.
• Space: O(1) — The operation is done in-place.
• Notes: This approach is slightly more efficient in practice as it reduces the number of loop iterations compared to the brute force method.