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 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.

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.

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.

Solution Implementation

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.