Flip image

easyFREEImage manipulationLinear AlgebraCV - DSA

Implement a function to manipulate a given $n \times n$ binary image matrix, flipping it horizontally and then inverting it. The goal is to understand how image transformation and binary inversion work together to produce the resulting image. In image processing, flipping an image horizontally involves reversing the order of elements in each row, which can be represented as $[a, b, c]$ becoming $[c, b, a]$ . Inverting replaces every $0$ with $1$ and every $1$ with $0$ :

\begin{aligned} f(x) &= 1 - x \end{aligned}

This technique is widely used in data augmentation for training machine learning models.

Example

Input

image = [[1,1,0],[1,0,1],[0,0,0]]

Output

[[1,0,0],[0,1,0],[1,1,1]]

Reasoning

image is a $3 \times 3$ binary picture: row $i$ , column $j$ holds pixel $x_{ij}$ , where $1$ is a lit pixel and $0$ is a dark one.
A horizontal flip mirrors the picture left to right, so column $j$ of the result takes the pixel from column $n-1-j$ . Row [1,1,0] becomes $[0,1,1]$ , row [1,0,1] is a palindrome and stays $[1,0,1]$ , and the all-dark row $[0,0,0]$ is unchanged.
Inverting applies $f(x) = 1 - x$ to every pixel: $[0,1,1] \to [1,0,0]$ , $[1,0,1] \to [0,1,0]$ , $[0,0,0] \to [1,1,1]$ .
Combined, each output pixel is $o_{ij} = 1 - x_{i,\,n-1-j}$ , giving [[1,0,0],[0,1,0],[1,1,1]]: still $3 \times 3$ , still only $0$ s and $1$ s.
Notice that rows never move up or down, only within themselves. Since the flip moves pixels and the inversion changes values independently, doing them in the other order gives the same picture.

Constraints

n == image.length n == image[i].length 1 <= n <= 20

More from CV - DSA

Concept primer

Flip Image: Comprehensive Background and Solution Guide

Background Knowledge

This problem involves fundamental binary image processing operations. Binary images, which contain only two values (0 and 1), are widely used in computer vision, document analysis, and image recognition tasks.

Key Concepts

Binary Matrix Representation A binary matrix is a 2D array where each element is either 0 or 1. In image processing contexts:

0 typically represents background or "off" pixels
1 typically represents foreground or "on" pixels

Horizontal Flip (Reversal) Reversing each row means reading the row from right to left instead of left to right. For a row of length n, element at index i moves to index n-1-i.

Inversion (Bitwise NOT) Inversion is a bitwise operation where each bit is flipped:

0 → 1
1 → 0

This operation is fundamental in binary image processing and is used in various applications including malware detection and document analysis.

Why This Matters

Binary image operations are essential preprocessing steps in document analysis, character recognition, and image retrieval systems. Understanding efficient manipulation of binary data is crucial for resource-constrained environments.

Algorithm Approach

Two-Phase Strategy

The problem requires two sequential operations:

Phase 1: Horizontal Flip - Reverse each row
Phase 2: Inversion - Flip each bit (0↔1)

Naive Approach

def flipAndInvertImage(image):
 n = len(image)
 # Phase 1: Flip horizontally
 for i in range(n):
 image[i] = image[i][::-1]

 # Phase 2: Invert
 for i in range(n):
 for j in range(n):
 image[i][j] = 1 - image[i][j]

 return image

Optimized Approach (Single Pass)

Combine both operations in a single pass to improve cache locality and reduce iterations:

def flipAndInvertImage(image):
 n = len(image)
 for i in range(n):
 # Reverse and invert simultaneously
 left, right = 0, n - 1
 while left <= right:
 # Flip horizontally and invert in one step
 image[i][left], image[i][right] = 1 - image[i][right], 1 - image[i][left]
 left += 1
 right -= 1

 return image

Step-by-Step Strategy

Step 1: Understand the Input

Verify the matrix is n×n where 1 ≤ n ≤ 20
Confirm all elements are binary (0 or 1)

Step 2: Choose Your Approach

For this problem size (n ≤ 20), both naive and optimized approaches work well. The optimized approach is preferable for demonstrating algorithmic thinking.

Step 3: Implement Horizontal Flip

Use two pointers (left and right) starting from opposite ends of each row:

Swap elements at positions left and right
Move pointers toward the center

Step 4: Implement Inversion

For each swapped element, apply the inversion: new_value = 1 - old_value

Step 5: Verify with Examples

Input: [[1,1,0],
 [1,0,1],
 0,1,1]]

After flip: [[0,1,1],
 [1,0,1],
 [1,1,0]]

After invert: [[1,0,0],
 [0,1,0],
 [0,0,1]]

Common Pitfalls

Pitfall	Issue	Solution
Off-by-one errors	Incorrect loop bounds or pointer positions	Use left <= right condition; verify with small examples
Modifying while iterating	Changing array during iteration causes issues	Use two-pointer technique or create new array
Forgetting inversion	Only flipping without inverting	Combine both operations or ensure both phases execute
Incorrect inversion logic	Using wrong formula (e.g., image[i][j] = image[i][j] ^ 1 vs 1 - image[i][j])	Both work; 1 - x is more readable for binary values
Not handling edge cases	n=1 (single element) or all 0s/1s	Test boundary cases explicitly

Time & Space Complexity

Time Complexity: $O(n^2)$

Must visit each element in the n×n matrix at least once
Two-pointer approach: $n/2$ operations per row × n rows = $O(n^2)$
Cannot be improved below this since output size is $O(n^2)$

Space Complexity: $O(1)$ or $O(n^2)$

In-place modification: $O(1)$ auxiliary space (excluding output)
Creating new matrix: $O(n^2)$ space for result

Optimization Notes

The optimized single-pass approach reduces constant factors:

Naive approach: 2 full passes through the matrix
Optimized approach: 1 pass with combined operations
Practical impact: ~2x faster for large n, though both are $O(n^2)$

Implementation Comparison

Approach	Time	Space	Readability	Best For
Naive (separate phases)	O(n²)	O(1)	High	Learning, clarity
Two-pointer (combined)	O(n²)	O(1)	Medium	Interviews, optimization
Functional (list comprehension)	O(n²)	O(n²)	High	Pythonic style

The two-pointer approach is recommended for technical interviews as it demonstrates understanding of in-place algorithms and optimization techniques.

solution.py

Python 3.13

Test results