Flipping the Matrix | HackerRank | Solution Explained - Python
HTML-код
- Опубликовано: 20 авг 2024
- Flipping the Matrix | HackerRank | 1 Week Preparation Kit
Thanks for watching! Please hit the like and subscribe! It would mean a lot :)
Social Media
_______________________
Linkedin - / navidmisaghian
Discord - honcho#5006
_______________________
#leetcode #leetcodequestionandanswers #programming #coding #python #interviewpreparation #faang
Figuring this out on the fly is akin to just knowing how to solve a rubiks cube with no prior research
Literally. This is BULLSHIT.
And somehow companies think that this is to be skilled on real life.
man it was humbling that this was considered a "basic" on hackerrank
Now it's medium 🙄
There is basically zero chance that anyone would solve this in 20 minutes without having seen it before.
that is why the video and tons of "prepare for coding inteview" books exist :)
@@andreypopov6166 because of bad interview questions? I agree.
i do not like this approach either, it seems to be legit for CS or som R&D position. But this is a "reality" and unfortunately many companies blindly copying this hiring strategy.@@stillmattwest
Sometimes we need to be prepared for boat race even if provided boat have hole in it
@@andreypopov6166
Yeah, because of BAD interview questions. This is a BAD interview question.
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...
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.
the same happens to me haha
I had the same problem lol
I did the same, the explanation on hacker rank is misleading, because it shows that we need to flip things to reach the solution, but the problem is in which to flip first, the rows or the column.
How in the 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
don't worry man. I have 17 years of experience I've had a lot of programming jobs with a high pay and I got this excercise as a challenge from a friend and it was hard. I couldn't get it in 24 mins as hackerrank requested
@@GaboLaTo that’s a relief to hear. Sometimes I feel so insufficient in this field. I just want to get my foot in the door. I love programming and it’s fun to learn, but it’s so hard to find the opportunities for a job with no degree.
@@MrRANDUM145 the first one is the hardest. Keep learning and keep trying!
Hey, 3 years experience almost and this test got me, don't underestimate yourself, just know that by knowing this and practicing and also figuring out every piece of it, means you're adding it to your recognition pattern that you will eventually use someday to solve an issue without even knowing how (you'll probably forget all the hard work, and it will be all rewards) ;) Good luck.
I know it's been 6 months since you commented but omg I feel this so hard
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 :)
that single line in a loop is genius
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. 😅
😁
Did you pass your interview?
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
I appreciate you 🥰
This is really cool and solves matrix problems very quickly
!
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 :)
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.
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."
Figured this out quickly and put it into practice really well
Nice work!
Your explanation was amazing, really clears things up.
thank you :)
Anyone feeling bad when they can't figure these problems out before the time runs out?
the image you drew helps a lot for me to understand it. Thank you
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;
}
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.
respect! Great solution
clear explanation, thanks
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.
Very useful
Thanks a lot
Great explanation! Understanding the idea is the most important thing!
Thank you!
The problem is so confusing I couldn't understood it at all at first. Thanks for the video
Makes me happy that I helped :)
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...
Great explanantion.
Thank u.😍😍😍😍😘
perfect explanation and great logic to solve it! thx for sharing
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
individual row or column "flipping" seems to be not a "linear" operation and seems to be purely from a fancy world of "who knows why coding challenges".
@@andreypopov6166 technically it could be argued as a series of linear operations but that is irrelevant. The point is I agree with you
i am still wondering...what should i learn or read to be able to understand the math. reasoning behind the solution :) at the same time being just a software developer but not an engineer in CS R&D department....@@yauchinlam2276
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 :)
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?
Each quadrant has a mirror value on a uniform graph. Think of it like an x and y plot in geometry. When you have a geometric figure on one quadrant and want to reflect it over the y-axis flip it to the position it is currently at. For e.g. a figure at position (-1, 5) reflected over the y-axis ends up at position (1,5). Same with the theory pertaining to the problem above. Each index value in the upper left-hand quadrant had a reflection value somewhere on the matrix. Thus, by mirroring the values we are able to find which value corresponds to which value. This problem is very verbose in the sense that this only works since we are only concerned with the upper left-hand quadrant. Thus, if we aimed to find the largest values with no regard as to where they might be on the matrix we would have to approach it differently.
@@techandnavid I understand how the mirroring works! There are four positions in the upper left quadrant for a 4x4 matrix, call them q1(0,0), q2(0,1), q3(1,0) and q4(1,1). When you mirror q3 for example, you are also replacing q4!! So how did you know that there exists a combination such that you could mirror q3 without affecting q4? Thanks for taking the time to respond, I might not understand that your answer is already answering this, but I'm still confused and would greatly appreciate if you could explain
@@kamalkettaneh2160 I was thinking the same as you. You're right in the most basic sense that mirroring q3 you will also mirror q4 in that specific move. What I figured out by going through combinations by myself is that this problem is similar to some sort of 2D Rubiks cube. One flip of a row/column will flip all the squares in that part of the quadrant, but the key is to think of it as a combination of a lot of moves to get values where you want them to be. All the solution explanations I have found including this one just say you find the max value of all its mirror values and that is it. This is technically right but they dont explain why. You cannot just mirror one value in a quadrant without flipping the other values in that row/column in one move. It takes a combination of multiple moves to get that result just like a Rubiks cube. So the solution they are showing is right, but the explanation doesnt show how it works with the rules in the question. Because of this it would be very hard to do this via brute force method (at least the code would be complex). That is why all the solutions use this pattern. It is correct but it makes it seem very simple when the actual matrix operations to get there would be complex.
@@Ukranianolo EXACTLY thank you!! Do you know where I can find a "proof" that this works? I don't really get the rubiks cube analogy because I've never solved one hahahha
@@kamalkettaneh2160 Unfortunately I don't know. I just tested it out with a pen and paper myself to see as I also was confused. Its annoying but I recommend trying that just to see it works.
aint no way bro lookin at dunk highs !!!🤣🤣🤣
aint no fuckin way this is an easy problem
Great explanation. I love your matrix drawing with colors! This is simple once figured but hard to beginners.
I have 7 years of experience, it is hard.
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.
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.
Clean solution and nicely explained. The illustration was key 👌🏻
Great explanation!
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!
Keep it up
thank you! that was very clear
Glad it was helpful!
Thanks man, I was really confused and your explanation was great 💪
That's awesome! Incredible explanation, thank you so much!
Thanks man, it explain the idea so good. I start to understand why the logic is the key of programming.
Thank you for your explanation! So simple and elegant!
Amazing explanation man thanks 🙏🏽
thanks bro for such a clear explanation. I was confused by the question itself.
Man... you're God. Thank you.
Thanks for the expiation.
thank you so much man
Happy to help!
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?
super clear explanation thanks!
tnks a lot bro
Amazing explanation it helps me aloT
thanks bro
Could anybody sloved it on by own congrajulations to you🎉🎉🎉🎊🎊
The most difficult job in the world is solving problems through code,need lots of thinking🤔
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.
First
I fucking double dare someone to deduce this solution, seeing the problem for the first time in 24 minutes
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)?
how would you do it if you needed to actually make the maximal matrix
gotcha
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
im dying to know the solution of this. this problem is insane
Its greedy method, there is another method as well which i dont even understand after scratching my head to bleeding.
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
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?
It is called a greedy algorithm. If you want a correct explanation such as all combinations of rotations, it is called top-down dp or backtracking. Besides, it is hard to rotate columns by using Python. You may need numpy to do it. The easiest greedy algorithm example I can understand is to do a level order traversal on a tree and select the min value of each level. Apparently, you will not always get the minimal path sum by using such greedy algorithm.
@@hewbi123-ze3zz Nice job showing a specific rotation sequence that solves the problem. I was wonrdering about something similar, "Do the rotations to get the max value into arr[0][0] contradict with the rotations to get the max into arr[0][1] and the other arr[i][j]'s?" It turns out that since the number of rotations is not limited, there exists a sequence of rotations that get all the max's in the correct place. Good thing the problem does not ask for the sequence but only the final values.
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 ruclips.net/video/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
even if it's a whole number, the language can store it in a float. That is the case with python 3. And the range function expects an integer and it will fail if you pass a float.
@@GaboLaTo oh ok. Yes true. I did mine in JavaScript.