#832

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Flipping an Image

Flip each row of a binary matrix horizontally and invert its values efficiently using a two-pointer scanning approach.

array two pointers bit manipulation matrix simulation

Problem Statement

You are given an n x n binary matrix representing an image. The task is to flip the image horizontally, meaning each row should be reversed, and then invert the image so that every 0 becomes 1 and every 1 becomes 0.

Implement a function that performs both the horizontal flip and inversion in place. The solution should efficiently handle all rows with a two-pointer scanning strategy, tracking invariants to avoid common off-by-one mistakes and unnecessary extra space.

Examples

Example 1

Input: image = [[1,1,0],[1,0,1],[0,0,0]]

Output: [[1,0,0],[0,1,0],[1,1,1]]

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

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 Approach

Two-pointer horizontal flip

Initialize two pointers at the start and end of each row. Swap the values while moving pointers toward the center. This ensures a full horizontal flip in a single linear pass per row without extra storage.

In-place inversion during scanning

While swapping elements with two pointers, invert the values simultaneously by replacing 0 with 1 and 1 with 0. This merges both operations into a single loop, saving time and space.

Handle middle element in odd-length rows

For rows with an odd number of elements, after swapping pairs, invert the central element separately. Tracking invariants prevents skipping or double-inverting this middle value.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N^2) because each of the N rows of length N is scanned once. Space complexity is O(1) since all operations are performed in place with no extra storage.

What Interviewers Usually Probe

Check if the candidate correctly flips rows without using extra arrays.
Watch whether inversion is combined with swapping or done in a separate pass.
Confirm that middle elements in odd-length rows are handled without errors.

Common Pitfalls or Variants

Common pitfalls

Swapping values without inverting them at the same time causes incorrect final results.
Off-by-one errors when moving two pointers can skip elements or double-invert.
Failing to handle odd-length rows' middle element separately leads to wrong inversion.

Follow-up variants

Apply the same two-pointer flip and invert approach on a rectangular matrix instead of a square one.
Perform horizontal flip only, without inversion, to isolate the flipping logic.
Invert all elements without flipping to practice bit manipulation in place.

FAQ

What is the main idea behind the Flipping an Image problem?

The main idea is to flip each row horizontally using two pointers and then invert each element in place for efficiency.

Can this be done without extra space?

Yes, by scanning each row with two pointers and performing swaps and inversion simultaneously, no additional storage is needed.

How do I handle odd-length rows?

After swapping pairs with two pointers, invert the central element separately to ensure correctness.

Why use two-pointer scanning instead of built-in functions?

Two-pointer scanning allows in-place operations, combines flipping and inversion, and demonstrates clear algorithmic control for interviews.

What common mistakes should I avoid?

Avoid skipping middle elements, double-inverting values, or using extra arrays unnecessarily. Track pointers carefully for correctness.

terminal

Solution

Solution 1: Two Pointers

We can traverse the matrix, and for each row $\textit{row}$, we use two pointers $i$ and $j$ pointing to the first and last elements of the row, respectively. If $\textit{row}[i] = \textit{row}[j]$, swapping them will keep their values unchanged, so we only need to XOR invert $\textit{row}[i]$ and $\textit{row}[j]$, then move $i$ and $j$ one position towards the center until $i \geq j$. If $\textit{row}[i] \neq \textit{row}[j]$, swapping and then inverting their values will also keep them unchanged, so no operation is needed.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        n = len(image)
        for row in image:
            i, j = 0, n - 1
            while i < j:
                if row[i] == row[j]:
                    row[i] ^= 1
                    row[j] ^= 1
                i, j = i + 1, j - 1
            if i == j:
                row[i] ^= 1
        return image

Continue Practicing

#861 score after flipping matrix #749 contain virus #1284 minimum number of flips to convert binary matrix to zero matrix