
Problem Statement
In the provided problem, we are given a binary matrix image
where n x n
denotes its dimensions. The task is to manipulate this matrix by performing two specific transformations:
- Flip the matrix horizontally. This means reversing the order of elements in each row of the matrix. For instance, if a row in the matrix is
[1,1,0]
, after a horizontal flip it would become[0,1,1]
. - Invert the matrix. Post the horizontal flip; each element in the matrix needs to be inverted. In this context, inversion means converting every
1
to0
and every0
to1
. For example, after flipping if a row reads[0,1,1]
, it should be transformed to[1,0,0]
after the inversion.
The end goal is to return the matrix after these transformations have been applied to each row.
Examples
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.length
n == image[i].length
1 <= n <= 20
images[i][j]
is either0
or1
.
Approach and Intuition
The process of transforming the matrix can be understood and implemented through the following steps:
Flip Horizontally:
- Traverse through each row of the matrix.
- Reverse the order of elements within the row. This can be done using slicing in Python (
row[::-1]
), or any similar method in other programming languages which supports reversing lists or arrays.
Invert the Matrix:
- After flipping all the rows horizontally, iterate through each element of each row.
- Replace
1
with0
and0
with1
. This can involve a conditional check for each element (e.g.,if element is 1 then it becomes 0
).
Given these operations and based on our constraints whereby the dimensions and values are within a manageable range (n
up to 20 and matrix elements as 0 or 1), an approach that involves iterating through each element in the matrix sequentially to perform the required transformations is computationally feasible.
Thus, the algorithm involves running two nested loops: the outer loop iterates through each row and the inner loop iterates through each element of the row, ensuring all elements are first reversed and then inverted. The entire process runs in O(n^2)
time complexity where n
is the dimension of the matrix, making it a straightforward and efficient solution for the given problem size constraints.
Solutions
- Java
class Solution {
public int[][] invertAndFlipImage(int[][] image) {
int cols = image[0].length;
for (int[] row: image)
for (int j = 0; j < (cols + 1) / 2; ++j) {
int temp = row[j] ^ 1;
row[j] = row[cols - 1 - j] ^ 1;
row[cols - 1 - j] = temp;
}
return image;
}
}
The solution provided handles the problem of flipping an image horizontally and inverting its pixels. The function invertAndFlipImage
operates in-place on a 2D array image
. Below is an outline on how this Java function accomplishes the task of flipping and inverting:
- Determine the number of columns in the image with
int cols = image[0].length;
. - Use nested loops to iterate through each row and every element within half of the column (due to the symmetry of flipping):
- Outer loop iterates over each row:
for (int[] row : image)
. - Inner loop runs until halfway through the row or, in case of an odd number of columns, includes the central element:
for (int j = 0; j < (cols + 1) / 2; ++j)
.
- Outer loop iterates over each row:
- Inside the inner loop:
- Perform the XOR operation with 1 to invert the binary pixel values.
- Swap the current element
row[j]
with its opposite in the same row (row[cols - 1 - j]
). - Ensure the swap also applies the inversion by setting
row[j] = row[cols - 1 - j] ^ 1
androw[cols - 1 - j] = temp
.
- Return the modified image.
This procedure effectively flips each row's elements horizontally and inverts their values from 1 to 0 or from 0 to 1, maintaining efficient in-place modifications without additional space requirements, using XOR for inversion and simple swaps for flipping.
No comments yet.