Flipping the Matrix | HackerRank | Solution Explained - Python 

Figuring this out on the fly is akin to just knowing how to solve a rubiks cube with no prior research

The illustration definitely helps to visualise the problem. I can't believe this is on a beginner mock test when the other problems are nothing remotely like this...

man it was humbling that this was considered a "basic" on hackerrank

There is basically zero chance that anyone would solve this in 20 minutes without having seen it before.

I'm on day two of trying to solve this and finally gave up and headed here. Thank you for your full explanation. Seeing it now makes a lot of sense, but I just could not wrap my head around what was needed. I originally wrote a ton of logic to actually flip columns and reverse rows to try to solve this problem. I finally started to see the pattern you are showing when I wrote out a matrix out on paper and cut it into pieces to move around. I never did quite understand the mirroring process and even if I had, I don't think I would have been able to loop through them like you did. I learned a lot from this video. Thank you for sharing your knowledge.

How in the matrix flipping fuck is this considered an easy level challenge? I'm fucked if this is the kind of thought process I need to have throughout the 25 phases of coding interviews for a single "entry level" dev job

Thanks for the solution. humbled. But at the same time looking at comments I am happy that there are many others like me out there :)

Got this as my test, took me like 22 of the 24 minutes they gave me to finally come up with this idea of the pattern, but then didn't have time to code it out. Thanks for posting this so I at least got to see it working, was going to be up all night wondering if I was crazy not ever getting to see it actually run. 😅

that single line in a loop is genius

how do people figure out these problems just by themselves?!?! Anyways, thanks for the clear and simple solution! :)) other youtube vids were too long lol

Don't usually comment on videos, but the matrix implementation is actually so genius, I would have never figured this out. Appreciate the step by step explanation, it's so valuable for someone like myself :)

I'm interested in how one would come up with this. In my years of college and comp sci classes, the algorithm for finding a section of a matrix never came up. I think I'd simply tell the proctor of a interview, "I'd have to Google it to find the solution, as I would in my day to day work."

Thanks for your video. I didn't fully watch it, but just seeing the matrix drawing you made and how the mirroring works was enough to get me through the problem. This problem, along with "Counting Valleys" has taught me that what the text says doesn't really matter, it's all about the expected output. Literally reversing rows until you get to the result can be a huge computational effort, but once you understand that you really just need to find the biggest number among each set of mirrored elements and sum them, the problem gets much easier and just throws all the reversing and flipping away.

Your explanation was amazing, really clears things up.

Thanks for explaining this out and the illustration cleared up a lot - I was thinking each row/col as a whole array so my logic was off. I'm posting the javascript equivalent here - The function findMaxMirrorValue will determine the max value for a point on the matrix (only for the upper left quadrant, if the quadrant is changed, the logic does not account for that) Then it's just a matter of summing up the values for each point. function findMaxMirrorValue(point, matrix){ let rowpivot = (matrix.length -1)-point[0]; let colpivot = (matrix.length -1)-point[1]; let values = []; values.push(matrix[point[0]][point[1]]); //value at point values.push(matrix[point[0]][colpivot]);// row mirror values.push(matrix[rowpivot][point[1]]);//col mirror values.push(matrix[rowpivot][colpivot]); //Diag mirror values.sort(function(a,b){ return (a < b)? 1: (a > b)?-1:0; }); // console.log("Values are ",values); return values[0]; } function flippingMatrix(matrix) { // Write your code here let stop = (matrix.length/2); let sum = 0; //Loop through the points in the upper left matrix for(let row=0; row < stop; row++){ for(let col=0; col < stop; col++){ sum += findMaxMirrorValue([row,col], matrix) } } return sum; }

the image you drew helps a lot for me to understand it. Thank you

First try taking it, I really having hard time solving it myself and just give up before the times up. Big thanks for the intuition.

We should be so grateful that this video exists. Hackerrank's own "explanation" of their 4x4 matrix example must be the worst and least intuitive explanation I've ever seen in any logical/mathematical problem in my life.

Anyone feeling bad when they can't figure these problems out before the time runs out?

Good job on the video explanation but how did you find out about this pattern? I got a Bachelor in Mathematics before becoming a software engineer and that “pattern” was not taught in Linear Algebra, Discrete Mathematics, Abstract Algebra, etc. I am still looking for Math articles on this. In short: coding problems involve a bunch memorization of patterns. Edit: Yeah confirmed most Mathematical studies on a matrix do not deal with this operation. Example Linear Algebra a matrix is a representation of ax1+bx2+cx3+…+zxn where a,b,c, z are the values in a matrix. Flipping would cause it to be zx1+….+axn which would not help in solving linear equations. Hence no reason for it to be in Abstract Algebra either. Now it’s use in Graph Theory and Topology is a different story. Nothing for Adjacency Matrix. Of course there is a Math called Matrix Theory

Great explanation! Understanding the idea is the most important thing!

I know this has to be true, but how did you figure out that there exists a combination such that you could assign each quadrant the maximum of its mirror images? for example, the solved example shows us to first flip the column of index 2, then flip the row of index 0 thus getting q1 (119) max and q2 (114) max together (i.e in position (0,0), and (0,1)), but, if you flipped row index 0 first, and then column index 2, the 119 and 114 would not be together in the top left quadrant, indeed their positions would be (0,0) and (0,2), and if you flipped the row again you'd get 114 in the correct position (0,1) but 119 in the wrong position (0,3). So, how did you convince yourself there was always a combination of row and colum inverses that would allow you to get the max for each q1,q2,q3,q4?

This is a super elegant solution. But can we assume that there is always a possible solution for any initial configuration of values and for any matrix size, considering that when flipping a row, we distort columns and vice versa?

aint no fuckin way this is an easy problem

Now it makes so much sense. I coded a lot and got a wrong result. Learned a lot, but the solution was way simpler than I thought. Thank you :)

Clean solution and nicely explained. The illustration was key 👌🏻

I was so close to figuring it out but I just couldn't seem to put the dots together. Thank you so much, it was super easy once you mentioned the mirrors. Went and completed it, and now going to watch the rest of the video as thanks!

perfect explanation and great logic to solve it! thx for sharing

aint no way bro lookin at dunk highs !!!🤣🤣🤣

Figured this out quickly and put it into practice really well

Great explanation. I love your matrix drawing with colors! This is simple once figured but hard to beginners.

Hi! I came here to confirm that the problem is not well written, because if you flip a column [0] (leftmost column) for instance, [0][0] and [1][0] move together (top two values of leftmost column). which means that you cannot calculate the value per cell individually. rather, one would have to calculate the sum of the whole matrix within the possible universe of column/row combinations, since individual grids dont move or flip individually. Additionally, the problem states that N can be much larger than a 4x4 matrix. Which means that this drawing and corresponding calculations will not match a 6x6 or a 8x8 grid. At least from my perspective. In any case, thanks for sharing, since i couldnt be sure the problem and questions were wrong before i actually saw your video! I spent the while 20 mins without putting a character on screen...

Very useful Thanks a lot

respect! Great solution

This is really cool and solves matrix problems very quickly

The problem is so confusing I couldn't understood it at all at first. Thanks for the video

Thanks for saving me of going through the Greedy Algorithms rabbit hole (as suggested in my report). Not that it's not worthy to look at, but this explains how figuring out the approach is more than half of the work done.

Thanks man, I was really confused and your explanation was great 💪

Great explanantion. Thank u.😍😍😍😍😘

clear explanation, thanks

Thanks man, it explain the idea so good. I start to understand why the logic is the key of programming.

Thank you!

This question is a great example of what's wrong with a lot of tech interviews. To solve this in the given time you would have had to memorize the algorithm ahead of time. What someone has memorized doesn't show me what happens when they are faced with a new problem that you can't google. In an interview I might ask someone to tell me how they might solve it so I can get an idea of how they solve problems. I am more interested in how someone might solve a problem they have never seen. Not getting the exact answer in 30 minutes.

Great explanation!

thanks bro for such a clear explanation. I was confused by the question itself.

That's awesome! Incredible explanation, thank you so much!

Amazing explanation man thanks 🙏🏽

I am looking at this issue for not too long to be honest but there is something I don't understand with this approach. Imagine matrix like this: 1000 42 83 119 56 1000 56 49 15 78 101 43 62 98 114 108 How could you ever swap 42 with 114 without relocating 1000 to another square and losing max sum in that angle ? The solution you wrote just takes highest mirror number and adds it to the sum, but it doesn't check if that rotation is optimal.

Thank you for your explanation! So simple and elegant!

thank you! that was very clear

Man... you're God. Thank you.

Your solution works for the sample matrix (and apparently for all matrices in the test cases), but I don't understand why your solution works in the general case. Let's label our top row's elements as: [A1, B1, B2, A2] Assume the following values: [100, 3, 101, 3] In our first iteration, to see if we should add A1 or A2, we pick A1. We move to the B1 element now, we decide to swap it for B2. Doing this means we also switch A1 and A2 again, because we can only reverse per row (and per column). If I understand correctly, your algorithm's intermediate sum would now be equal to 100 + 101, but this should not be possible, afaik.

Thanks for the expiation.

Do you not also have to get max vals for B, C, and D to find the max sum for the entire quadrant (not just the A corner)?

Could anybody sloved it on by own congrajulations to you🎉🎉🎉🎊🎊

tnks a lot bro

thank you so much man

super clear explanation thanks!

Keep it up

thanks bro

how would you do it if you needed to actually make the maximal matrix

Amazing explanation it helps me aloT

i was able to find the logic but not able to find the [n-i-1] and [n-j-1] formula to get that particular index

The most difficult job in the world is solving problems through code,need lots of thinking🤔

First

im dying to know the solution of this. this problem is insane

guys screen got stuck at 10:06 can anyone provide the complete solution. upto this point im only able to see of to flip the A's. dont know how to flip the C,B and D's

I fucking double dare someone to deduce this solution, seeing the problem for the first time in 24 minutes

Its greedy method, there is another method as well which i dont even understand after scratching my head to bleeding.

What if this was the matrix: 119 114 42 112 56 125 126 1 15 78 56 43 62 98 83 108 According to this algorithm, the answer would be 119 + 114 + 56 + 126. But I'm confused about how you would switch the 126 in the second row with 125 in the second row?

gotcha

Love the explanation but you were too fast at times

Hey dear, awesome, immense thanks for your explanation on this mirroring concept of x-y axis quadrants and I was totally confused what to do but after watching your video, gave a very big sigh. Following is the Java code for anyone in need: import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; class Result { /* * Complete the 'flippingMatrix' function below. * * The function is expected to return an INTEGER. * The function accepts 2D_INTEGER_ARRAY matrix as parameter. */ public static int flippingMatrix(List matrix) { // Write your code here int sum = 0; int len = matrix.size(); for (int x = 0; x < (len / 2); x++) { for (int y = 0; y < (len / 2); y++) { // mirror concept as explained in ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-4rin1enhuQQ.html OptionalInt temp = IntStream.of(matrix.get(x).get(y), matrix.get(x).get(len-y-1), matrix.get(len-x-1).get(y), matrix.get(len-x-1).get(len-y-1)).max(); sum = sum + temp.getAsInt(); } } return sum; } } public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int q = Integer.parseInt(bufferedReader.readLine().trim()); IntStream.range(0, q).forEach(qItr -> { try { int n = Integer.parseInt(bufferedReader.readLine().trim()); List matrix = new ArrayList(); IntStream.range(0, 2 * n).forEach(i -> { try { matrix.add( Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" ")) .map(Integer::parseInt) .collect(toList()) ); } catch (IOException ex) { throw new RuntimeException(ex); } }); int result = Result.flippingMatrix(matrix); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); } catch (IOException ex) { throw new RuntimeException(ex); } }); bufferedReader.close(); bufferedWriter.close(); } }

It’s a 2n by 2n matrix . No need for floor division because it will always return a whole number