Flipping an Image solution and explanation
IBM
Google
9 more videos on this problem
LeetCode Flipping an Image Solution Explained - JavaNick White · 6:52 · 8K views
Flipping an Image | LeetCode 832 | C++, Java, PythonKnowledge Center · 10:01 · 5K views
Flipping an Image | Leet code 832 | Theory explained + Python codeSai Anish Malla · 6:13 · 3K views
Flipping an Image | flipping an image | leetcode 832 | matrixNaresh Gupta · 4:13 · 2K views
832. Flipping an Image | LEETCODE EASY | CODE EXPLAINERcode Explainer · 4:00 · 2K views
Flipping an Image | Live Coding with Explanation | Leetcode #832Algorithms Made Easy · 3:21 · 1K views
Flipping an Image | Leetcode 832 | leetcode solutionEasyLeetcode · 13:56 · 814 views
Leetcode 832 - Flipping An Image (JAVA Solution Explained!)LC Bear · 8:11 · 812 views
LeetCode 832 : Flipping an Image | Solution in JAVAAmit Manjarly · 10:04 · 793 views
Leetcode Flipping ImageJohn Kim · 10:21 · 505 views
The problem
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.lengthn == image[i].length1 <= n <= 20images[i][j]is either0or1.
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.
class Solution:
def flipAndInvertImage(self, image):
for row in image:
start, end = 0, len(row) - 1
while start <= end:
row[start], row[end] = row[end] ^ 1, row[start] ^ 1
start += 1
end -= 1
return image
# Example usage
image = [[1,1,0], [1,0,1], [0,0,0]]
result = Solution().flipAndInvertImage(image)public class Solution {
public int[][] flipAndInvertImage(int[][] image) {
for (int[] row : image) {
int start = 0, end = row.length - 1;
while (start <= end) {
int temp = row[start] ^ 1;
row[start] = row[end] ^ 1;
row[end] = temp;
start++;
end--;
}
}
return image;
}
public static void main(String[] args) {
int[][] image = {{1, 1, 0}, {1, 0, 1}, {0, 0, 0}};
Solution solution = new Solution();
solution.flipAndInvertImage(image);
}
}#include <vector>
using namespace std;
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
for (auto& row : image) {
reverse(row.begin(), row.end());
for (auto& pixel : row) {
pixel ^= 1;
}
}
return image;
}
int main() {
vector<vector<int>> image = {{1, 1, 0}, {1, 0, 1}, {0, 0, 0}};
image = flipAndInvertImage(image);
return 0;
}function flipAndInvertImage(image) {
for (let row of image) {
let start = 0, end = row.length - 1;
while (start <= end) {
[row[start], row[end]] = [row[end] ^ 1, row[start] ^ 1];
start++;
end--;
}
}
return image;
}
// Example usage
let image = [[1,1,0], [1,0,1], [0,0,0]];
console.log(flipAndInvertImage(image));#include <stdio.h>
void flipAndInvertImage(int** image, int imageSize, int* imageColSize){
for (int i = 0; i < imageSize; i++) {
int start = 0, end = imageColSize[i] - 1;
while (start <= end) {
int temp = image[i][start] ^ 1;
image[i][start] = image[i][end] ^ 1;
image[i][end] = temp;
start++;
end--;
}
}
}
int main() {
// Example usage
int image1[3][3] = { {1, 1, 0}, {1, 0, 1}, {0, 0, 0} };
int *imagePtrs1[3] = { image1[0], image1[1], image1[2] };
int imageColSize1[3] = { 3, 3, 3 };
flipAndInvertImage(imagePtrs1, 3, imageColSize1);
return 0;
}public class Solution {
public int[][] FlipAndInvertImage(int[][] image) {
foreach (var row in image) {
int start = 0, end = row.Length - 1;
while (start <= end) {
int temp = row[start] ^ 1;
row[start] = row[end] ^ 1;
row[end] = temp;
start++;
end--;
}
}
return image;
}
static void Main(string[] args) {
int[][] image = new int[][] { new int[] {1, 1, 0}, new int[]{1, 0, 1}, new int[]{0, 0, 0} };
Solution solution = new Solution();
solution.FlipAndInvertImage(image);
}
}The Python solution uses a two-pointer technique to flip and invert each row efficiently. XOR with 1 is used for inversion.
Time Complexity: O(n^2) due to iterating over each element.
Space Complexity: O(1) for in-place operations.
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.
class Solution:
def flipAndInvertImage(self, image):
n = len(image)
for row in image:
for j in range((n + 1) // 2):
if row[j] == row[n - 1 - j]:
row[j] ^= 1
row[n - 1 - j] ^= 1
return image
# Example usage
image = [[1,1,0], [1,0,1], [0,0,0]]
result = Solution().flipAndInvertImage(image)public class Solution {
public int[][] flipAndInvertImage(int[][] image) {
int n = image.length;
for (int[] row : image) {
for (int j = 0; j < (n + 1) / 2; ++j) {
if (row[j] == row[n - 1 - j]) {
row[j] ^= 1;
row[n - 1 - j] ^= 1;
}
}
}
return image;
}
public static void main(String[] args) {
int[][] image = {{1, 1, 0}, {1, 0, 1}, {0, 0, 0}};
Solution solution = new Solution();
solution.flipAndInvertImage(image);
}
}#include <vector>
using namespace std;
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
for (auto& row : image) {
int n = row.size();
for (int j = 0; j < (n + 1) / 2; ++j) {
if (row[j] == row[n - 1 - j]) {
row[j] ^= 1;
row[n - 1 - j] ^= 1;
}
}
}
return image;
}
int main() {
vector<vector<int>> image = {{1, 1, 0}, {1, 0, 1}, {0, 0, 0}};
image = flipAndInvertImage(image);
return 0;
}function flipAndInvertImage(image) {
let n = image.length;
for (let row of image) {
for (let j = 0; j < (n + 1) / 2; ++j) {
if (row[j] === row[n - 1 - j]) {
row[j] ^= 1;
row[n - 1 - j] ^= 1;
}
}
}
return image;
}
// Example usage
let image = [[1,1,0], [1,0,1], [0,0,0]];
console.log(flipAndInvertImage(image));#include <stdio.h>
void flipAndInvertImage(int** image, int imageSize, int* imageColSize) {
for (int i = 0; i < imageSize; i++) {
for (int j = 0; j < (imageColSize[i] + 1) / 2; j++) {
if (image[i][j] == image[i][imageColSize[i] - 1 - j]) {
image[i][j] ^= 1;
image[i][imageColSize[i] - 1 - j] ^= 1;
}
}
}
}
int main() {
// Example usage
int image1[3][3] = { {1, 1, 0}, {1, 0, 1}, {0, 0, 0} };
int *imagePtrs1[3] = { image1[0], image1[1], image1[2] };
int imageColSize1[3] = { 3, 3, 3 };
flipAndInvertImage(imagePtrs1, 3, imageColSize1);
return 0;
}public class Solution {
public int[][] FlipAndInvertImage(int[][] image) {
int n = image.Length;
foreach (var row in image) {
for (int j = 0; j < (n + 1) / 2; ++j) {
if (row[j] == row[n - 1 - j]) {
row[j] ^= 1;
row[n - 1 - j] ^= 1;
}
}
}
return image;
}
static void Main(string[] args) {
int[][] image = new int[][] { new int[] {1, 1, 0}, new int[]{1, 0, 1}, new int[]{0, 0, 0} };
Solution solution = new Solution();
solution.FlipAndInvertImage(image);
}
}In the Python approach, each row is treated using symmetry. If both the mirrored elements are equal, they are inverted using XOR.
Time Complexity: O(n^2), analyzing each symmetry-bound pair.
Space Complexity: O(1) owing to in-place transformation.
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).
func flipAndInvertImage(image [][]int) [][]int {
for _, row := range image {
i, j := 0, len(row)-1
for ; i < j; i, j = i+1, j-1 {
if row[i] == row[j] {
row[i] ^= 1
row[j] ^= 1
}
}
if i == j {
row[i] ^= 1
}
}
return image
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pass Method: Flip then Invert | Time Complexity: O(n^2) due to iterating over each element. |
| Single-Pass Optimization | Time Complexity: O(n^2), analyzing each symmetry-bound pair. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When 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 Optimization | O(n*m) | O(1) | Preferred in interviews or performance-focused code since flip and inversion are combined in one traversal. |
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.