Deep Dive into the Matrix Data Structure

Key Takeaways

what are the chances of you knowing what this is yes you got that right this is a table something that you use to organize data using constructs like columns and rows however did you know that a table is also known as a matrix a matrix is a type of a multi-dimensional array and is one of the most popular data Circ discovered in coding interviews and this video I will discuss the most important aspects about matrixes and how to implement them hi my name is Ricardo ferera and I'm a developer advocate here with AWS welcome back to this series about data structures in this episode I will talk about matrixes the Matrix data structure is widely used in many fields such as linear algebra computer graphics and statistics but I am almost sure that this is not the reason why you are here today chances are that you are here because number one you are a software engineer and number two matrixes are heavily explored during coding interviews why Matrix are so popular well because they enable the efficient storage and manipulation of arrays during coding interviews developers are frequently required to solve problems involving two dimensional arrays and the problems vary from things like printing The Matrix values in a form of a spiral to something even more elaborate like uh in place rotating the matrix by 90° in clockwise Direction in addition you may see sorting algorithms like quick sort being used along with Matrix implementations overall The Matrix data struy is a versitile tool that frequently appears in coding interviews therefore being an invaluable topic for you to learn while preparing for one in this case let's get to work a matrix is a two-dimensional data struy that is used to store and man temp arrays in a TBL form it is made up of rows and columns where each element of the array is referred to as a cell imagine for example a spreadsheet where each row represents a record and each column represents a feud or an attribute of that record in a matrix you can access individual Elements by their row and column indices in the spreadsheet example that I just gave you let's say you want to retrieve the column first name you could access the first name value for the first row by using the notation Matrix Z of one where Matrix is the name of the Matrix and zero and one are the column and row indices respectively Matrix data structures are commonly used in mathematics physics and computer science for solving linear equations representing graphs and Performing Matrix operations such as addition subtraction multiplication and transposition of data they are also used in programming languages like matlb Python and Java for scientific Computing and data analysis overall matrixes provide a convenient way to organize and manipulate data in a Tabler format making it easier to perform calculations analyzing data and represent complex relationships between variables matrixes have several advantages for example a matrix data structure is a collection of rows and columns that are arranged in a gridlike fashion the stricty of the Matrix allows for efficient storage and retrieval of data it can also be used to represent and solve a wide range of mathematical problems such as linear equations Vector spaces and agent values it is a powerful tool for data analysis and visualization of data as it allows for easy manipulation of data and the ability to see patterns and relationships between variables however just like any data circuit matrixes have disadvantages one of the main disadvantages of a matrix data circle is its size a matrix data can be large and become unwieldly especially if it contains a lot of data this can make it difficult to manipulate and analyze data especially if you are using a programming language that does not have efficient Matrix operation support for it another disadvantage of a matrix data structure is its complexity creating a matrix data structure requires careful planning and design and can be easy to make make mistakes when you are designing The Matrix additionally modifying the data in a matrix can be timec consuming and difficult especially if you need to modify multiple rows or columns let's see how matrixes work from the implementation perspective all right back to our Visual Studio code we're going to start the implementation of our Matrix in this class here called Matrix which you can find here on the packet ADT so so the first thing we're going to do is to declare the Matrix so declare a matrix with five columns and five rows so this means that we're going to create a perfectly squared Matrix I'm going to hit enter uh let's see what code risper provides seems to be correct uh variable Matrix this is the Matrix using the Java notation which is one array within another array and then these are the D dimensions of this matrix it's correct and then we're going to just like we did with the uh the array episode we're going to initialize this Matrix with random values so um let's ask code whisper to create a method to inage The Matrix with random values going to hit enter let's see how it comes this method signature seems to be correct or at least uh suggestive enough hit enter let's see what the code looks like uh looks correct I'm going to close the method but just let me just review the matter for a second so here we have a outerloop that's going to iterate over the columns and for each interaction is going to have an in Loop that's going to iterate over the rows of the Matrix so and then for each column and row it's going to associate a random value so it seems to be correct the only way for for us to actually double check this is to print the values of this Matrix so let's create uh here we go Amazon code whisper is kind of a trying to anticipate what I want to do which is create a method to print a matrix thank you code whisper is exactly what I need um so yeah print a matrix I am going to use this one here seems to be correct and then okay it's probably doing some sort of a identation in the output okay system print in okay I'm going to close it h seems to be correct but let's execute this method for the first time so we can check if it's doing what it's supposed to do uh for this I'm going to create a main method uh and then we can go from there so so it's going to go yep that's what I need so instantiate the Matrix initialize the Matrix and then print the Matrix let's execute this code for the first time so we can see the contents of this Matrix and more importantly what's going to be the layout that this uh print mate bricks method is going to use we going to run and then okay now I understand what the code is doing so basically is doing this kind of a manipulation with the strings and space and checking if the it is the end of the Matrix so we can start uh finishing that rle so it print out the values with this kind of a like a table right uh like a matrix that has like a bunch of rows and columns those and as you as I mentioned before since we're creating a matrix that has five columns and five rows as you can see here is a perfectly Square Matrix um and the output doesn't seem like so perfectly but it is U like concept actually it is a a square instead of a rectangle right so so far so good uh it's definitely creating some random values uh in our Matrix now before we move further uh it is important for you to know that uh what I mentioned before about it sometimes when you're working with matrixes is complicated but you has to careful design of it and what I meant by this is this so when we were declaring The Matrix we we had to do this conscious decision about how many actual columns and rows we were going to have and then everything that uh uh happen further rely on the fact of this fixed size data struct so this is one of the things that you have to keep in mind because when you are creating one Matrix for the first time and each align with values is going to sound just like you you see here a bit easy because you know up front what you're going to do but uh the complexity of matrixes start happening when you start mutating and adding on removing values uh let's see uh a couple of examples of this type of complexity the first scenario we're going to play with is the scenario where you were asked to include into the existing Matrix a new rle so the currently Matrix has five columns and five rows so you are going to end up with a matrix that now has six rows and this new row is going to be initialized with random valum so let's see uh how this code and implementation would look like so let's ask code whisper to create a method to add a new row into the Matrix and in it the row with random values right so I'm going to hit enter to see the implementation of this um and uh okay let me start with the math signature add row I'm going to hit enter and then let's see what comes from this um all right so there's only one suggestions as you can see here one of one so I'm going to Simply hit Tab and accept the suggestion so we are basically creating a new Matrix uh like I mentioned before dealing with the matrixes is complicated because of the nature of their fixed size so so every time you are going to add or remove elements and columns and uh rows you most likely end up with the operation of cre recreating a new Matrix transversing the existing Matrix and copying the values to one and another so this is a this is an operation that takes time to compute and depending on the size of the Matrix uh number of columns and number of rows like I mentioned and and the before it can become computationally expensive so this is one of the things that you have to keep in mind during the current interview right and if the interviewer are asking you to perform operations like this is not only that you have to know how to do it but you have to always keep that in mind because in a given point of time you might need to kind of a change your approach for doing things but right now basically what they're doing is after creating the new Matrix going to basically need read the existing values and copy to this new Matrix and then doing some putting the U and the new M the new row that has been added is going to be initialize with random valid which is basically what we have asked in the instruction so let's see how this goes so I'm going to Simply after printing the original Matrix I'm going to put a separation here so we can see the difference of and then we're going to Matrix add row right so this is the row that's going to be initialized with random values and then we're going to once again print the Matrix and as you can see here code whisper is already assuming that this is what we want to do this is one of the uh inter things and things about like generative AI Technologies because giving a proper context and giving the proper set of instructions that you were given as a prompt for the generative AI implementation it is able to do some inferences about what your intentions are it's uh it is almost like a a humanlike prediction of behavior it's very amazing but anyway let's execute this code one more time to see if this is doing what we are asking for so here is the result of our first print with the square Matrix so Square because it has uh five columns and five rows and here you have the second one with the existing values but now as you can see here it has like five columns and 1 2 3 four five six uh rows so it seems to be doing what you're supposed to do so it you just added a new role into the existing Matrix right um so if we reveal the code here you're going to see that it involves the creation of a new Matrix the reading of the existing values the this is kind of optional because this is basically the result of us initializing with random values and then we are basically doing the re re referencing of the new Matrix to the old Matrix um so it's basically for for us to say okay the the the new Matrix now has to be the one that has six rows now the former one that has uh five rows so this is one great example of restructuring operations that you can do in a matrix exercise now the second operation that we're going to actually play with is removal of columns right so this is a little trickier because adding roles it's somehow uh operation where you basically dealing with the last dimension of a matrix right but now we're changing the first dimension of the Matrix which is the columns right so that's a little trickier uh so let's see how this goes so let's create a new method create a method to remove the last column of the Matrix right so that's a good instruction for Amazon code whisper let's hit enter and see how it goes remove columns seems to be correct the method signature is suggestive and uh I'm going to hit enters and see what are the possible implementation so basically we're playing around here with two choices one of them iterate over the roles using the length and the other one length minus one I'm going to accept this version where lens minus one seems to be more correct to me because as you may know arrays and Java at least they start with zero so if you want to read the last position of array you have to always uh remember that it is not the last position is not going to be the size of the array but size or length minus one right so we have to compensate this fact that the arrays start from zero um so we've removed the column and we're going to do the same exercise here so we're going to create another separator to see how this goes and then we're going to yes thank you Amazon code whisper this is exactly what I want I want to remove the column and then print the Matrix one more time so it's let's let let let's see how this goes I'm going to run the code one more time and then let's review the output so this is the first print so we have the square Square Matrix with five columns and five rows seems to be correct then the second one which it's we we can assume it's correct because we didn't change that part of the code so it's going to be like still five rows five columns and six rows but in this version here we're basically operating with the a matrix that is similar to this one you can see but given the first columns right but it doesn't contain the last column which is the the column that contains the 4 9 0 2 2 and 1 so that last column was properly removed now that we see that the code works and congratulations Cod whisper because you were spot on on this one uh let's uh review the code so always start with the creation of a new Matrix you can't get away from this it's going to have basically the the same length of the existing Matrix and the number of rows will be the length minus one seem to be correct and then we're we're going to iterate over the uh the outer loop which is basically the number of columns that we have available and then we're going to copy for each row only what is considered to be uh the all the all the rows for each column but as you can see here because we're operating with lens minus one we're not only going to copy the last column so the the implementation seems to be correct and just like we did before we are doing the D referencing which is uh the existing Matrix is going to not only Point through the version in memory remember Java allocates all the objects on hip so that object is going to be deeren and then this reference called Matrix is going to reference the new Matrix so we're going to retire the old fermentation so what's going to happen in Java and by the way this is one of the things that you also have to keep in mind about the architecture of certain programming language in platforms uh in case of Java for example there might be situations where the interview come may come to you and say hey just out of curiosity uh what's going to happen with this Matrix variable after this code is acutes so you should know that uh because of this whole like referencing and de references what's going to happen with the U original Matrix is that it's going to be not only holding any references to it so it's going to be electable for being garbage collected because Java is a garbage Collective programming language so keep that in mind because those are one examples of Jabs that interviewers may come to and they again they're not doing this because they want to be mean at you they're doing to uh evaluate the depth of your knowledge into an existing program or in a matter of fact I would say that your death of knowledge on uh computer architectures in general because uh knowing how for example garard collect works it it's important for you to be a for them to measure you if you are a good developer in terms of optimizations and performance and things like this so now that we have completed this exercise of structuring let's play with some scenarios and examples that might happen your current interviews for for you to play with the idea of manipulation of data the first example is going to be actually pretty popular which is uh imagine that we're working with a table because again Matrix is basically a table and then you are going to do that operation that famous operation where you use your your mouse and then you click on top of a column right where it holds the titles of the columns and then you you want to sort an existing column specifically the column that you've just clicked but for this exercise you're not going to do any Mouse and you don't have any visual representation of your Matrix is everything is conceptual right so the instruction is uh how would you sort an existing column given a column how would you sort that column in ascendent order right so let's see how this uh would look like in a code level so let's create uh a method create a method which is going to to sort the elements of a given column in ascendant order right so given a column sort it and as inate order so let's see how the implementation looks like so the method signature is suggestive uh not sure if you notice uh this is one of the patterns that when working with code whisper uh it is interesting for you to know because um I'll start with the method signature see if they make sense because instinctively you might just want to kind of iterate over all the suggestion here but but I think it's always important for you to start with the method signature because this is going to be your your H how you want the code to look like so in in my perspective given the instruction of the problem I want to provide the column index so that's my input hence the parameter and column index and the operation is sort the column so the method signature seems to be correct right and return void means I don't want to return anything I just want to sort which is know in the algorithm space as a in place operation so why in place because I want to actually mutate the order of the elements within the data struy right so I'm going to accept this recommendation uh and hit enter so I can continue playing with the Sorting exercise there are two versions here uh both of them no actually there are four recommendations here let me iterate over each one of them and see which one we're going to use um this one is more like it in my opinion because dealing with matrixes you are almost going to end up in situations like this where you you need to iterate over at least once to read the values and uh one or a couple more times to rearrange the position of the value so you would never kind of be able to get away with the possibility of doing multiple iteration of and and that's where comes the complexity of performers complexity of dealing with matrixes because now you are regardless if you are changing the structur or simply doing in place uh mutations of data you have to do those like continuous operations right so it's uh something that you have to keep in mind um so let's execute the code and then we can go back to read the algorithm so um let me kind of a clean up a little bit of this we don't need to inspect if the whole add row and removing columns are working we know that is is working at this point so I'm going to remove kind of this uh operations so in between in at the Matrix and print the Matrix I'm basically going to put the separation one more time and then I'm going to request the Matrix to what is the name of the method sort column this one over here and then let's pick up maybe the First Column which is column number zero right and then we're going to print the Matrix again yes thank you code whisper this is what I need going to clear up this output a little bit and then let's see if this is working right so let's run the code one more time and inspect the output so here's the first output nothing is supposed to change here it's just a matrix with five columns five rows random values but we've asked for the First Column to be sorted so let's see if this happen so the First Column is 95028 and the second version The First Column is 02 589 which is a Dar good sorting in my opinion so this is the correct output that we were looking for so now that we know that the code is doing what it's supposed to do let's go back and review the implementation so sort column given an index what we're going to do is create a new version of the sorted array uh given the length of the um the existing Matrix and then we are going and again why an array with only one dimension or in other words an array because it is almost as if you were zooming in into one of the uh dimensions of that Matrix so remember a matrix is nothing more than an array whose the elements of the first Dimensions is another array right so before we move forward let's see this how this works visually so I'm going to put a breakpoint here and then we're going to debug the code so we can use the debug visualizer right so um let's work with the debug visualizer so uh debug visualizer this is new and then we're going to Simply use the Matrix right so this is a better way for you to visualize The Matrix so as you can see here the Matrix has five columns and five rows and each one of those Dimensions let's let me zoom in a little bit here let me give you more space for you to see let's see for example the First Dimension uh which is this one zero so in the First Dimension which is the first column the result of this Dimension is another array so this is the interesting thing about using the debug visualizer for you to see this uh more complex visualization of your Matrix so uh if you look it from this perspective what we are using here and ass sorted array is essentially we are capturing this array over here we're focusing and zooming in into only one dimension of that Matrix which is the first column right it could be any one of these other matrixes over here the difference between this one zero and this one is that this is the first column and this is the second column right so since we've requested the zero one which is represents the First Column that's the array that's uh over and then uh it's essentially going to perform Let me uh resume the debugging execution so what's going to happen here is that the code is going to read all the elements of the First Column and then is going to perform the sorting and if you remember the episode of arrays and if you look here to the suggested code basically what this code is doing is an impementation of the algorithm called bubble sort right and why is easy to remember because bubble sort this its characteristics is a has a simpler implementation is a essentially a a nested Loop of of some sort of and that is basically swapping the elements and then we're going to once this inner loop new created array is sorted we're basically going to replace the the the elements of the existing Matrix with this sort of array so again create a new array read the existing values do the sorting and then we're going to replace do a implace replacing is that the the proper way to do it let me know here in the comments that if the way I said that out loud is correct but it seems to be the case it sounds redundant but it isn't like we're doing a in place meaning that we're doing inside the structur replacing of the values right so so things to be correct uh now let's do another interin exercise that has to do with data visualization as well but has to do with how we're going to print the values of the Matrix right one very popular uh problem that interviewers like to explore in coding interviews is how you can think of a matrix in terms of like a Dimensions uh first of all like a Matrix what is the Matrix is a two-dimensional array right the First Dimension is the columns the second dimensions are the the the roles so the problem statement usually like uh create an algorithm that's going to print the values of the existing Matrix very similar to what we have done here so the print Matrix but this is what we call printing the values of the Matrix and their natural order right so the way they're sitting there in The Matrix is going the way is going to be printed the problem statement that interviewers like to explore is print the values of the existing mat in a spiral order so spiral is that shape that go into like different circles that keep like getting smaller and smaller and smaller uh and then that is the type of output that they want for you to implement the algorithm to so uh let's see how the implementation goes I'm going to execute the code so you can see what anire irro looks like and then we can review the code from that right so I'm going to create a code here right below the print M Matrix methods I'm going to use code whisper to create a method to print the Matrix values in a spiral format right so I'm strictly giving the directions about what I need to do I'm going to hit enter and then let's see how the implementation goes uh um all right yep brain spiral the method signature is correct I'm going to hit enter and let's see how this goes um could whisper it thinking about what to suggest okay all right the implementation sounds a bit sophisticated but since we have no we have actually Four suggestions of it so one two three and four okay this one doesn't look what I need but this one here sounds to be what we need so I'm going to get that one we can always accept one and then if it's not correct we can simply go back to the other one I'm going to hit enter okay okay I'm going to hit close this one close this one and essentially it's printing this so I'm the only thing I'm going to do is removing this printing here right uh no actually I don't need to remove this printing because what this this method that's the interesting way for you to work with Amazon code whisper we you gave it your intention you accepted the implementation and at a given point in time your mental model is going to think oh no no I'm going to get rid of this like whole printing here but again code whisper is doing this suggestion for a reason because hey you to print this right so this is code whisper suggesting that you have to kind of a give some uh row spaces in between it inter direction of the the loop so I'm going to keep the suggest I'm going to trust C whisper that is going to do what he supposed to do uh just like we did before let's skip the reading of the algorithms for now let's just see how this goes and then we can go back to the to the code uh let me go to the main method here I'm going to remove this breakpoint and then in the main method uh let's actually remove the sore column we verified that sore column is working as as expected so instead of this we're going to ask print Matrix print spiral yeah that's what we need and we're going to remove that last print Matrix so what the code is doing now is create a matrix initialize print the one again like I said printing in in this natural form and a space for us to see the difference visually about the the difference and then print in a spiral let's clear the output and run the code to see if it's doing what it's supposed to do uh we're going to click run and then all right so let's see how this is doing so if you look this is how you should look an aspiral in a matrix so ins spiral is basically going to start right reading the elements like this it's going to 5 3 9 48 which seems to be the case 5 3 9 48 and then once it hits the end of the last column is going to start reading down so 8 9814 so 48 and then 9 9814 so is reading right here down and then the next one's going to be like this 7 212 so 7 212 that sounds correct and then once it hits the beginning of the matrix it's going to be 4 92 uh so let me yeah four so here's the thing it's not four okay let me I I lost my count so two and then four 8 three so what is doing here four8 oh no here yes so that's that's correct so it's now it's going to do a transer 483 see here and then it's going to 7 yes 483 now is is kind of a like in a diagonal or orientation is for 483 is doing like this right so here's the count of 483 and now 729 so 729 so now it's going down again but look now you're not going down considering the last column it has to be one column before because the last column has been red in the first Direction so it's the spiral remember is it's supposed to be going down and going inner inner inner in the loop so 7 29 and then it's going to 24 go up again right so 2 four which is this one and this one so it did this exercise beautifully which is doing this doing go down go this going a transversal and then moving to the right center which is the last four over here of the Matrix so that's what an inspiral printing of the values of a matrix look like so remember that you have to kind of do this exercise when you look for the implementation of the algorithm this way visually right it it start to make more sense one of the things that at least is tricky for me when I got like questions like this in a live interview especially is that you you have to be like a very articulated with and first kind of a imagine data algorithm data circuit is ultim an exercise imagination you have to imagine how the structur and the output would look like and then you go from there right so always when you were studying algorithms that the Circ try to do this kind of imagination exercise imagine the D cery imagine this representation imagine it a stery and this is where the debug visualizer can help you a lot with some data steres but now that we've seen that the output is correct let's go back to the implementation and review the code so essentially let me get rid of the console for a second it's taking too much space all right okay so what the codee's doing is all right it it have variables for you to remember what is the row start and the column starts and where is the column end and the row end so it always have kind of a this reminders about where you already read and then you have to kind of a move inner and inner so there's going to be this kind of outer loop that's going to always keep reminded okay keep in mind that for every iteration you have to keep of getting away from the uh the edges of the rows and the columns so it's always checking if the row is the end of the row or the column is the end of the columns and then you were going to have inner Loops to transverse the either a given column or a given row that that you were reading and then it's going to kind of a change and mutate these uh reminders here to kind of a keep adjusting the Precision of your spiral iteration so the algorithm seems to be doing what it's supposed to do so it's it's it's doing fine uh now let's check one more kind of a problem that you may see in a coding interview and it seems to be like a complicated problem but you're going to see that's that's one of the most obvious one that you can possibly be able to solve right so the problem statement is usually started like this like a how would you check if the matrix it's a square one right so in the beginning of this uh implementation part I kind of a gave away what a square Matrix looks like and a square Matrix for you to know is basically a matrix where the number of columns match the number of rows so basically what your algorithm supposed to do is to check if this equals to this is that simple right uh so let's see if this is the case I'm going to ask code whisper to create uh create a method to check if the Matrix is a square one I think that's a good problem statement that's going to be the right prompt for code Whisperer so I'm going to hit enter and yep yep exactly that's the that this this is it so is a square is basically is going to check if the Matrix length is which is the column right numbers of columns remember the first dimension of a matrix is always the columns and then it's going to check if the it matches with the first row which is another array and it's going to check the length of this array if it matches with the number of columns so if it matches yeah it's a square so I'm going to do this I'm going to remove pry if it's a spiral and I'm going to Simply nope I want to print spiral Matrix and then check if it say a spiral yes Matrix is a square not spiral it's Square Matrix and I'm going to put a question mark here like if I'm asking it is it square or not so let me execute the code and then is going to print it and say is a square Matrix true yeah because it has uh four four columns and four rows now let's go back to that implementation where we've added a new uh which one we had which exercise we remove a column right yes let's speak this one let's remove a column after checking if the Matrix is a square so matrix. remove column so we've just remove a column we've changed we've did an in place changing of the stry of the Matrix and then we're going to ask again if considering this new mutation of the of this The Matrix if it still look like um a square Matrix right so recap the implementation we're going to print it and then we're going to ask if it's Square we're going to remove the column and then see if this two holds true so let's clear the output and I'm going to click run and yep seems to be the case right so it first create a matrix initialize with the values it is a square mat true and then we remove the last column and why is saying here that's false because now since we've removed the column this value here is going to be smaller than the result of this value over here so this whole verification here will return false so uh it's a simple implementation right you basically are comparing the uh the length of the the number of columns with the you retrieve the first row of that Matrix and then you compare the length of it with the number of columns but it is a powerful verification because the the interview is want you to verify how much you can like create this mental model of not only kind of visualize that what what is a square um what is a known Square Matrix like a known Square Matrix let's say you have have a a table with five columns and 20 rows right so mentally and Visually this is going to look like more like a rectangle right then a square right because it's going to be like a it's going to be like this like this number of columns but a very long number of rows or it can do the other way around you have like a three rows and a bunch of columns so still it's going to be like a rectangle a perfect square Matrix is the one we have five rows and then you're going to have like f sorry five columns and then you're going to have like five rows so this is how you verify visually but more importantly it also wants to the interview wants you to know verify how much you know how this visual representation looks like in a structure level because you are being tested and understanding of the Matrix data structure let's wrap up what you have seen in this episode matrixes are a two dimensional data structur use it to store and manipulate arrays in a Tabler form it allows for efficient storage and retrieval of data just like arrays adding and removing elements require changing the stery of the Matrix because their size is fixed this is particularly true for large matrices containing manual roles where adding a new rle becomes computationally expensive therefore matrixes are ideal for scenarios where is read only such as calculations and data visualization my suggestion for you is to keep practicing different sorting algorithms with matrixes and use Amazon code Whisperer to assist you with the code generation then spend some time studying the generated code and whenever applicable criticize and correct the code in the next episode of this series we will take a look at the notorious linked list if you started watching this series from the playlist the next video about linked lists should start pretty soon if not I put the link of the next video in the description below see you in a bit