Flipping an Image
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the first one by eliminating the need for an auxiliary matrix. It modifies the input matrix directly, thus saving space. The operations are still performed in two separate passes: first flipping all rows, then inverting all elements.
Algorithm
- Iterate through each row of the
imagematrix. - For each row, reverse it in-place using two pointers,
leftandright.- Initialize
left = 0,right = n - 1. - While
left < right, swapimage[row][left]withimage[row][right], then incrementleftand decrementright.
- Initialize
- After all rows are flipped, iterate through the entire
imagematrix again. - For each element
image[i][j], update it to its inverted value:image[i][j] = image[i][j] ^ 1. - Return the modified
imagematrix.
Walkthrough
To achieve the result with O(1) extra space, we can modify the input matrix directly. The first pass reverses each row of the image matrix in-place. For each row, we use a two-pointer technique. One pointer starts at the beginning of the row (left) and the other at the end (right). We swap the elements at these pointers and move them towards the center until they meet or cross. The second pass iterates through the now-flipped matrix and inverts every element using the XOR operator (^), which flips a bit (0 becomes 1, 1 becomes 0). The modified input image is then returned.
class Solution { public int[][] flipAndInvertImage(int[][] image) { int n = image.length; // Step 1: Flip each row horizontally in-place for (int i = 0; i < n; i++) { int left = 0; int right = n - 1; while (left < right) { int temp = image[i][left]; image[i][left] = image[i][right]; image[i][right] = temp; left++; right--; } } // Step 2: Invert the image in-place for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { image[i][j] = image[i][j] ^ 1; } } return image; }}Complexity
Time
O(N^2), where N is the dimension of the matrix. The first pass for flipping takes O(N^2) time, and the second pass for inverting also takes O(N^2) time.
Space
O(1), as we modify the matrix in-place and use only a constant amount of extra space for loop variables and temporary storage for swaps.
Trade-offs
Pros
Highly space-efficient, using only constant extra space.
Cons
Requires two passes over the data, which might be slightly less performant than a single-pass solution due to cache effects.
Modifies the input matrix in-place, which might not be desirable in all scenarios.
Solutions
Solution
class Solution {public int[][] flipAndInvertImage(int[][] image) { for (var row : image) { int i = 0, j = row.length - 1; for (; i < j; ++i, --j) { if (row[i] == row[j]) { row[i] ^= 1; row[j] ^= 1; } } if (i == j) { row[i] ^= 1; } } return image; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.