832. Flipping an Image
Problem Description
The problem provides us with a two-dimensional square matrix image
, where each element is a binary value (that is, either 0
or 1
). Our goal is to transform this matrix through two steps:
- First, we need to flip each row of the matrix horizontally. Flipping horizontally means that we reverse the order of the elements in each individual row. If we visualize each row as a sequence of pixels in an image, this operation would resemble looking at the row in a mirror.
- Second, we need to invert the entire matrix. Inverting means we swap each
0
with1
and vice versa.
The task is to perform these operations on the given matrix and return the resulting matrix. A key point is that we need to flip first and then invert.
Intuition
To approach this problem, let's focus on a single row to understand the operations required. Flipping a row is straightforward: we simply need to reverse the elements in the row. This can be done by swapping the elements starting from both ends and moving towards the middle. For example, to flip [1,1,0]
we swap the first and the last elements to get [0,1,1]
.
Inverting a row then requires us to iterate over each element and switch 1
s to 0
s and 0
s to 1
s.
However, we can perform the flipping and inverting in a single pass to make our solution more efficient. Notice that if an element is different from its corresponding element on the opposite side, flipping will just move them around, and inverting won't change that factāthey will remain different. The only case where we need to act is when the elements are the same; then, we swap and immediately invert (since post-flipping, they would be mirrored and the same). This can be achieved using an XOR operation with 1
(since 0 ^ 1 = 1
and 1 ^ 1 = 0
).
Also, if the number of elements in a row is odd, there will be a single element in the center after flipping, which will not change its position. This element alone should be inverted.
The code given carries out this optimized algorithm. It iterates over each row, flipping and inverting when needed, and deals with the potential middle element of odd-length rows. Finally, it returns the modified matrix, now flipped and inverted as required by the problem description.
Learn more about Two Pointers patterns.
Solution Approach
The solution to this problem involves a straightforward yet smart iteration over the matrix, particularly focusing on each row one by one. Several concepts are at play here:
-
In-place Modification: To save on space complexity, we perform the flipping and inverting of elements in place, modifying the original matrix without using any additional data structures for storage.
-
Two-Pointer Technique: This is a common pattern used in array and string manipulations. Here, it is utilized to reverse the elements of each row. We start with two pointers,
i
andj
, representing the start and end of a row, respectively. -
Bit Manipulation: Since we know our matrix will only contain binary digits
0
and1
, we can utilize an efficient operation known as XOR (^
) for inverting bits;0
becomes1
, and1
becomes0
.
Here is a walkthrough of the code to clarify the implementation of these concepts:
for row in image: # Iterating over each row of the matrix i, j = 0, n - 1 # Setting pointers to the beginning and end of the row while i < j: # Loop until the [two pointers](/problems/two_pointers_intro) meet in the middle if row[i] == row[j]: # Only swap and invert when the elements are the same row[i] ^= 1 # Invert the `i`-th element using XOR row[j] ^= 1 # Invert the `j`-th element using XOR # If the elements are different, no action is required since flip and invert would keep them different i, j = i + 1, j - 1 # Move the pointers closer to the center if i == j: # If the row has an odd number of elements, invert the central element row[i] ^= 1
After the for
loop runs for each row, all rows have been flipped and inverted according to the problem's constraints. The matrix image
is now modified in place and is returned as the final result.
In this method, the code achieves O(n^2)
time complexity, since each element is visited once, and O(1)
extra space complexity, as we only use a few variables for iteration and no additional storage for the result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the provided solution approach on a small 3x3
example matrix:
Original Matrix: 1 0 0 1 1 0 0 1 1
- We will process this matrix row by row.
- Each row operation includes flipping and inverting.
- The flipping and inverting are done using two pointers for each row, and an XOR operation is used for inverting.
Processing the first row: [1, 0, 0]
- Pointers
i
andj
start at positions0
and2
respectively. - Elements at
i
andj
(1
and0
) are different ā no operation necessary since they will be different even after flipping and inverting. - Move
i
to1
andj
to1
(pointers meet in the middle). - Since
i == j
, we invert the element at the center using XOR. The updated row is[1, 1, 0]
.
Processing the second row: [1, 1, 0]
i = 0
andj = 2
.- Elements at
i
andj
(1
and0
) are different ā again, no operation necessary. - Move
i
to1
andj
to1
(pointers meet in the middle). - Since
i == j
, we invert the element at the center using XOR. The updated row is[1, 0, 0]
.
Processing the third row: [0, 1, 1]
i = 0
andj = 2
.- Elements at
i
andj
(0
and1
) are different ā no operation necessary. - Move
i
to1
andj
to1
(pointers meet in the middle). - Since
i == j
, we invert the element at the center using XOR. The updated row is[0, 0, 1]
.
Here's the matrix after processing all the rows:
Flipped and Inverted Matrix: 1 1 0 1 0 0 0 0 1
- Notice that in this example, the outer elements of each row didn't need inverting because they were different from each other.
- The only elements that were inverted are the ones that ended up in the center after flipping (which in this case occurred for every row).
- The final modified matrix is the result of the flipping and inverting operations.
Solution Implementation
1class Solution:
2 def flip_and_invert_image(self, image):
3 """
4 Flips the image horizontally, then inverts it, and returns the resulting image.
5 :param image: A list of lists representing a binary matrix.
6 :return: The flipped and inverted image as a list of lists.
7 """
8
9 # Get the number of columns in the image
10 num_columns = len(image)
11
12 # Traverse each row of the image
13 for row in image:
14 # Set two pointers, starting from the beginning and the end of the row respectively
15 left, right = 0, num_columns - 1
16
17 # Continue swapping pixels until the pointers meet or cross
18 while left < right:
19 # If the values at the current pixels are the same, invert them
20 if row[left] == row[right]:
21 row[left] = 1 - row[left] # flip the pixel value
22 row[right] = 1 - row[right] # flip the pixel value
23
24 # Move the pointers towards the center
25 left += 1
26 right -= 1
27
28 # If the number of columns is odd, flip the central pixel
29 if left == right:
30 row[left] = 1 - row[left]
31
32 # Return the modified image
33 return image
34
35# Example usage:
36# sol = Solution()
37# image = [[1,1,0],[1,0,1],[0,0,0]]
38# print(sol.flip_and_invert_image(image)) # Output: [[1,0,0],[0,1,0],[1,1,1]]
39
1class Solution {
2
3 // The method flips the image horizontally and then inverts it.
4 public int[][] flipAndInvertImage(int[][] image) {
5 // Loop over each row in the image
6 for (int[] row : image) {
7 // Initialize two pointers for the start and end of the row
8 int start = 0, end = row.length - 1;
9
10 // Continue swapping until the pointers meet or cross
11 while (start <= end) {
12 // If the elements at the start and end are the same, flip them
13 if (row[start] == row[end]) {
14 row[start] ^= 1; // XOR with 1 will flip 0 to 1 and 1 to 0
15 row[end] = row[start]; // The flipped value is the same for start and end
16 }
17 // If start and end pointers are pointing to the same element,
18 // that means there's an odd number of elements in the row and
19 // we need to flip the middle element once.
20 // Note that this will also be handled correctly in the above if block.
21 if (start == end) {
22 row[start] ^= 1; // Flip the middle element
23 }
24 // Move the pointers inward
25 start++;
26 end--;
27 }
28 }
29 // Return the image after flipping and inverting
30 return image;
31 }
32}
33
1class Solution {
2public:
3 vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
4 // Iterate over each row of the image
5 for (auto& row : image) {
6 // Initialize two pointers, i starting from the beginning and j from the end of the row
7 int i = 0, j = row.size() - 1;
8 // Loop until the two pointers meet or cross
9 for (; i < j; ++i, --j) {
10 // If the current elements at i and j are the same, flip them
11 // Flipping is done by using XOR operation with 1
12 if (row[i] == row[j]) {
13 row[i] ^= 1;
14 row[j] ^= 1;
15 }
16 }
17 // If there is a middle element (odd number of elements), flip it
18 if (i == j) {
19 row[i] ^= 1;
20 }
21 }
22 // Return the modified image after flipping and inverting
23 return image;
24 }
25};
26
1/**
2 * Flips the image horizontally, then inverts it (1's become 0's and vice versa).
3 * @param {number[][]} image - A 2D array representing a binary image
4 * @return {number[][]} - The modified image after flipping and inverting
5 */
6function flipAndInvertImage(image: number[][]): number[][] {
7 // Iterate over each row in the image
8 for (const row of image) {
9 let leftIndex = 0; // Starting index from the left side
10 let rightIndex = row.length - 1; // Starting index from the right side
11
12 // Flip and invert the row using two pointers approach
13 for (; leftIndex < rightIndex; ++leftIndex, --rightIndex) {
14 // If the left and right values are the same, invert them
15 if (row[leftIndex] === row[rightIndex]) {
16 row[leftIndex] ^= 1;
17 row[rightIndex] ^= 1;
18 }
19 }
20 // If we have an odd number of elements, invert the middle one
21 if (leftIndex === rightIndex) {
22 row[leftIndex] ^= 1;
23 }
24 }
25 // Return the image after performing flip and invert
26 return image;
27}
28
29// Example use:
30// const resultImage = flipAndInvertImage([[1,1,0],[1,0,1],[0,0,0]]);
31// console.log(resultImage);
32
Time and Space Complexity
The time complexity of the code is O(n^2)
where n
is the length of each row of the image
. This is because the algorithm iterates over each element of the image once. Each row has n
elements, and there are n
rows.
The space complexity of the code is O(1)
since the operation is done in-place and does not require any additional space that is dependent on the input size. The variables i
, j
, and n
use a constant amount of extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!