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.
[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.
[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 either 0 or 1.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.
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.
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.
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.
Time Complexity: O(n^2) given each element may potentially be processed.
Space Complexity: O(1) since modifications are in place.
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).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Two-Pass Method: Flip then Invert | Time Complexity: O(n^2) as each element is visited once. |
| Single-Pass Optimization | Time Complexity: O(n^2) given each element may potentially be processed. |
| Two Pointers | — |
| 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. |
Flipping an Image | LeetCode 832 | C++, Java, Python • Knowledge Center • 5,026 views views
Watch 9 more video solutions →Practice Flipping an Image with our built-in code editor and test cases.
Practice on FleetCode