Check if Array Is Sorted and Rotated - Leetcode 1752 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem check if array is sorted and rotated so before we get into this problem today I want to mention a couple quick things even though this is an easy problem there's another easy problem that I would solve before you solve this one and depending on what order like these problems are going to be like released on in terms of like the daily problems maybe yesterday's problem was the one that I'm already talking about and in case you're wondering how I know what the daily problems are going to be in advance I guess I'll just tell you guys at this point if you are logged in and you go to the leak code homepage and you kind of just scroll through this feed what you'll notice is that leak code releases editorials in this feed and it kind of tells you which problem an editorial was released for so I see that Leo just created these two editorials I know that these are going to be the daily problems at some point I just don't know exactly which day they're going to happen but I know they're going to happen eventually um the problem that I'm talking about by the way is this one maximum ascending subra sum it's also an easy problem and I think in some ways it makes today's problem like slightly easier but anyways I kind of just feel like I told a kid that Santa Claus isn't real so I'm really sorry if I just like ruined the illusion of the daily problem for you but anyways we got a problem for us today we're given an array that was originally sorted in non-decreasing order that pretty much just means ascending order but we could have duplicates so that's why they use the word non decreasing rather than ascending we could have some duplicates um so I'll even just add a duplicate in this example let me just throw a five in there so you can see if this is the array that we were given that must mean that the original array looked like this 1 2 3 4 5 five but what happened is the array was rotated what that basically means is we cut the array in half at some point so I think this point and then we took this part of the array and then moved it over there and so you can see that that kind of lines up with this part over here and I guess I misspoke earlier it's actually not guaranteed that we were given an array that was necessarily originally sorted but our goal is to determine if it was or not so for example just to be clear with this array we see that if we were to take this and then move it over there yes we would have had a sorted array so for the first example we would return true but the second example is a bit more interesting let me draw that one down here it's 2 1 3 4 no matter how you slice it this original array is not sorted if we split it like this and then we move the two over there it's still not sorted if we take this and then move it over there well it's definitely still not sorted there really isn't any way to make this sorted so for this example we would end up returning false so how do you go about solving a problem like this one well first of all I'm going to cover I guess at least one Brute Force way to implement this because this is an easy problem but then I'll show you a more optimal way to implement this and I would kind of argue that that optimal way is a little bit Advanced for an easy problem to be honest it's not a lot of code I just use a kind of technique that usually comes up more often in medium problems so in terms of Brute Force One possible Brute Force solution would just be uh to check if the original array is sorted and then pretty much what I talked about then try every pivot if the original array is not already sorted try this pivot that would mean creating a new array where these are the elements and then we take three and then move it after that so in other words you could just pop this element from the beginning and move it to the end obviously that would be an O of n operation but even if you were to do it the other way popping it from this side which would technically be constant moving it this way would still be a linear time operation and either way we are still going to have to scan through the entire array to determine if it's sorted in non-decreasing order anyways that's one way you pop this you move it over there is it sorted nope pop this move it over there is it sorted nope pop this keep doing that pop this one and then finally we do end up with a sorted array it should look something like that so that's one way to do it at each step we are doing a linear time operation and we are going to have at most n steps so n^2 is going to be the time complexity now can we do better yes we can let me show you at least one way that I thought of there's probably multiple ways to solve this problem though I think the editorial had a different solution but I kind of like my solution better when you're dealing with rotated problems one common technique is just to take the array itself and then concatenate it with itself in other words I'm going to end up with something that looks like this I have the original array and then I take the exact same elements and then I add them after that so this is the second copy of the array and it's combined into a single array this is kind of like the halfway point so why exactly did I do that because now I can solve this problem kind of with a sliding window well it's not technically a sliding window but to me it feels like a sliding window problem because consider this now I can do this I can say is this entire thing sorted nope okay is this entire thing sorted nope and just keep going like that and eventually I'll find this window over here which is sorted and at that point I can return true okay so that doesn't really look that much more efficient every window is of size n so it looks like I'm still going to be doing n squ steps in the worst case but that's where the sliding window comes in why not do something like this I'm going to change colors three and then check the next guy four okay so far we're in non increasing order then five okay keep going another five that's okay if two adjacent elements are equal that's perfectly fine but then we see the one one is smaller than five so that tells us that okay we were so close we had a length of four if we could have just found a window of size n which in this case is six we would have been good but we didn't find that so what do we do well we're going to restart our window now from this element since it's a one we have to throw away all of our previous work that's unfortunate but it's okay now we start at one and we look at two so far so good then we look at three then we look at four then we look at five and then we look at this last five we could keep going but n is already equal to six so this is how you know we found the solution and we can return true so this is a perfectly working solution but you can see it does require additional space so technically we're creating a new data structure it's going to be linear time and linear space but we actually don't need to create another data structure this is where the advanced technique comes in where technically these indices are this and technically I want to have my ey pointer at the beginning and I do want it to Traverse over this input but if I was at an index over here what would I do these ones are pretty easy to deal with because I could just say okay I'm at index 4 I could just reference the original array and see what is that index 4 in the original array but when I'm get over here I'm technically out of bounds of the original array but it's actually a very easy fix just take the index and mod it by the length of the original array which is half the length of the new array so in other words if I have my I index at 8 I just take eight and I mod it by six that giv gives me two and that tells me that this value is going to be the same value at index 2 in the original array and that is the case so using this technique we can actually eliminate the need to actually store these elements in memory we already know they're the exact same elements that are over here anyway so why should we store them this way we get the uh space complexity down to be constant that's how this is going to work and to mention I'm actually going to be starting my ey pointer at index one just because I want to compare this with the previous element and I want to keep track of the contiguous count the size of our window I'm always going to have the size of the window to at least be one because one element is technically in non-decreasing order but when I make the first comparison I'm going to compare I with index IUS one and if they're in non-decreasing order then I can bump this up by one and it'll now be two if I get to this point and I see okay now my window is no longer valid I will reset the C count back down to one so that we can start over from here and then compare these two together and then just keep going okay so now let's code it up so the first thing I'm going to do is just get the length of the input array nums and then I'm going to have my count variable like I said I'm going to set it to one initially and then I'm going to have my Loop I'm going to Loop starting from one all the way not to n but actually two * n this is how I'm kind of imitating having this array being concat ated with itself so what we would want to do is something like this if nums at index ius1 is less than or equal to the current number then we can increment our count otherwise we would reset it back down to be one if we ever get to a case where the count is equal to n then we can return true otherwise out here we would return false unfortunately there are actually a couple bugs with this approach maybe you can point them out but I'll just tell you what they are first of all we forgot here to do the modding because we might end up out of bounds 2 * n that doesn't exist in the original array so that's why here we have to add the mod by n and same thing over here take this and mod it by n the other bug and this is more of an edge case what if the array was of size one well this Loop would not execute we don't even have a chance to return true and even more than that if n is equal to one well then we would want to return true no matter what so here you could do something like this n equal 1 return true or you could actually even just update the statement we have down here to be n is equal to 1 then return true otherwise this will return false which is what we intended to do so I'll run this now you can see here it works it's pretty efficient if you found this helpful check out n code. for a lot more I'll see you soon