Make Two Arrays Equal by Reversing Subarrays - Leetcode 1460 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem make two arrays equal by reversing subarrays so this is an easy problem and at first glance you might be wondering why it seems a little difficult for an easy problem but I'm going to show you that there's a pretty simple way to think about this problem basically the idea is we're given two arrays they're always going to be of the same length so we don't have to worry about that but we basically want to take elements I guess they say the second array and we can choose any sub array so it could start from the beginning or it could go through the middle whatever any subarray and then reverse those numbers so we want to know can we turn this array into the original array and this example we actually can so it's not super obvious how but firstly we take these first three elements and reverse them I think then we get 1 4 2 3 and just so you know the target array is just 1 2 3 4 so we're trying to kind of get it in sorted order at least in this example so next I think we can swap these two and then we'll get 1 2 4 3 and then we can swap the last two and then we'll have 1 2 3 4 so it seems kind of difficult I mean to brute force it there's going to be a lot of possible subarrays but when you're clever you can think about it in terms of this we just want every single element let's start with one we want one to go in the beginning we want to get it over here doesn't really matter where the rest of the elements are after that we want to get two in the second position then we want to get three in the third position and four in the last position the easiest way to do this is just take this element and just keep swapping it with its left neighbor so that would end up looking something like this 1 2 4 and then three so now two is already in the right spot and then we could swap these two the way I'm thinking about this is definitely not going to minimize the number of like reversing subarrays or anything like that but we're not asked to minimize it we just want to know can we actually form the target array so at this point it's not a matter of how we swap the elements it's only a matter of do we actually have all the elements in the second array that we have in the first array basically we're asking is regardless of the order of these two arrays are these arrays equal I'm sure you already know this cuz you've definitely gone through the ne code 150 list and you're probably tired of me even mentioning this but once again NE code 150 I always talk about it because it always comes up this is pretty much the exact same problem as valid anagram and so the solution is going to be similar I'll quickly mention the trivial solution we can just take both arrays and sort them which is going to be n log n time both of the arrays are of equal length and then after we sort them we can just check if they are both equal to each other that's not the most efficient solution though the most efficient solution is going to be about counting the elements in each array because we could technically have duplicates we might have multiple fours we might have multiple ones so we want to know does the count of every single element in each array match the count in the other array so counting is generally done with a hashmap so that's how I'm going to do this so if we were to create a hashmap of both of these we' see that one has a count of one in this case two has a count of one three has a count of one and four has a count of one as well obviously we could have you know some elements with multiple like we could have three twos we could have four threes something like that and then we'd have the second hashmap and we would just want to check are the elements in every single hashmap equal and also that there aren't any keys in the other hashmap that don't exist in both hashmaps visually I think this is pretty simple to understand but coding it up might be a little bit tricky so let's get into that this is going to be a linear time solution though because we're just going to be iterating over both inputs and then building the hashmap hash maps have constant operations for every single thing so that's why it's efficient and space complexity is going to be for the hashmap as well so first let me actually just show you the most trivial way to code this up python makes it so easy so we can do something called a counter on the target array and we can do counter on the second array this is basically building a hashmap counting the occurrences of each element and for us to check if these are exactly equal well python makes that pretty easy too just use the equal sign so we can just return this so that's the oneliner solution to this I know you might consider it cheating but I do feel it's worth mentioning because it does work but maybe in a real interview you will be asked to elaborate on these you might be asked to implement the counter yourself so let's actually get into that let's say we have count one and count 2 and both of these are going to be hashmaps and they're going to be default dictionaries so the default value is going to be an integer that's going to make things slightly easier for us so what we're going to do is iterate over both arrays python makes that pretty easy we can iterate over both of them at the same time using something like this for N1 N2 IN Zip the target array and the other array I if you wanted to do this the original way you could do something like this for I in range length of Target because we know both of them are the same and then to get N1 you could just do something like Target at index I to get N2 you could do something like array at indexi so this is equivalent to this this is obviously a little bit shorter you can learn exactly how to do that in my I think python for coding interviews course we just want to take let's say the elements from Target which is going to be N1 is going to correspond to count one so we're going to do this increment it by one same thing for count two we're going to take N2 and increment that by one the reason I made these default dictionaries is here this is basically the same as doing a count one like N1 is equal to itself plus one obviously if the key doesn't exist in the hashmap already with a regular hashmap we would get a key error but with default dictionaries it'll return zero as the default value because we specified it as an integer again I think this this is also covered in Python for coding interviews but now we want to check that both of these are equal the first thing we're going to check is that the length of both of them are equal because even though the length of the input arrays were equal we also want to check that the distinct elements in both of these are also equal now that we've kind of eliminated duplicates so let's check length of count one is not equal to count 2 in that case let's return false otherwise before we're allowed to return true we also have to check that the count of each element is equal so let's just go through all the keys in one of the hashmaps so n in count one and if the count is not equal to the same element in count two then we would return false and the fact that we have the length check up here we'll make sure that if these two hash maps are not equal this will eventually evaluate to false because we know both of the inputs were of the same length so if they have the same number of distinct elements the count of all of them should be equal if they are equal otherwise the count is going to differ at some point and in that case we would return false so if these don't return false we return true and you can see that this will also work but there actually is a way to get this down to just using a single hashmap so let me kind of optimize this just a tiny bit let's just have a single hashmap let's call it count we're going to do the same thing up here but with the first element we're going to increment the count of that with count from the second element with the same hashmap we're actually going to decrement the count so you might be able to see where I'm going with this we don't need the length check anymore but we do need to go through every key in the hashmap and we need to make sure that the length is equal to zero because if it's not equal to zero at any of the keys that means that either we had extra elements in the first Target or we had some extra elements here it could be positive or it could be negative but it should be zero so if it's not zero we would return false otherwise down here we return true so let's just run this and you can see that also works these run times are pretty random all of the solutions I showed you had actually the same time and space complexity obviously this one only used one hashmap but the big o space complexity is still technically the same if you found this helpful check out n code. thanks for watching and I'll see you soon