In this post we will attempt to solve LeetCode 832. Flipping an Image in Java.
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]. Constraints: o n == image.length o n == image[i].length o 1 <= n <= 20 o images[i][j] is either 0 or 1. Related Topivs: o Array o Two Pointers o Matrix o Simulation
We are given a matrix of 0s and 1s and are asked to flip and then invert some of the values.
Seems like the key of this problem is going to blend both operations into one to achieve better performance.
We will be developing the solution using the Java programming language with the VSCode IDE on a Windows machine. Java is quite portable so you can use the platform of your choice. The simplest way to solve the problem is to use the online IDE provided by LeetCode. Since I will be developing the solution on my machine and then copying the code to submit, I will need a test scaffold which will collect the input data, populate the arguments for the function of interest, call the function of interest and display the results. Note that the test code IS NOT PART OF THE SOLUTION!
public int[][] flipAndInvertImage(int[][] image) {
}
The signature for the function of interest matches the requirements. We are provided a n x n matrix and we need to return a matrix in which both operations have been applied to the input data.
1,1,0 1,0,1 0,0,0 main <<< n: 3 main <<< image: [1, 1, 0] [1, 0, 1] [0, 0, 0] main <<< flipAndInvertImage0: [1, 0, 0] [0, 1, 0] [1, 1, 1] main <<< flipAndInvertImage1: [1, 0, 0] [0, 1, 0] [1, 1, 1] main <<< flipAndInvertImage: [1, 0, 0] [0, 1, 0] [1, 1, 1] 1,1,0,0 1,0,0,1 0,1,1,1 1,0,1,0 main <<< n: 4 main <<< image: [1, 1, 0, 0] [1, 0, 0, 1] [0, 1, 1, 1] [1, 0, 1, 0] main <<< flipAndInvertImage0: [1, 1, 0, 0] [0, 1, 1, 0] [0, 0, 0, 1] [1, 0, 1, 0] main <<< flipAndInvertImage1: [1, 1, 0, 0] [0, 1, 1, 0] [0, 0, 0, 1] [1, 0, 1, 0] main <<< flipAndInvertImage: [1, 1, 0, 0] [0, 1, 1, 0] [0, 0, 0, 1] [1, 0, 1, 0]
The test cases are separated by two blank lines.
The input lines represent the contents of the image n x n array of 0s and 1s. Our test code seems to read the input data and determine the size of the square `image`. The size of one dimension `n` is assigned and displayed by our test code. The contents of the `image` are then displayed. So far all is well. We are ready to call the function of interest.
It seems that our test code will call three implementations of the function of interest. The results for each call are displayed.
Note that as it was previously stated, the test code IS NOT PART OF THE SOLUTION!
/**
* Test scaffold.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read first input line ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** determine n ****
int n = arr.length;
// **** declare and populate image ****
int[][] image = new int[n][];
image[0] = arr;
for (int i = 1; i < n; i++) {
image[i] = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
}
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
System.out.println("main <<< image: ");
for (int i = 0; i < n; i++)
System.out.println(Arrays.toString(image[i]));
// **** clone image ****
// int[][] cloned = image.clone();
int[][] cloned = new int[n][n];
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
cloned[r] = image[r];
// **** call function of interest ****
image = flipAndInvertImage0(image);
// **** display output image ****
System.out.println("main <<< flipAndInvertImage0: ");
for (int i = 0; i < n; i++)
System.out.println(Arrays.toString(image[i]));
// **** restore image ****
image = cloned.clone();
// **** call function of interest ****
image = flipAndInvertImage1(image);
// **** display output image ****
System.out.println("main <<< flipAndInvertImage1: ");
for (int i = 0; i < n; i++)
System.out.println(Arrays.toString(image[i]));
// **** restore image ****
image = cloned.clone();
// **** call function of interest ****
image = flipAndInvertImage(image);
// **** display output image ****
System.out.println("main <<< flipAndInvertImage: ");
for (int i = 0; i < n; i++)
System.out.println(Arrays.toString(image[i]));
}
Not much to add to the description of the test code. We make a deep copy of the input data so we can afford to change the input array and return a copy and then be able to make additional calls to different implementations of the function of interest using the same input.
/**
* Given an n x n binary matrix image,
* flip the image horizontally,
* then invert it,
* and return the resulting image.
*
* Execution: O(N) - Space: O(1)
* 82 / 82 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 41.8 MB
*/
static public int[][] flipAndInvertImage0(int[][] image) {
// **** initialization ****
int n = image.length;
// **** sanity checks ****
if (n == 1) {
image[0][0] = (image[0][0] == 0) ? 1 : 0;
return image;
}
// **** flip image horizontally - O(n) ****
for (int i = 0; i < n; i++)
flip(image[i]);
// **** invert image - O(n) ****
invert(image);
// **** return processed image ****
return image;
}
We start by performing a sanity check. If the image is a 1 x 1 matrix, the result is the same image with the input value flipped.
The function then calls an auxiliary function `flip` to flip all the rows.
Next we invoke the `invert` auxiliary function to perform the flip of values.
This approach should work but we should be able to get better performance by blending both operations into a single pass.
/**
* Flip the contents of the specified array.
*/
static private void flip(int[] arr) {
// **** initialization ****
int n = arr.length;
int i = 0;
int j = n - 1;
// **** flip array contents ****
while (i < j) {
// **** flip elements ****
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// **** update indices ****
i++;
j--;
}
}
The `flip` auxiliary function flips / reverses the values of a row. It starts by initializing three variables. A while loop is entered. End values are swapped and the indices are updated. We have used this same approach in previous posts in this blog.
/**
* Invert the values of the specified matrix.
*/
static private void invert(int[][] matrix) {
// **** initialization ****
int n = matrix.length;
// **** invert values ****
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
matrix[r] = (matrix[r] == 0) ? 1 : 0;
}
The `invert` auxiliary function inverts the values of the specified matrix. In C/C++ using indices to access cells in a matrix is quite efficient. Not so much in Java. We should operate on each row at a time. Will try that in the next implementation.
/**
* Given an n x n binary matrix image,
* flip the image horizontally,
* then invert it,
* and return the resulting image.
*
* Execution: O(N) - Space: O(N)
*
* 82 / 82 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 42 MB
*/
static public int[][] flipAndInvertImage1(int[][] image) {
// **** sanity checks ****
if (image.length == 1) {
image[0][0] = (image[0][0] == 0) ? 1 : 0;
return image;
}
// **** initialization ****
int n = image.length;
int[][] matrix = new int[n][n];
// **** copy cell values from image to matrix - O(N) ****
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
matrix[r] = (image[r][n - 1 - c] == 0) ? 1 : 0;
}
// ???? ????
// System.out.println("<<< matrix[" + r + "]: " + Arrays.toString(matrix[r]));
}
// **** return matrix ****
return matrix;
}
This is the second implementation of the function of interest. In this one we use a separate array. The idea is to generate the values for each cell in a single pass.
The next loops allow us to flip and invert the values and copy them to the `matrix`. When all is said and done our function returns the `matrix`.
/**
* Given an n x n binary matrix image,
* flip the image horizontally,
* then invert it,
* and return the resulting image.
*
* Execution: O(N) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 41.7 MB, less than 8.71% of Java online submissions.
*/
static public int[][] flipAndInvertImage(int[][] image) {
// **** initialization ****
int n = image.length;
// **** sanity checks ****
if (n == 1) {
image[0][0] = (image[0][0] == 0) ? 1 : 0;
return image;
}
// **** flip and invert cells one row at a time - O(N) ****
for (int[] row : image) {
// **** flip and invert cells - O(n) ****
for (int i = 0; i * 2 < n; i++)
if (row[i] == row[n - 1 - i])
row[i] = row[n - 1 - i] ^= 1;
}
// **** return processed image ****
return image;
}
This implementation of the function of interest makes the changes on the input `image`. Note that it works on a row at a time. The reverse value is handled using the XOR operation instead of an inline test and update.
At this time please go back and take a look at the comments section of each implementation of the function of interest. You can see the progression of the execution times from longer to shorter.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named FlippingAnImage.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John