this problem is probably the hardest I've ever attempted to solve I'm not even kidding I think this is honestly not Elite code hard I think this is a different class of problems I think super hard I've never done code forces but I assume that this is kind of the caliber of problems you see on code forces hopefully I think you at least learned like how I kind of approach problems this one I will admit was too hard for me and the reason I don't feel bad about it so I was reading this AMA on code forces from Scott woo I recently made a video about him if you don't know who he is he's basically a competitive programmer really really good one of the best of all time he's also more widely known for creating Devon the AI software engineer but we're not talking about that today I thought this response from him was pretty interesting as it relates to getting good at competitive programming which is very similar to you know getting good at Elite code at least you know Elite code is easier than competitive programming let me just say that I'm not a competitive programmer hey Scott what's the appropriate amount of time one should spend on some problem before giving up on doing it at all by themselves and look at the tutorial instead some people say 15 to 20 minutes max some people say a long time but his response was really interesting to me and even kind of surprising this is an interesting one it seems like a lot of people recommend waiting and thinking more but personally I look at editorials as soon as I get stuck the key piece though is to make sure to connect the motivation of the solution how could I make the Insight that leads to disc discover discovering the solution is a separate question from what is the solution and it's important to think about the former as well so what he's saying is understanding the solution like sliding window backtracking DFS whatever knowing the algorithm is good that's necessary it's important you have to do it but it's easier than understanding why when I make videos that's what I try to do of course I show you the code it runs usually usually but I try to explain why you probably know that the first part of what he says he doesn't spend a lot of time thinking about it that was really interesting to me because when I started leak code I would spend like five hours on one problem I just thought that's the only way to learn but no even this guy this guy's a genius if you watch that other video this guy is a literal Prodigy he doesn't even waste his time he's not even like you I'm not going to spend a few hours on this maybe he wouldn't be able to figure it out some problems are pretty damn insane right there are some Geniuses out there it took them weeks months to come up with certain algorithms why would he want to ReDiscover that why would he want to reinvent the wheel when that's not his priority he's not trying to invent new algorithms he's trying to get good at competitive programming so when you're trying to get good at leak code there's no shame in looking at a solution okay you didn't derive you know the shortest path algorithm by yourself don't feel bad about that look at the solution okay fine but understand it knowing all of that I think it'd be kind of interesting if I showed you how I approach a new problem a new problem that I probably won't be able to solve solve let's do it so let's go to leak code up the difficulty let's go to some of these hard problems sort them based on difficulty so let's try uh this one minimum reverse operations because it's a relatively recent problem 2600 I guess I could try that one as well and lucky for us this problem doesn't even have an editorial let's see what's going to happen minimum reverse operations we're given an integer n integer p in the range 0 to n minus one representing zero indexed array of length n okay n is that this is some live problem solving that you're seeing from me all positions are set to zeros except position P which is set to one okay so binary array interesting I'm kind of just looking at the example okay looks like this is different than what they are talking about so we're going to need some more context I guess n and p are representing arrays they're not necessarily arrays which is funny why do they even give us this if there's no parameter so this is me getting mad because leak code problem descriptions are really annoying okay given an integer array band containing some positions from the array the I position in band array of the I position is equal to zero and band of I is not equal to P so what this is basically telling us that every value in band is not going to be equal to P because if it was equal to P we know that P tells us the index where the value is set to one so this is just an over complicated way so that's hard problems for you really over complicated descriptions you can perform multiple operations on the array in an operation you can choose a subarray with size K and reverse the subarray however the one in Array should never go to any of the positions in band now I'm getting to the point where I realize that me talking to you guys as I'm explaining this is making it harder for me because if I had read this part before trying to understand this I would have gone faster so this is a little bit of the thought process because now we realize that band just tells us every position in the input array that the one is not allowed to be at and initially we know one will not be at any of those band position positions return an array answer where for each I in the range answer over I is the minimum okay so at this point I know that the result is going to be of size n so let's just initialize an array like this this way it's kind of like us taking notes here and then we know this is what we're going to return at least we have a little bit of the starter code set up this is the minimum number of reverse operations needed to bring one to position I in the array or 1 if it's impossible we know for when it's impossible I'm again just going to do what I know so far but in some cases like in a real coding interview I probably wouldn't start coding immediately though I don't think this is bad I mean this isn't real code this is just kind of this is the same as taking comments for example but now I know band tells us the impossible positions so I'm going to go through for B in band I'm going to say result at B is going to be equal to ne1 this tells us this position can never have a proper result a subrise continuous B the values of answer of I are independent for All Eyes the reverse of an array is an array containing the values in reverse order okay I don't even know why I read that okay so now examples matter I don't even know half of what this problem is even asking yet to this point just quickly reading the constraints nothing special I assume band is going to be smaller than n okay they do confirm that here it's going to be less than or equal to n minus one and of course they're all going to be inbounds okay so we don't worry about any of these crazy things let's look at an example now this is where I start to whiteboard or start to do comments so to make this easier for you guys to understand visually let me try to draw it out I remember the problem description so I'm not going to focus on that I'm going to focus on the example so we know size array of size four p is the position where the one is so we have this binary array and we have an array band I'm not going to draw that out it's already there for us we know we have an array result I'm going to draw that I guess over here cuz I want these to match up visually so it makes it easier for us to understand we initially fill them all with zeros right but I know immediately that the band positions are going to be netive 1 so one this position is going to be negative 1 this is going to be negative 1 okay I'm not even thinking about code I'm not writing code right you don't see me writing any code I'm just drawing I'm just thinking about it so how many reverse operations is it going to take to bring one in this spot it's impossible how many in this spot it's impossible how many in this spot in this spot that's what we're trying to answer so far we're just drawing it out here one's already there how many operations does that take that's zero right well what about over here we can take any one subarray and reverse it such that we bring one here so now I'm starting to notice a pattern I haven't coded it up I'm asking a question in my head I'm asking myself is it always going to be possible to bring one in every position assuming it's not a band position right band positions are easy we don't worry about those and the starting position is also easy so now I'm wondering is it always going to be possible for me to bring a value in every single position intuitively I think probably not because that's the whole motivation of having baned positions in the first place let's try some examples now obviously for us to bring one in this position we would just choose the entire array then reverse it if we do that one is going to end up over here which is valid so that's one operation now when you think about this subarray that we defined I'm still trying to in my head answer the internal question of can we always bring a one in every open spot when I chose the subay I really shows it by picking the end points right that's what defines a sub rate we don't always have to pick one as the end point right one could technically have been over here and had we reversed this array we would have ended up moving this one over here right but now I'm asking myself why would we ever do that why would we ever pick an array bigger than that are we always going to pick one as the endpoint because we could have accomplished the same thing here by picking these two end points so now I'm actually I'm honestly not sure this problem seems easier than it should be or should we always pick the one now I'm starting to think maybe there's some counter example I can think of but at this point let's assume that we're always going to pick one as one of the end points and then if we want to put one over here let's just pick that as the end point is there anything wrong with this approach so far I'm not able to think of it is it really this simple I guess that's what I'm asking myself is it always going to be one for all these open spots this seems too easy I must be missing something now okay and now I realized I didn't even read the entire problem if you read this explanation K is equal to 4 we can only pick subray of size K okay that's dumb by me right so now you can see reading the problem is pretty damn important that's usually where a lot of mistakes come from okay so now in this case the original solution still works it's one in this case because K is equal to 4 this is the subarray that we pick but now I can think that in some cases let's say if K was equal to two we're just going through some examples we pick these two end points let's still assume that we always pick one as one of the end points though I can think of a counter example where that might not happen so now I'm starting to realize this problem is kind of a you know politically uncorrect term this is kind of a crackhead problem because in this case if we try with k equals 2 I'll show you what I mean if we now uh pick you know this subate we can't do that we're not allowed to do that therefore one can probably never end up here so now I'm thinking can we be greedy and I already thought in my head probably we can't be greedy actually probably we can't because when I'm being greedy I'm always picking this one as the end point because if K is equal to two Okay we'll just push it as far as we possibly can right it's kind of like the problem Jump game jump this guy as far as he can well what if he lands somewhere where he's not allowed to land so that's a problem here right but think about this think about this example where this is actually a zero right where this is not a banned position this is not banned and let's say a is equal to 3 well we can't do this this is a subarray of size three we can't make that jump because it's still invalid so we kind of have to jump here first but we're not allowed to do that right now because this is a subarray of size two but what if we had an extra element consider this was the original example well here we can pick this subarray this is a subarray where one is not at one of the end points but actually even if we reverse this it's not going to do anything for us so it looks like I created the wrong example so the point I'm getting at there is an example where sometimes we're not going to be able to be greedy I don't want to spend a lot of time drawing it out but you can probably think of one but so at this point I've realized that we can't be greedy we can't always consider that as the end point of the subay so at this point I've learned a lot about the problem there's still a lot I kind of need to learn there's some patterns I still need to recognize but I don't want to waste too much time on this so I'm going to keep going for a little bit until I feel like I'm really really stuck then I'll update you guys on how far I got and then we're going to go look at the solution if we can't figure it out and and then see how we can actually understand the solution and understand why it works because I spent a few minutes it's important to try to solve a problem until you really get stuck and that's when you look at a solution and then see well where did I go wrong originally okay so it's been like 10 to 15 minutes and I've gotten to the point where I've realized this is a really hard problem I might not be able to figure it out and even if I can it's going to take me a really long time so we're going to look at the solution I will quickly summarize what I know about the problem so far looking at slightly different example than this one let's say we had one here and let's say we have three zeros before and after let's say k is still equal to four what I've kind of realized is that basically depends how we pick the window we have four choices because in a window of size four we can put one here or we can put it here or we can put it here or we can put it here now when we do this reversal we might be moving one to the left by three right by three here or we might be moving it to the right by three and it's going to go both ways but let me just kind of show you here so uh this window we'll move it to the right by three this window we might move it to the right by one this window we move it to the left by one and here we move it to the left by three so basically in terms of like our choices that we have we can either do a plus one in terms of like the position that we change this from we can do a plus three we can do a minus one and a minus three so that's going to be different depending on the position of one like here we can't can't really do a minus that's because there aren't any positions over there but we can do plus three here we can't do a plus one though because that would require elements over here so that's kind of why I'm getting to the point where this might be the wrong line of thinking because this is so damn complicated right that's kind of why I'm getting to the point where like I kind of want to just look at the solution now cuz I'm going possibly down the wrong track now if this was known to us if we could somehow figure out how we're allowed to move then it does seem very similar to jump game in that to fill in positions we could approach it like okay let's try to figure out how many moves it would take us to get here right and then run some algorithm or some Loop and then try to figure it out for every single position like that or we could think about it another way like from here we could do some kind of traversal right traversing this array we could say okay I'm allowed to move a plus one or I'm allowed to move uh + one + 3 - one minus 3 like from here right like I can do this or this or I can do uh this and this and so even though plus two or minus 2 wasn't included in this set if I do a plus one and then I do from here if I do a plus one here as well and from here I do a plus one it looks like we're allowed to reach every single spot so the only thing is we're counting right so for here it's one here it's one here it's two here it's one here it's two and here it's one so now I'm kind of getting to the point where this is kind of a traversal potentially it could be a graph traversal so to me it looks like possibly backtracking though given that we're looking for the shortest path shortest path meaning minimum number of jumps it takes to get to each graph wise that sounds like breath first search but even then I would need this set and even if I knew it actually this does seem possible because the breath for search is going to continue like this and the only thing is if we land on these I guess we stop the breath for search like we're not allowed to visit these positions and I think other than that it's fine but figuring this out is not straightforward like that's going to be kind of annoying though it does seem possible but again like I could be on the wrong track I don't want to write a bunch of code and then I'm missing like one Edge case time to look at the solution so there's no editorial so let's look at the solutions just so you guys know back in my day there weren't a bunch of helpful YouTube videos about problems like the only way to learn was to look at some of these really cryptic Solutions so there's a python one thankfully let's take a look at it thank God there is at least some explanation let's try to understand it it looks like it is a graph problem to some extent sorted list so I have no idea how sorting is relevant to this problem I was not able to make that conclusion um so let's try to figure out how and I'm probably going to do a lot of Silent thinking right now and then I'll try to kind of explain why the solution works and try to give you my interpretation of this uh discussion solution we start our investigation if there is a one at position node what neighboring nodes could it reach in one move kind of along like a greedy train of thought I left before reading this let's just see what he's saying be the the starting positions of the subay to be reversed okay that makes sense I think he's talking kind of about what I was like how we can position p in any one of those four slots right so this is I left is going to be the starting position minus k + 1 so that math wise in my head it makes sense cuz I've done it a bunch of times and he's taking the max because it's possible that this could go out of bounds it could go out of bounds too far to the left and he's going to do pretty much the same thing on the right side so a minimum of this node plus K like how far can we go to the right but make sure it doesn't go out of bounds I don't know why he's subtracting this though oh because he's considering the starting position of the subarray so just to quickly look back at our example what he's saying is we can start the sub aray anywhere from here minus K minus one it's possible though that this could go out of bounds so we take the max there and then from here we say this plus K minus1 but that itself is not going to be the starting position and not only that this part might not even exist it could go out of bounds so it might be possible that actually this is the furthest we can jump from here and if that is the case then the furthest left our window could start at is going to be like this so this is kind of complicated this is very mathematical I don't blame you if you don't understand all of it but I'm just again trying to explain how I'm approaching this even the parts that I don't understand quite fully I am trying to like bucket them and say okay this is the math stuff I'm not going to focus on that too much but uh this this isn't super crazy for right now then after reversing a subay from I to I + kus1 this is like the valid range of starting positions that the subray starts at and then if we reverse it the one will be moved to I + kus1 minus node in the end neighbor is chosen for some interval in here so I don't fully understand this part let's just quickly do it in our head so let's say this is the starting position this is our eye and this is the window these are the boundaries which he I think identified with some variables in this case it's simple it's going to be like that but if it were more complicated if it were something like this then it's going to be moving here so what's kind of like the general formula so I have I in the wrong position if this was the subay I would actually be over here so what he's saying is I is not always going to be in the same position as like P and so if this is the case then this is going to be I + K -1 and if we were doing the reversal of this P would end up over here here which is what we're trying to figure out like where is P going to end up so this is very mathematical so I'm just at this point trying to verify that his formula Works he's saying I so the left point plus the right Point minus the node so why is he doing that this plus that minus this okay I think I have it I think I understand why he's doing that because if you think about this the distance between I and P which in this case is one is going to tell us like okay that's one so then starting from here here we want to move to the left by one and that's going to tell us where P ends up so that's kind of the intuition behind the formula that he's giving I think not bad but again like this is complicated right like even if you could figure this out which I'm kind of figuring out just by looking at his solution it's taking me a while isn't it armed with this information let's do a standard breath for search however this is too slow as we are considering the same neighbors a lot it's basically the BFS that I was talking about kind of like okay you can go to these neighbors considering our example we'd be able to jump here and we be able to jump here but not here at least in one jump so this is a technically a working solution I guess that's the good thing like we did find a working solution but even this one is not efficient okay fine and that's because there's repeated work right that's the problem in this example there's not a ton of repeated work but you can imagine with this there is a lot of repeated work but why can't we just Market visited I guess that's kind of my question I'm not sure honestly so let's continue reading this to remedy this let's keep track wi nodes haven't been reached by our BFS yet okay so he is marking them kind of visited I guess we split these by parity into remaining of zero and remaining of one why is that what does that even mean when we have some interval low low plus two high of potential neighbors the reason he's incrementing by two I think is just cuz like depending on the position of the array I won't go into it I guess but it's the same thing like how we could hop by one and then by three but we can't hop by two that's the general case I guess that's always going to be the case we have some interval of potential neighbors we can query the intersection of this interval with unvisited nodes quickly as we only consider each unvisited neighbor once so I'm going to be completely honest with you guys I don't understand this paragraph I genuinely don't I'm going to read the code to see what he ends up with let's see the time complexity is n s and the space complexity is O of n what is sorted list where did he mention sorted list why do we have a sorted list I still don't understand that oh I think that's the parody that's the parody part so I guess if we can understand why he's doing a sorted list we can kind of understand the parody I'm going to think about it to be honest I'm going to look at the code I'm going to read it and then I'm going to try to explain it okay so I'm not going to lie I've been sitting here for 20 minutes now and while I think I'm getting a little bit more of the intuition this problem is insane this problem is probably the hardest I've ever attempted to solve I'm not even kidding I can see why it is the third hardest problem on leak c i I think this is honestly not Elite code hard I think this is a different class of problems I think super hard I've never done code forces but I assume that this is kind of the caliber of problems you see on code forces so I'm going to keep it real with you guys I probably theoretically could get a better understanding of this problem if I was sitting here for an hour or two or maybe even more just kind of whiteboarding it looking at this code I can understand the high level I can understand what he's doing here he's partitioning half of the elements here half the elements there he's using these two sorted lists to to Mark nodes as visited even coming up with a solution to use one sorted list to Mark him visited is very very difficult I think and the fact that he partitions them into two is difficult I think because it doesn't actually improve the time complexity it just improves it by a factor of two which usually doesn't matter for leak code problems but this time it does and just to kind of show you guys this is a video from another leak code YouTuber who's better at leak code than me I will admit and you can see the contest here like this was from a leak code contest only 900 people even attempted the problem usually I think at least 10,000 people will join each contest but in this problem most people did not even attempt this problem and of the people who attempted it only about 5% of people passed it and these are not stupid people just so you know these are really really smart people that means probably the person who's ranked like 100 on leak Cod or 150 they were not able to solve this problem the 150th best leak coder in the world was not able to do it so you know look at me I wasn't able to do it I don't feel bad even to understand it it would take me a long time and look at this guy's video this guy is better than me and this video he has is 1 hour long this guy was able to solve the problem he was able to solve it in the contest let me move my camera in this contest he got 88 in the world he's a very very smart guy um you can see first question he did it in 1 minute 5 minutes 7 minutes this fourth question it took him 58 minutes I think the bug counts as a penalty as a 5minute penalty so his total finish time was an hour and three but you know this is hopefully I think you at least learned like how I kind of approach problems this one I will admit was too hard for me and the reason I don't feel bad about it the reason I don't feel bad about myself right now is because I've made a lot of Le code videos 500 plus I've solved I think like 700 problems so I've probably in terms of hours spent between 1 to 2,000 hours on leak code I know that sounds pretty crazy right and most of those hours honestly weren't like rigorous like it's not like I was solving problems that were challenging for me most of that time was spent on easy medium questions that I was explaining on YouTube so even that 1 to 2,000 hours wasn't as rigorous or as productive as it could have been for improving I will say this guy or the guy we talked about at the beginning Scott woo these are really smart people but they've probably spent 5,000 10,000 I mean Scott woo he's been doing competitive programming since what he's 10 years old or something he's probably spent 10,000 hours on this it's true some people you know have different innate abilities but practice goes a long way don't compare yourself to other people don't say this guy so much better than me at this he probably put in 10 times the work that you did so if you put in the work you could be better that's not the conclusion of this video I'm not saying you should go out and be a competitive programmer I don't want to be I do this stuff one I enjoy it two it's good for coding interviews if I need to do an interview tomorrow I'll probably be able to pass it three I enjoy it I enjoy making the YouTube videos I like explaining to people I like helping people so that's why I do it don't take it too seriously this was embarrassing for me I'm not going to lie I was not able to solve or understand the problem I could probably give given more time but this time I'll take the L