Longest Turbulent Array - Leetcode 978 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem longest turbulent subarray we're given an integer subarray and we want to return the length of the maximum size turbulent subarray from the given input array now what exactly is a turbulent array well it's best understood with an example so let me first draw it out using this example that they gave us and I'll show you how simple this problem really is so let's say that this is our input sub array for every adjacent pair of values there's some equality between them either this one is going to be greater which is true in this case or we could have the opposite case where the right value is greater or we could even have a third case where adjacent values are equal to each other every pair of values every adjacent pair of values is going to have some equality between them I'll quickly draw them out here we can see 4 is greater than 2 10 is greater than 7 8 is greater than seven eight is greater than one and nine is greater than one all we want to do is return the longest subarray well not the actual sub array itself but the length of the sub Ray such that we have the longest alternating streak between equality signs what I mean by that is no matter how we start for example here we start with a greater than sign then for the rest of the sequence the sign has to be alternating like the equality has to be alternating first it was greater than now it's going to be less than then it's going to be greater than and then it's going to be less than now for equal we don't count that so a turbulent array as defined by this problem is alternating between greater than or less than signs one more point of clarification here we have four signs but we're not counting the signs themselves these signs form this array where we have one two three four five values and we return five you can see that down here so why couldn't we also include the first value over here well take a look at the signs we started with greater than that's fine but then we had a second greater than in a row that's not what we were looking for at that point we can't include this anymore this is the longest turbulent sub array well these first two values where we can start at this value so thinking about it this way the problem becomes pretty simple we're just looking at this array we want to find that optimal longest turbulent array which is this one in this case we can't extend it further over here now technically this is also a turbulent array it has three values in it but that's not what we're looking for we have a longer one which is five over here so how can we solve this problem efficiently because when we're talking about sub-arrays we know we can Brute Force this by just checking every single sub array and do that in N squared time because that's how many sub arrays there are going to be so how do we do even better well when we get here the first two values we are good so far it's sort of like a sliding window technique or you could say this is pretty similar to cadane's algorithm I kind of think of them as overlapping because they're very similar but yeah sliding window we're gonna try to grow our window as much as we can but when we can't grow it anymore let's see if there's any patterns we can identify to eliminate any repeated work starting at these two guys there's some equality between them the only problem would be as if there was an equal between them at that point we would be able to say this is not even of length two but since there is equality between them this is a valid turbulent subarray of length two but now when we introduce another value at this point we wouldn't initialize our pointers like this by the way we'd have a left pointer and a right pointer for our sliding window and then we would shift the right pointer over here now we're comparing these two values we're always going to compare the value at Index right with Index right minus 1 which is over here so now we look at this and we see that the problem here is that our previous one was a greater than and right now again we have a greater than sign that's not what we wanted we can't say that this is a turbulent sub array so what do we say we found the longest one starting at this position but now we have to start over we're going to now start at the next position over here at this left index and our right pointer which was over here is now going to be shifted to the right by one so now our right pointer is going to be over here so now we keep track that the previous sign that we saw was a greater than sign and now we compare are right with Index right minus one so we look at this equality sign now it's less than well I don't even know I think this one is called greater than this one is called less than but the point is that they're different this is a valid turbulent subarray now we go one more time over here we see again that they are opposites so this is also a valid turbulent subarray we go one more time our right pointer is over here compare these two see the sign it's the opposite which is good so these are continuing to be turbulent sub arrays finally here though and this is going to be interesting we get the equality so not only is it different than the previous one but it is an equality sign which we are going to handle in a special way I'll show you how the first thing is that this is not a turbulent subarray so now what should we do should we now try to find the longest turbulent sub array starting at this position we already found the longest one starting at this position that's this guy of length five so now should we start over here well definitely not because if this whole thing is a turbulent subarray then we know for sure and we're not including like this a rightmost value but if this whole thing is a turbulent subarray then for sure this is going to be a turbulent subarray because if all of these are alternating then of course a subset of them are also going to be alternating we're basically saying that for a turbulent subarray any sub-array of that turbulent subarray is also going to be turbulent so that's why we can use the sliding window at this point I would take the left pointer and not just shift it by one but I would shift it all the way over here now our right pointer is already here I'm going to move the left pointer over here as well and we're also going to shift the right pointer by one over here so we would have this subarray and it is turbulent because it's different than the previous value which was well the previous equality which was equals this one is greater than and at that point our algorithm would continue as normal now the one thing I want to say that's different about the equality here what if instead of this being an equals we just had another less than sign well in that case our right pointer is already over here but we would actually want our left pointer from over here not to be shifted all the way over here because then our left pointer would be here and then we'd increment the right pointer to be over here and then we would check this but that would be a problem because in that case we would have missed this subarray we would have just skipped all the way to here so when there's an actual greater than or less than in that case we don't want to skip all the way to the right index we don't want to take our left pointer and then shift it to the right index we want to stop at right minus one so we would normally stop here if this is not an equal sign but if this is an equal sign then we don't shift the left pointer over here and the right pointer over here because this is not even like a valid turbulent Subaru even though it's just two values it's not valid so we would just want to skip this one all together but that's the main idea it's basically a sliding window problem at its core so the time complexity is Big O of n it's a linear time algorithm and the space complexity is O of one because we don't need any additional data structures so now let's code this up so as I said I'm going to first initialize my pointers a left pointer to zero and a right pointer to one I'm gonna also initialize our result and the previous sign so initially I'm going to set the result which is the length of the maximum size turbulent subarray to B1 B because we're guaranteed that the input array is going to be non-empty and a single value does count as a turbulent subarray so I think one is a good initial value and I'm going to set the previous sign equal to the empty string it can also end up being the greater than sine or the less than sign or just empty as well I'll show you how that's going to be used in a bit we're also going to take our right pointer and just iterate it through the entire length of the array there's a couple cases if array at index R is greater than the array at the previous index or actually I'm going to write it the other way I'm going to write the smaller or the previous value to the left because this is how we're going to use our equality signs but if the previous value is greater and the previous sign was not equal to the greater sign meaning that it was was either empty meaning that we basically started at the beginning of the array or that it was the less than sign this is good because that means our array is turbulent so at that point what we would do is possibly update our results so we would set it to the max of itself and the length of the current sub array which would be right minus left plus one we would also want to increment the right pointer by one and we should update the previous character now to be equal to greater than because that is what we have here so this is just one of the cases with my solution there is going to be some code duplication I could write it a more concise way but I think the way I'm going to write it now is going to be very clear on what the solution is because we have these equalities I think this code is going to be really easy to read and it's going to be pretty easy to write as well because this was one of the cases now I'm going to just copy and paste this and get the other case else if we had the opposite of this meaning if the current value is greater and the previous sign was not the greater sign or you know whatever you call this then we would basically do the same thing here the only difference is we would change the previous character to be the opposite one and the third case here is either we had consecutive signs or we saw an equal sign in either case we want to set the previous to be something else we could set it to be equal or we could just set it to be like an empty string it doesn't really make a difference because the way we're actually using it here is we're only checking if it's not equal to this or not equal to this so we can just keep it simple here the other case is remember the right pointer if they were equal signs that we saw or if the two adjacent values were equal then we want to increment our right pointer so if a array of at write indexes equal to array at right minus one then we want to set right to right plus one else we leave it as it is and regardless of how we update these we always want the left pointer to be equal to right minus one if we are updating our sliding window if you know this condition executed this part I admit is probably the most confusing about this solution but it has to do with how we want to handle equal signs basically we want to skip them all together this is the entire code you can see all we really have to do is keep track of the previous character that's giving us all the information we need the rest of it is pretty much just duplication we're just updating previous three times we are updating the result a few times and just incrementing our pointers a few times as well after that's done all we have to do is return the result and let's run this to make sure that it works and as you can see yes it does it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon