1
\$\begingroup\$

The task is taken from leetcode

Given a binary matrix A, we want to 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].

Example 1:

Input: [[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: [[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]]

Notes:

  • 1 <= A.length = A[0].length <= 20
  • 0 <= A[i][j] <= 1

My functional solution:

const arr = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]];
const flipAndInvertImage = A => A
    .map(x => x.reverse())
    .map(x => x.map(i => i ? 0 : 1));


console.log(flipAndInvertImage(arr));
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

If this was computer graphics each operation would be called a transform. You would never do two or more transforms in sequence you would combine the transforms into a single transform and apply that to the image.

As in this case the transforms are abstracted and thus hard coded you can avoid the need to combine transforms and just hard code the combined transform. IE reverse and flip in one expression.

Invert is often called "image negative". The transform is done by subtracting the pixel value from the maximum possible pixel value

Two versions

The first inverts using 1 - pixel and second using bitwise operation pixel ^ 1

const flipInvertImg = img => img.map(row => row.map((p,i) => 1 - row[row.length - 1 - i]))

or

const flipInvertImg = img => img.map(row => row.map((p,i) => row[row.length - 1 - i] ^ 1))
\$\endgroup\$
3
\$\begingroup\$

Flipping binary numbers (i.e. bits) from 0 to 1 or vise-versa can be achieved with bitwise operations, like XOR. This may give a slight performance increase in some browsers - refer to this jsPerf.

Instead of the ternary:

 .map(x => x.map(i => i ? 0 : 1));

Use XOR:

 .map(x => x.map(i => i ^ 1));

Unless I am mistaken, you should be able to combine the two .map() callbacks into one -

.map(x => x.reverse().map(i => i ^ 1));

This will lead to fewer function calls, resulting in less resources required to complete.

const arr = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]];
const flipAndInvertImage = A => A
    .map(x => x.reverse().map(i => i ^ 1));


console.log(flipAndInvertImage(arr));

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the hint with the bitwise operation. But your last code is incorrect I think. This should give me the correct result: const flipAndInvertImage2 = A => A.map(x => x.map(i => i ^ 1)); \$\endgroup\$ May 1, 2019 at 21:17
  • \$\begingroup\$ but that could wouldn't have the reverse() calls, and thus each row would not be flipped... \$\endgroup\$ May 1, 2019 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.