The Problem

While studying for interviews, I’ve been practicing my algorithm skills on LeetCode and other sites quite a bit. Read on for a walkthrough of my JavaScript solution to the Flipping an Image problem on LeetCode (instructions from LeetCode are below).

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:

Example 2:

Notes:

Now let’s get started! Throughout the solution explanation, I’ll be using the first example input provided by LeetCode to demonstrate what’s happening through the function: [[1,1,0],[1,0,1],[0,0,0]].

We’ll be taking A (the original array) and transforming its values to return, so we will not need to make a new array for our result. To get to our solution, we should first flip our image horizontally, which will require changing the order of the elements in the A array.

Our solution will consist of nested for loops to iterate through the array of arrays, so to save an extra calculation each time we run through our inner loop, let’s declare a length variable to save the length of an array within A. Because we know that each array in A will be the same length due to the structure of a matrix, we can just find the length of the first array in A without worrying about the loop running correctly.

Next, let’s create our outer loop to move through A, which will have 3 iterations in this case: 1 [1,1,0], 2 [1,0,1], 3 [0,0,0]. Because A is an array of arrays, we should loop through each of the inner arrays as well, so we can touch on each individual element. Here’s the code we have so far, leaving some space in the outer loop for the inner loop to come.

We will be performing all transformations within our inner loop. Starting at index 0, we’ll be iterating through each array in A until the index is equal to or greater than half of the length of any of the arrays, as the index will increment with each pass. By only going over half of each array, we can avoid transforming the same elements multiple times.

To help us transform A, we will create a temporary variable, called curr, to save the values at the current element in the inner loop, A[i][j]. As we loop through [[1,1,0],[1,0,1],[0,0,0]], curr will touch the first two elements, 0 and 1, of each array in A. Console logging the value of curr through the loop gives us (in order): 1, 1, 1, 0, 0, 0.

Now let’s start transforming! We’re going to start by swapping the value of A[i][j] with the opposite (0 if 1, and vice versa) of the current value at A[i][length -1 -j]. The element we’re currently looping on is now flipped horizontally AND inverted. For example, our first array in A was originally [1,1,0]. So far at j = 0, the array is [1, 1, 0] because 1 was flipped with the opposite of 0, which is 1. If we keep going, at j = 1 the array will be [1,0,1] because we are flipping the element with itself and inverting it, changing the 1 to its opposite, 0. We just need to do one more thing to complete the transformation. Because the value at A[i][length -1 -j] is at A[i][j], we’ll have the value at A[i][length -1 -j] equal the original value of curr, pre-transformation. Now, the first array is equal to [1,0,0].

After returning the transformed array A outside of both loops, we have our completed solution, and all tests should now be passing! The runtime of this solution is O(n²).

Related posts:

Climate change can lead to flooding, hurricanes, droughts, wildfires and habitat loss. But could it also be shaking the ground beneath our feet? The debate around the connection between climate…

August 21st 2017. The first total eclipse across the U.S. in 38 years. Millions traveled to witness the totality, caught off guard by its emotional impact, reminding us of our origins and destination.