HackerRank: Flipping the Matrix (JavaScript)
Flipping the Matrix is a “medium” challenge on HackerRank. It’s a tricky problem to visualize and seems fairly complicated when you first try to figure it out. But once you sketch out a strategy for solving it, the actual solution is very straightforward.
The problem statement can be found here:
We are asked to return the maximum sum of the elements in the upper-left quadrant of a square matrix (same number of rows and columns).
It may appear a bit arbitrary as to what to flip first and whether can you be sure you have the maximum values in the upper-left quadrant when dealing with increasingly large matrices. That’s why the wise approach is to come up with a generalized solution.
Using this simple 4 x 4 matrix, we can replace the upper-left submatrix elements with a, b, c, d. Then we can flip our rows and columns to see exactly where a, b, c, and d appear in the other quadrants.
These are the ONLY places corresponding elements can flip to regardless of how many flips you perform. So all you have to do now is generalize the location for the other three n x n quadrants using the rows and columns. Notice that we will only be cycling through the n x n submatrix in the solution, but comparing those numbers to values relative to the 2n x 2n matrix. By subtracting either the row or col index from 2n, and 1 from that to account for our zero-indexing, we have generalized this correspondence for any size square matrix. All that’s left to do is track the maximum value and add it to the total.
And the solution:
In short, the trick to this challenge is to first consider the result of flipping the rows and columns. Then the next challenge is how to access the corresponding elements in the other quadrants so you can compare them. The strategies used here are excellent ones to have in your back pocket when faced with other matrix challenges you may encounter.
Happy coding!
