HackerRank’s Flipping the Matrix Problem

Sean invented a game involving a 2n x 2n matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times. The goal of the game is to maximize the sum of the elements in the n x n submatrix located in the upper-left quadrant of the matrix.

Given the initial configurations for q matrices, help Sean reverse the rows and columns of each matrix in the best possible way so that the sum of the elements in the matrix’s upper-left quadrant is maximal.

---

I came across this problem and was initially stumped by it. I decided to sketch out the problem which really helped me break it down into something more tangible.

As I worked through it, I realized that the matrix could be represented as a nested array, which I had to traverse in order to get the maximum values to the matrix’s upper left-hand quadrant. But what values could be swapped and what moves were not allowed?

By working backward from a sample solution, I recognized that the elements in the matrix could only swap with their direct horizontal or vertical counterparts, not freely across the entire matrix — like folding a piece of paper, values could only be swapped across an invisible vertical or horizontal line.

Next, I realized that, much like how nested arrays are structured, the values could be compartmentalized into smaller sub-matrices. From these sub-matrices, I could extract the maximum values to replace the upper-left quadrant values.

Working backward and visualizing each step taken toward a solution helped me focus on the four values or indices being compared at any given time (top left, top right, bottom left, and bottom right). With this in mind, I worked out how to reassign values as I iterated through the nested arrays. Here’s what I came up with:

public static int flippingMatrix(List<List<Integer>> matrix) {
  int size = matrix.size();

  // Half since we are working with quadrants
  int mid = size / 2;

  // Counter to track the total sum of the maximum values
  int totalMax = 0;

  for (int i = 0; i < mid; i++ ){
    for (int j = 0; j < mid; j++) {
      // Get the possible elements from the four mirrored positions
      int topLeft = matrix.get(i).get(j);
      int topRight = matrix.get(i).get(size - j - 1);

      int bottomLeft = matrix.get(size - i - 1).get(j);
      int bottomRight = matrix.get(size - i - 1).get(size - j - 1);

      // Find the maximum value among the four possible positions and add it to the total sum
      totalMax += Math.max(Math.max(topLeft, topRight),
      Math.max(bottomLeft, bottomRight));
    }  
  }
  return totalMax;
}

// Solution:
// 119 + 114 + 56 + 125 = 414

Taking out a pen and paper — or in my case, a digital notepad — turned out to be a great way to get my thoughts flowing. It helped me spot a pattern and map out recurring behaviors in the problem.

---

Visually breaking down a problem can often reveal simpler, more intuitive solutions. If you’re a visual learner like me, I highly recommend exploring resources like VisualAlgo, which provide interactive visual descriptions and solutions of algorithms and data structures.

Thanks for reading!