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.
This is the most efficient approach. It combines the flipping and inverting operations into a single pass for each row. By analyzing the combined effect of the two operations, we can derive a more direct transformation that is both time and space optimal.
Algorithm
- Iterate through each
rowof theimagematrix. - Initialize two pointers for the current row:
left = 0andright = n - 1. - Loop while
left <= right. - Inside the loop, compare the values at the pointers:
image[row][left]andimage[row][right]. - If
image[row][left] == image[row][right], invert the value at both pointers. (Note: for the middle element whereleft == right, this effectively inverts it once). - If the values are different, the combined flip-and-invert operation results in no change, so we do nothing.
- Move the pointers inward:
left++,right--. - After processing all rows, return the modified
imagematrix.
Walkthrough
We can process each row in a single pass using two pointers, left and right, moving from the ends towards the center. For each pair of elements image[row][left] and image[row][right], we need to swap them and then invert them. A key observation simplifies this:
- If
image[row][left]andimage[row][right]are the same (e.g.,[1, ..., 1]), flipping doesn't change their values relative to each other. Inverting them changes both (e.g., to[0, ..., 0]). - If
image[row][left]andimage[row][right]are different (e.g.,[1, ..., 0]), flipping swaps them (to[0, ..., 1]), and inverting swaps them back (to[1, ..., 0]). The net result is no change. This logic allows us to update the row in a single pass. We iterate fromleft = 0andright = n-1inwards. Ifimage[row][left] == image[row][right], we invert both. If they are different, we do nothing. For rows with an odd number of elements, the middle element (left == right) is handled correctly by this logic, as it's compared with itself and gets inverted.
class Solution { public int[][] flipAndInvertImage(int[][] image) { int n = image[0].length; for (int[] row : image) { for (int i = 0; i * 2 < n; i++) { int j = n - 1 - i; // If the bits are different, flip and invert cancel out. // e.g., [1, 0] -> flip [0, 1] -> invert [1, 0]. No change. // If they are the same, they must be flipped. // e.g., [1, 1] -> flip [1, 1] -> invert [0, 0]. if (row[i] == row[j]) { row[i] = row[j] = row[i] ^ 1; } } } return image; }}Complexity
Time
O(N^2), where N is the dimension of the matrix. We iterate through each row, and for each row, we process up to its midpoint. This results in visiting each element effectively once.
Space
O(1), as all modifications are done in-place.
Trade-offs
Pros
Most efficient in both time and space.
Combines operations into a single pass, which is elegant and can be faster in practice due to better data locality.
Cons
The logic is slightly more complex to derive than the straightforward two-pass approach.
Modifies the input matrix in-place.
This approach strictly follows the problem description by performing the two operations, horizontal flipping and inverting, in two separate steps. It uses an auxiliary matrix to store the result, leaving the original matrix unchanged.
Algorithm
- Initialize a new
n x ninteger matrixresult. - Iterate through the input
imagefromi = 0ton-1(rows). - For each row
i, iterate fromj = 0ton-1(columns). - In this inner loop, perform the horizontal flip:
result[i][j] = image[i][n - 1 - j]. - After the first pass, iterate through the
resultmatrix fromi = 0ton-1andj = 0ton-1. - In this second pass, perform the inversion:
result[i][j] = result[i][j] ^ 1. - Return the
resultmatrix.
Walkthrough
This method is the most straightforward. First, we create a new n x n matrix, say result, to store the final image. In the first pass, we iterate through each row of the input image. For each row, we reverse it and store the reversed row in the corresponding row of the result matrix. In the second pass, we iterate through the result matrix and invert each element. An element 0 becomes 1, and 1 becomes 0. This can be done using the XOR operation element = element ^ 1. Finally, we return the result matrix.
class Solution { public int[][] flipAndInvertImage(int[][] image) { int n = image.length; int[][] result = new int[n][n]; // Step 1: Flip each row horizontally and store in the new matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { result[i][j] = image[i][n - 1 - j]; } } // Step 2: Invert the new matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { result[i][j] = result[i][j] ^ 1; // Invert the bit } } return result; }}Complexity
Time
O(N^2), where N is the dimension of the matrix. We traverse the matrix twice: once for flipping (N*N operations) and once for inverting (N*N operations).
Space
O(N^2), where N is the dimension of the matrix. This is because we create a new `result` matrix of size `N x N`.
Trade-offs
Pros
Simple to understand and implement.
It's a pure function as it does not modify the original input matrix.
Cons
Inefficient in terms of space complexity as it requires an auxiliary matrix of the same size as the input.
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; }}/** * @param {number[][]} image * @return {number[][]} */ var flipAndInvertImage = function (image) { for (const row of image) { let i = 0; let 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; };class Solution {public: vector<vector<int>> flipAndInvertImage(vector<vector<int>> &image) { for (auto &row : image) { int i = 0, j = row.size() - 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; }};class Solution: def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]: n = len(image) for row in image: i, j = 0, n - 1 while i < j: if row[i] == row[j]: row[i] ^= 1 row[j] ^= 1 i, j = i + 1, j - 1 if i == j: row[i] ^= 1 return imageVideo 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.