Skip to main content
Talentd

Flipping an Image - Solution & Explanation

EasyArrayTwo PointersBit ManipulationMatrix14 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a binary matrix. For every row, first flip it horizontally (reverse the row), then invert each bit (0 becomes 1 and 1 becomes 0). The goal is to transform the image in-place and return the updated matrix.

Approach 1: Two-Pass Method - Flip then Invert (Time: O(n*m), Space: O(1))

The straightforward approach performs the two required operations separately. First iterate through each row of the array and reverse it using two pointers from both ends. This horizontal flip swaps row[left] with row[right] until the pointers meet. After the row is reversed, iterate through it again and invert every bit using bit = 1 - bit or a conditional toggle.

This method is easy to reason about because it mirrors the problem statement exactly: flip first, then invert. Each cell is processed twice—once during the reversal and once during inversion—resulting in O(n*m) time complexity for an n by m matrix. Space complexity remains O(1) because the transformation happens in-place.

Approach 2: Single-Pass Optimization (Time: O(n*m), Space: O(1))

The optimized approach combines the flip and invert steps into a single pass. Use the two pointers technique on each row. While swapping elements from both ends, invert them at the same time. When swapping row[left] and row[right], assign the inverted values directly using a bit manipulation trick such as value ^ 1 to toggle the bit.

If both elements are the same, the swap would normally leave them unchanged after inversion. Handling the inversion during the swap avoids doing a second pass. For odd-length rows, the middle element just needs a single inversion when left == right.

This approach still processes each cell once, giving O(n*m) time complexity, but it reduces redundant work and keeps the implementation concise. The matrix is updated in-place, so the space complexity stays O(1).

Recommended for interviews: Interviewers typically expect the single-pass solution. The two-pass method demonstrates that you understand the problem transformation clearly, but combining the operations using two pointers and bit inversion shows stronger algorithmic thinking and optimization skills.

Approach 1: Two-Pass Method: Flip then Invert

This approach involves two distinct passes over the matrix: first to flip each row horizontally by reversing the elements, and second to invert all the elements by replacing 0s with 1s and vice versa.

This C solution uses a two-pointer technique to simultaneously flip and invert each row of the binary matrix. Using XOR with 1 inverts each bit.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) as each element is visited once.
Space Complexity: O(1) as no additional space proportional to input size is used.

Try this approach in the editor →

Approach 2: Single-Pass Optimization

This approach attempts to combine the flipping and inverting processes in one pass to enhance efficiency, leveraging the symmetry characteristics of the problem.

This C solution performs operations on symmetry pairs. When both elements in a pair are equal, they are inverted together, optimizing for fewer operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) given each element may potentially be processed.
Space Complexity: O(1) since modifications are in place.

Try this approach in the editor →

Approach 3: Two Pointers

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

Finally, if i = j, we directly invert row[i].

The time complexity is O(n^2), where n is the number of rows or columns in the matrix. The space complexity is O(1).

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pass Method: Flip then Invert

Time Complexity: O(n^2) as each element is visited once.
Space Complexity: O(1) as no additional space proportional to input size is used.

Single-Pass Optimization

Time Complexity: O(n^2) given each element may potentially be processed.
Space Complexity: O(1) since modifications are in place.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass Method (Flip then Invert)O(n*m)O(1)Best for clarity and step-by-step implementation that directly follows the problem statement.
Single-Pass OptimizationO(n*m)O(1)Preferred in interviews or performance-focused code since flip and inversion are combined in one traversal.

Video Solution

LeetCode Flipping an Image Solution Explained - Java • Nick White • 8,454 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Flipping an Image easy or hard?
Flipping an Image is classified as an Easy problem on LeetCode. The challenge mainly tests understanding of array traversal, matrix manipulation, and basic two-pointer optimization.
How to solve Flipping an Image in O(n*m)?
Iterate through each row and use two pointers starting at the left and right ends. Swap the elements while simultaneously inverting them using a bit toggle like value XOR 1. Continue until the pointers meet, handling the middle element separately if the row length is odd.
Flipping an Image Python or Java solution?
In Python or Java, iterate through each row and use two pointers to swap elements while applying an inversion operation such as value ^ 1 or 1 - value. This performs the horizontal flip and bit inversion in one pass with constant extra space.
What is the best approach for Flipping an Image?
The single-pass two-pointer approach is the best solution. It flips each row and inverts bits at the same time while traversing from both ends toward the center. This avoids a second traversal and still runs in O(n*m) time with O(1) extra space.
What data structure is used in Flipping an Image?
The problem operates directly on a 2D array (matrix). The algorithm relies on array traversal and the two-pointer technique, along with simple bit manipulation to invert binary values efficiently.
What is the time complexity of Flipping an Image?
Both common approaches run in O(n*m) time where n is the number of rows and m is the number of columns. Every cell in the matrix must be visited at least once. The optimized method performs flip and inversion together but still processes each element only once.
Is Flipping an Image asked at Google, Amazon, or Meta?
Flipping an Image is a common easy-level array and matrix problem used in coding interviews and online assessments. Variations involving matrix transformations, bit inversion, or two-pointer row operations appear at companies like Amazon, Google, and Meta.

Ready to solve this problem?

Practice Flipping an Image with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays