832. Flipping an Image

EasyArrayTwo PointersMatrixSimulation
Leetcode Link

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 with 1 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 1s to 0s and 0s to 1s.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which technique can we use to find the middle of a linked list?

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 and j, representing the start and end of a row, respectively.

  • Bit Manipulation: Since we know our matrix will only contain binary digits 0 and 1, we can utilize an efficient operation known as XOR (^) for inverting bits; 0 becomes 1, and 1 becomes 0.

Here is a walkthrough of the code to clarify the implementation of these concepts:

1for row in image: # Iterating over each row of the matrix
2    i, j = 0, n - 1 # Setting pointers to the beginning and end of the row
3    while i < j: # Loop until the [two pointers](/problems/two_pointers_intro) meet in the middle
4        if row[i] == row[j]: # Only swap and invert when the elements are the same
5            row[i] ^= 1 # Invert the `i`-th element using XOR
6            row[j] ^= 1 # Invert the `j`-th element using XOR
7        # If the elements are different, no action is required since flip and invert would keep them different
8        i, j = i + 1, j - 1 # Move the pointers closer to the center
9      
10    if i == j: # If the row has an odd number of elements, invert the central element
11        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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's apply the provided solution approach on a small 3x3 example matrix:

1Original Matrix:
21 0 0
31 1 0
40 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 and j start at positions 0 and 2 respectively.
  • Elements at i and j (1 and 0) are different – no operation necessary since they will be different even after flipping and inverting.
  • Move i to 1 and j to 1 (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 and j = 2.
  • Elements at i and j (1 and 0) are different – again, no operation necessary.
  • Move i to 1 and j to 1 (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 and j = 2.
  • Elements at i and j (0 and 1) are different – no operation necessary.
  • Move i to 1 and j to 1 (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:

1Flipped and Inverted Matrix:
21 1 0
31 0 0
40 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.
Not Sure What to Study? Take the 2-min Quiz:

Which data structure is used to implement priority queue?

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫