Array of Objects to Matrix - Leetcode 2675 - JavaScript 30-Day Challenge

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem array of objects to Matrix so this is definitely a difficult problem basically we are given some object that could be highly nested and we want to sort of flatten it this is kind of analogous to taking like a document in a document like database and converting it to SQL or like a relational database or like in the form of a table and we know tables are of course two-dimensional and the word Matrix is Itself by definition is two-dimensional so there is some practicality to this problem I will mention though that it's not like a one-to-one mapping like we'll first take a look at some of the examples on what exactly we're trying to do so basically every single key value is going to be a value in the first row so we want to take every single key value in any of the objects in this case we have a list of two objects and there's only two keys A and B and all of those are going to go in the first row and they need to be be sorted as well that should be pretty easy for us if we can find all the keys and the following rows of the output the next one is basically going to be all of the values in the first object the next row is going to be all of the values in the second object and they need to be ordered by the key so here we can see a maps to 2 so 2 is going to be in the first position even though it's in the second position in the object and the second object a maps to four so it's going to be here now you might be thinking what if not every key is in every single object in this array well thankfully they do have some examples for that this second example is an interesting one all of the keys are a b c and d so we add those to the first row even though some of the keys show up in the first object some of them show up in the second in the first object a maps to one B maps to two but C and D don't show up so we put an empty string in the output for that now this is kind of the first hint that it's not reversible what we're doing here if we get like the two-dimensional Matrix we can't reverse this back to to the object because how do we distinguish between whether in the first object C did not appear at all therefore there's an empty string or maybe C actually did appear in the first object but it just happened to map to an empty string see we can't distinguish that so therefore this operation that we're doing here is not really reversible and there are other reasons for that as well that I won't really spend too much time on but the second example shows us on the nested scenario where a doesn't map to a value it's not a primitive it's actually another object and of course objects have keys so what would we do would we just consider B and C as keys in the first row not quite because that doesn't give us all the information we know that we started with an a key and then we took a second key B so therefore we put a period in between them and similarly over here and we could you know be nested even further there could be B maps to another object then we'd have to put a period behind B and then add like the following key as well so that kind of gives you a hint that this problem is going to to possibly be solved with recursion and that's how I'm going to solve it the fourth example is also interesting because they not only tell us that we could be given an array of objects we could also be given an array of arrays arrays are kind of like objects it's just the differences that the key is going to be the index in this case so this array basically think of this as being Rewritten like this on the right hand side where instead of being an array it's actually this it's an object where the key just happens to be zero and it maps to this object so these are sort of equivalent here this one is a bit more representative and it makes it more obvious that we're going to be starting with the zero here and of course we could have others as well we could have an array of multiple and therefore we would go to one and it maps to some object and then maybe two maps to some object so basically I'm spending time on understanding the problem before we get into solving it because you really want to have a good understanding of the edge cases here so there's definitely a lot of way ways to solve this problem a sort of naive approach that you might first try is just try to map every key to a list of its values so you'd create an object and you would try mapping every key for example zero dot b to a list of all of the values that show up in the object but if you do do it this way you would have to for every object keep track of like maybe in the first object it maps to a one in the second object it maps to nothing therefore we would have to explicitly add this and that can get kind of tricky especially if we don't know beforehand what all of the keys happen to be if you don't believe me you can try it this way I won't go super in depth on why this is going to be kind of tricky but this is sort of a hint that it's going to be useful for us to have all of the keys beforehand so I'm going to actually create a helper function to do that we're going to get all of the keys from an object and we're going to be doing this recursively given some object we want to basically get all all the keys so what should we first do go through the list of keys that are available to us in that object and we also know it actually could be an array and this will actually work in that case as well we use the in operator which gives us all the keys if it's an array it will do pretty much what we want it to it'll start at zero then go to one etc etc but basically there are going to be two cases here either object using this key happens to be an actual object this is this will be the recursive case the else case is if it's not an object in which case we know we found a key and we want to add it to all the keys available and the easiest way I'm going to do that is just by creating sort of a global key set out here which is going to be basically a hash set in JavaScript so that we don't have duplicates and then in the else case what I'm going to say is in the key set just add the current key that we're looking at so that's simple enough but remember this could be recursive as we keep going down that chain of keys we want to accumulate all of the keys we have AKA we want the path of all of the keys so we're going to have a second variable here and initially when we call our get keys like this passing in the parameter that's given to us the array and passing in an empty string that's what we're going to start with of course as the path so then when we add to the key set we actually don't want to just add the current key we want to add the new current path that we're at which is I'm going to say like this and at first you might just think we'll take the existing path add a period and then add the current key that's not bad but on the first iteration of the get keys function before we do any recursion path is going to be empty we don't want a preceding period before the current key so we kind of have to know is this empty or is it not the way I like to do this is like with the ternary operator if this is empty then therefore we just want the current key if it's not empty then we want to do what we previously had and instead of using the addition operator I'm going to write it like like this where the path is going to be proceeding then we're going to have a period in between and then we're going to have the current key variable and that will be the New Path and then instead of adding the key we want to add the New Path down here now the recursive case first of all we have to know that this is an object how do we know if it's an object well we can say type of but I'm actually going to create a helper function for that below for is object because we know null also evaluates to an object and when we have null we definitely don't want to execute the recursive case we want to execute this case so let's given some object be able to determine if it's null or not so if and actually we can just return this if object or object is not equal to null and the type of this object is equal to the string object then we'll know if this is an object and if it is we want to do the actual recursive case which we can call get keys we're going to pass in this a new object and then we want to update the path while we already have the New Path so we can just pass that in and remember the get keys we don't care about the return value we don't even need to return anything here because it's updating the key set which is not necessarily Global but it's outside of the scope of this function so we do have access to it the shared instance so I think this get keys is pretty much complete but if I call get keys on the array it's actually going to be a problem because remember we're given an array of objects like this so the first key iterating through this array is going to end up being zero but we don't care about that we care about the actual keys in the objects themselves like A1 Maps there if I call get keys on this array we're going to end up with a preceding zero for all of these we're gonna end up with a preceding one for all the keys in here we're going to end up with something like this that's a problem and I know that because that's what I tried initially so to fix it we actually want to go through every object in the array and actually we do that with the of operator that's always confusing for me and for every object then we want to call get keys and it's okay if we end up with duplicates because our key set will remove all of the duplicates but after we have generated that we do want to convert it to a list because we do need to sort it so in JavaScript it's pretty easy to do that you don't just call the array Constructor though that would be too easy we call array from passing in the key set so this gives us an array then we want to sort that array like this and then we can assign that to our keys and there we go so all we've done so far is basically built the first row so I'm going to create our result which we know is going to be a matrix so it's going to be an array where the first row is the keys so then of course the only thing left for us to do is actually get the values for the remaining rows and for that we're going to actually write a second helper function which is going going to be get values and similar to the first one it's going to take an object and it's going to take a path and we're going to recursively find every single value in each object now before I actually implement this I'm going to show you it's going to be called similarly to the get keys over here we're going to go through every object in the array and we could naively just get every value and put it into an array but we know that remember these values also have to be in the same relative order as the keys so the easiest way that I know to do that is to do it in two steps so we're gonna have this creating a map key to Value so we're going to get every single value and put it in this object mapping each key to the value now the order of these might not be exactly what we're looking for and after we've done that we're going to go through every key in our list of keys because those are the ones that are actually sorted in an order up here and then for every single key even the ones that not didn't necessarily have a value in this current object we're going to push something to the current row that we're going to be building so let's declare that up here and we're going to check if else like basically if this key is in the key to Value map then we're going to say row push whatever the value happened to be and we can get that from the map itself like this otherwise we know that the default thing that we want to push is an empty string and the reason this works is because remember even though we're doing this recursively we're pretty much guaranteed in any object a single key can only map to one value you might think well a key can map to an array but remember we're not just talking about a single key we are joining the keys recursively with like a period in between them so if a value was in an array we'd say well that key is going to be key dot 0 0 or maybe key.1 key.2 so each key will uniquely map to a single value in any single object and of course after we build a row we can push it to the result so a result dot push that row now the only thing left to do here is before we start doing all of this we expect the key to Value map to actually be populated and that's what get values is going to do we're going to pass in an object we're going to pass in the path and the third parameter we're going to pass in is the to Value because this is not necessarily accessible from the function that we've defined over here if we had to find key to Value up here like we did with key set then it would have been accessible the reason I'm doing it this way is we basically want to initialize an empty key to Value map for every single object in that array and this is kind of an easy way to do that so now get to values let's fill it out and remember the third parameter is going to be key to value and this is going to be similar to the above function where we're going to go through every key in the object we're going to declare the New Path similarly because we do care about the path that's going to tell us what the key is so if the key is null if the current path isn't all then it's just going to be the key otherwise I'm just going to copy and paste over here and similarly if this is an object then we do the recursive case so we want to check if the current e maps to an actual object or if it maps to A Primitive if it's a primitive that's going to be the base case for us where we say now key to Value the current key which is not just the key it's going to be the path the entire path the New Path maps to this object which we know now is a primitive otherwise we call get values recursively passing in the current object passing in the New Path and passing in the key to Value object which isn't really going to change we're just passing that in because we need this to pass it in to actually access that so since we already pretty much called this get values method up above and did everything correctly I think the only thing left for us now to do is actually return the result and I'm just going to do that up here you can see obviously I'm doing that before the function declarations down here that's perfectly fine because remember because of hoisting we can still call these functions because they're declared with the function keyword and of course I did have a bug path over here remember when we call it the first time we're just passing in an empty string because that's what the path is okay unfortunately I had another bug my ternary operators were in Reverse if the path is not null then we want to actually put the path as the prefix but if it is null then we just want to take the key so I think I did this with the python ordering because I'm used to doing holy code problems in Python so let me just reverse the order of these sorry if that was confusing and then I'm just going to copy and paste this one and move it up above and speaking of python unfortunately I use the in keyword over here when we're going through an array of values which that's what this is an array of objects I guess we want to use of if we use in it'll give us the index or the key and that's why we're using it when we're iterating through objects and we actually want the key but in this case we don't want the key we want the actual object and we probably want to make that same adjustment over here because Keys is an array and we want every value in that array you can probably tell I don't really love the way that we iterate through things in JavaScript but now let's run this to make sure that it works and as you can see yes it does and it's pretty efficient if you found this helpful please like And subscribe thanks for watching and I'll see you soon