Start by reversing each row with a two-pointer scan, then invert each value in place to achieve the final matrix. This approach avoids extra space and directly manipulates the input, ensuring both flipping and inversion are done in a single pass. Understanding how to track invariants at both ends of each row helps prevent off-by-one errors and ensures correctness.
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.
How GhostInterview Helps
- GhostInterview highlights correct two-pointer scanning patterns and tracks invariant positions in rows.
- The tool flags off-by-one mistakes in middle elements and simultaneous inversion during swaps.
- Provides visual step-through of flip and invert operations to confirm correctness before coding.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Flipping an Image instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Flipping an Image from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Maximize the score of a binary matrix by flipping rows and columns using a greedy approach and validation of invariants.
Open problem page#749 Contain VirusContain Virus involves using array-based Depth-First Search to contain viral spread by building walls around infected regions.
Open problem page#1284 Minimum Number of Flips to Convert Binary Matrix to Zero MatrixCompute the minimum flips to convert a binary matrix to zero by toggling cells and neighbors using array scanning plus hash lookup.
Open problem page