leetcode 2770 | Maximum Number of Jumps to Reach the Last Index | DP | Segment Tree |Leetcode POTD

Añadido: 2026-05-11

[00:00:01]So hello and good morning to everyone.

[00:00:03]So today's lead code is 2770 which is maximum number of jumps to reach the last index. Right? So basically in this question we are given a zero index integer array named as nums and whose size is n and we are also given an integer target. And initially we are at index number zero. And in one step we can jump from any index from index i to any index j such that such that j should be greater than the current index i. and and the difference of difference of the element present at index J and index I that is nums of J minus nums of I should be in the range from minus target to target right that difference should lie in the range then we can jump from index I to index number J right and what we have to do is we have to return the maximum number of jumps we have to return the maximum number of jumps to reach the index I n minus one from index zero like 0 to n minus one and what is the max max max number of jumps and if there is no way to reach index n minus one then we have to return minus one right so let's see examples to get the question more clearly so in the first example we are given that nums array is 1 3 6 412 and the target is 2 means the difference of the two values should be in the range minus2 to two and we are we are presented at index number zero so first can we go to index Number three.

[00:01:31]Yes, we can go because the difference is two. Then from three, can we go to six?

[00:01:36]No, the difference is three. From three, can we go to four? Yes, the difference is one. We can go. From 4 to 1, no, 4 to 1 is not possible. Then 4 to 2, yes, it is possible. And the difference is two.

[00:01:47]So how many jumps we have taken? 1 2 and three. We have taken three jumps. So the output here is three. As the maximum number of jumps that we can take is three only, right?

[00:01:57]Let's see the example number two. So here we are given with the same array 1 3 6 412 but our target value is zero.

[00:02:05]Now that means that means the difference of the value should be zero. So initially we are index number zero that has value one. That means we can jump to another index which has the same value.

[00:02:18]So we have jumped to this index having the same value. Now from here we can't jump to any future index because there is u no future index having the same value. So there is no way we can reach n minus one. Right? So hence we have written minus1.

[00:02:37]So let's move to the constraint part. So nums.length which is the n. So n is up to 10 power 3. Right? And each element in the nums array each element in the nums array can be from - 10^ 9 to 10 power 9. Right? And a target can be any value from two value up to 2 into 10^ 9.

[00:02:59]This is the target value. So here see n is 10^ 3. That means n² n² will be 10 power 6. So we can we can so like due to these complexities n² won't give us t won't give us t like n² will be a feasible solution it will be a feasible solution to us right so we can think of some solution of n² right so let's start so in this video I'll be explaining you the brute force approach that is n square approach using dp and I'll also be explaining you uh the same solution using segment right so please watch it uh completely. So here our problem asks the maximum number of jumps to reach n minus one from index number zero. So here see whenever we are asked for maximum or minimum jumps then the first natural choice which hits our mind is dp right.

[00:04:00]So we have declared so dp of i is basically the maximum jumps needed to reach index number i. Right? So that is DP of I. So suppose if DP of I is equal to 5 that means that means to reach index I from index number zero we need a maximum of five jumps. We need a maximum five jumps. And if DP of I is equal to minus1 that means this index cannot be reached. This index cannot be reached.

[00:04:27]Right? So we start. So at initially we are at index number zero. Initially we are at I is equal to zero. So DP of 0 will be zero because we do not need any jump to reach index number zero. We are present at that case. So DP of 0 is equal to0 will be our base case. Right?

[00:04:47]Will be our base case. So let's see how we'll be doing the transition. So here we can either do forward transition. We can either do forward transition or or we can do backward transition. Right?

[00:05:00]Either forward or backward. So let's see what will be the what will be in forward transition. So in forward transition what we'll do is we assume that we are currently at index number I. We are currently at index number I and then from this index I we'll jump to all the indexes J. We'll jump to all the possible indexes J. Right? And then update their values. Right? Update their DP of J values. Right?

[00:05:26]So from current state from current state I we are taking we are moving to all the future states J we are moving to all the future states J right so that's why it is forward transition right so we are currently at index I and then we try all future indexes J lesser than greater than I sorry and we check if our jump condition is valid that means the difference the difference of the elements should be in the range minus target to target if that happens then we update the DP value right by the already stored value or the current value the current value at I plus one more jump plus one more jump we are taking to reach there so DP of 5 + 1 so and we take the maximum of these so this is forward transition similarly we could have taken backward transition also so in backward transition what we assume what we assume that we are at we are now now at index index number at index j. At index j we are now at index j. So what we think is what are the previous states? What are the previous indexes I which are lesser than j? What are the previous indexes i which are lesser than j. From those indexes we can come to j.

[00:06:44]Right? We scan all the previous indexes i. We scan all the previous indexes i such that from those indexes we can come to j. Right.

[00:06:56]So we take all the previous indexes I and then from there we jump to J. So what we do is we'll scan all the previous indexes. We scan all the previous indexes I and then take the maximum value then take the maximum value of the all the previous indexes right and then add one because from I to J we need one jump. So add one to it. So DP of J is equal to 1 plus maximum of DP of I. So if we show it mathematically.

[00:07:28]So basically it is maximum among all the indexes I lesser than J and there is a valid jump. So we take DP of I + 1. So whichever index I gives us this value as the maximum then we take that value and store in DP of J. So here we have seen both forward transition and backward transition. So I'll be using forward transition and uh show you and like you can try out any like take forward or either backward transition.

[00:07:58]I'll be using forward. Right? So let's see an example. Right? So we are given the nums are 1 3 6 412 and our target is 2 right. So initially our DP will be DP of 0 will be zero and all the other states having minus one. That means they haven't either reached or they can't be reached. Right?

[00:08:19]Then for from index number zero at index number zero we have value one right we have value one. So we check all the future indexes where we can jump with this value right.

[00:08:33]So see from value one from value one what will be the range? Range will be it should be between minus2 to 2.

[00:08:42]Difference should be minus2 to two.

[00:08:44]Right? So it can be from three and then minus2 means I think -1 to -3. We can take all the values from minus1 to minus uh three.

[00:09:00]Right? So we can jump to three, we can jump to 1, we can jump to two. So these are the indexes where we can jump.

[00:09:09]Right? And see here here at index number zero the number of jumps are zero. So we mark the future indexes where we can jump we mark that DP value as their DP value as one. Right? So let's see.

[00:09:26]So first we see J is equal to 1. So at J is equal to 1 the difference difference is valid difference. So we mark DP of 1.

[00:09:35]DP of 1 is equal to maximum of the value stored. stored value is minus 1 and the current value that is at 0 + 1 it's 1.

[00:09:43]So this way for from i=0 we check for all j values for all j values and then update our dp value.

[00:09:53]Then we move to the next index that is from index number one. At index number one we have value is equal to three.

[00:10:00]Right? So again we try out all the J values from J= 2 to N minus one and then take the valid uh what we call valid indexes where the range where the range uh difference of the range satisfied and then again update the DP values right then we do the same thing from index two and index three like I have shown you only some part of it right so again we updated our DP after uh processing index number three. So this is our final DP right. So if you see the value stored at n minus one is n minus one is three. That means that means the maximum jumps required to reh to take from 0 to n minus one is three and that is our answer. So our answer is three. So let's see the code part of it. So in the code part we have first taken the size which is n that is num size and then we have declared a dp of the same size n and initially declared all the values as minus1 then our base case is dp of 0 is equal to zero then we iterate from all the indexes from 0 to n and then we see if our current state of that is dp of i is equal to minus1 that means we haven't reached that state so we skip that state. But if DP of I is not equal to minus1 is not equal to minus1 then then we iterate over all the future states J from I + 1 to N and then we find the difference that is nums of J minus nums of I and if a difference if a difference is is in the range minus target to target then we then we mark DP of J is equal to maximum of the value stored and and current value + one right current jumps plus one. So this way we'll we'll reach all the states from I to J and at the end what we'll do is we'll return DP of N minus 1 right so so this uh process of this approach of Rs is worked because our n is equal to th00and only but what if n is greater than 1,000 then n² n² will not be feasible it will give us t so then this approach would would be would have been failed and we have to think of some optimized solution right so so what we'll do is why why this approach is failing because for here for every J every j we have to scan all the previous indexes I we have to scan all the previous indexes I and which is making it slower which is making it slower right so so what so let's see that how we'll be optimizing it so if you see the condition. Our condition is that the difference that the difference should be from minus target to target. Right? So if we if we bring nums of J here, it will become nums of J minus target, nums of I and nums of J plus target. Right?

[00:13:12]So the if you rewrite if we rewrite the condition, this would have been like this way. are nums of I. Nums of I would be in this range would be in this range.

[00:13:25]Right? From nums of J minus target to nums of J plus target. Right?

[00:13:33]So for current index J, for current index J, we need all previous indexes.

[00:13:39]We need all among all previous indexes whose values lies in that particular range. What we want? We want we want that previous range that previous index I whose value whose value lie in the that particular range and so that index lies in the particular range and also it gives us the maximum value of the DP right. So now if you see our problem has been updated to a range problem that is range maximum query right that is we have to find we have to find maximum value of DP of I DP of I in a range in a range of indexes right for every current value that is nums of J what we need we need we need maximum value of DP of I that means we need for all indexes I lesser than J. We want that index who who gives us a maximum value of the DP. Right? And also also that this range this range should be satisfied for that for that particular index that is nums of J minus target should be lesser or nums of J plus target like that nums of I value should lie in the range. Right?

[00:15:00]Then DP of J DP of J will be the best value that we get plus one. Right? So now we have the range queries. So as we know for range queries we either use segmentry or fanic tree. So here we use segment tree because because segment tree to gives us a query also and it does the point update that is update at one position. So both giving range maximum query and point updation it does in log and time instead of off and time.

[00:15:33]So earlier I time complexity will be was be was big of n² but now using segment tree it will be reduced to n login sorry not n it will be n [clears throat] login right.

[00:15:48]So we use segment tree but there is one problem over here. See in the constraints we are given that the values in the nums array can be from - 10 power 9 to 10^ 9 - 10^ 9 to 10^ 9 and it is not feasible for us. It is not feasible for us to build a segment whose size is 10^ 9. So what do we do? So we have to think. So we'll be using coordinate compression. Now what is coordinate compression? So let's see. Suppose we are given a nums array who who has the values 1 3 6 412. So for coordinate compression what we'll do is first we take first we take unique unique sorted values unique sorted values of the nums array. Right? So see here the unique sorted values are 1 2 3 4 and six.

[00:16:44]Right? Then what we'll do is then we'll we'll assign new indexes new indexes to these uh compressed values. So one will be given index zero, two will be given index one, three will be given index two, four will be given index three and six will be given index number four.

[00:17:02]Right? So these are the new compressed indexes assigned to the to the nums values now. And now see earlier how much values we have. we have six values but after compressing we have only five values. So now the value becomes small indexes right. So now what will be our segment storing? So at compressed positions of value x right at compressed position of value x what we storing? We storing the maximum dp value that we can achieve using the particular value x. Right? So we'll be uh storing maximum DP value that we can achieve. So we'll try to understand it with the help of an example. So we have taken the same array 1 3 6 4 1 2 and our target is two. So first we need to we need to compress the indexes. So we first sort it. So we get 1 2 3 1 2 3 4 and 6. So one will get index number 0. two will get index number one, three will get index two, four will get index three and six will get index four in the compressed indexes. So now at step number one, at step number one, at index number zero, we have nums of zero, we have nums of 0 is equal to 1, right?

[00:18:26]We have nums of 0 is equal to 1. So and dp of 0 is equal to zero, right? We'll be starting from here and dp of 0 will be zero. So now we have to update the segment tree and and we store. So value one will store for value one. For value one we store DP is equal to zero in the segment. Right? Then we go to next step.

[00:18:52]Now at next step we have nums of one which is three. We have nums of one which is three. So for three we will be finding what will the range of the previous values. What is the range of previous values? So 3 minus k and 3 + k.

[00:19:10]So the range of previous is 1 to 5. So all the values in the range 1 to 5 are allowed for the current value. So now in for these values we find the maximum dp value. We find the maximum dp value.

[00:19:27]Right? So this is a range in what we call in the normal array. But see in com uh compressed indexes in compressed indexes the value corresponding to these are 1 2 3 and four because because if you see see six six is having index number four.

[00:19:49]So our range was 1 to 5. Our range was 1 to 5. So what are the indexes? Index is 0 1 2 and three in that particular range.

[00:20:00]Right?

[00:20:01]So for this particular range we have to find the compressed indexes. So the compressed indexes are 1 2 3 and four.

[00:20:08]Now what we do is we'll query we'll query and we find the maximum DP among these values. Right? But in currently in the segmentry we have value one that is DP of zero. So best value that we get is zero. And now we mark DP of 1 is equal to best + 1. So best is 0 + 1 is 1. So DP of 1 will be 1. So we update again we update our tree and value three. Value three will store DP as 1 right in the segment tree. Then we move to step three. And at step three we have we have taken nums of 3 is equal to 4. Nums of 3 is equal to 4. So again we found the allowed range that is 4 - 2 and 4 + 2 that is 2 to 6. So this is our allowed range. Then we find the compressed indexes range. Compressed indexes range.

[00:21:04]Right?

[00:21:05]So compressed indexes range is for 2 to six.

[00:21:11]For 2 to six are compressed indexes range is from 1 to 4. From 1 to 4 compressed indexes range is from 1 to 4.

[00:21:21]So now we'll query we'll query the maximum DP value in this range. And now suppose we have gotten we get the best answer is 1 then we mark DP is 1 + 1 we mark DP as 2 and then update our tree.

[00:21:35]So this way we'll do the query part and we'll do the updation part. If you don't know like uh if you don't know about segmentry I have already explained you I have already made a video on segmentry you can watch out that video and like you'll get it. So this way like using segmentry we could implement uh the solution and reduce our time from n² to n login right. So let's move to the code part. So in code we have implemented our segment class. In that we have taken integer variable n which is a size of the array and then our uh vector or we can say array to store the segment tree.

[00:22:21]Right? So this is a constructor which will take the size and then declare declare tree of size 4n. I have already explained in that video. So make sure to watch out the video on segment tree before uh seeing that this part right because I explained why we take size as four and in that video right then this is our u code for updation. So in update part we take the starting and ending uh range. So this is a range of the node and we have to update index idx with value well. So if we reach so this are base case that if we reach leaf node if we reach leaf node that is starting range is equal to ending range then we update tree of node is equal to maximum of tree of node comma value. Right? So this way we update this node and then after updating the node. Then if this is not the case then we take the mid part.

[00:23:21]Then we find the middle middle value and then check if in index is lesser than middle then we update the left child else we update the right child. After updating the child we update the parent.

[00:23:34]So parent value is equal to maximum of value of left child or maximum of value of right child. So parent is equal to maximum of left child, right child value. Right? So this is our update part. Then we see the query function. So in query function there can be three cases either no overlap or complete overlap or partial overlap. So in case of no overlap we return minus one. In case of partial complete overlap we return the direct value. We directly return the value. In case of partial overlap we go to left child and right child and find the maximum value out of these two right out of left child and right child.

[00:24:19]So this is query function then this is our main function. So in main function we have taken vector integer wells that is we are doing coordinate compression and then we are finding we are finding unique sorted values um of the of the nums array right and then then we are taking the size of the compressed compressed uh values and then made a segment of that compressed size right and then we have taken a ve dp of the same size and marked dp of0 is equal zero. Now we are finding we are finding the compressed index we are finding the compressed index of nums of zero in the wells array. So we are using lower bound wells dot begin wells dot end nums of zero. So it will gives it will gives us an iterator in iterator in wells array whose size is equal to equal to nums of zero.

[00:25:19]Right? And then we are subtracting minus wells dot begin to convert that iterator to index iterator to index. Right? So we get our position zero. So now we update this position zero with the DP value that is zero. Right? Then then we have used then we have used a loop on from 1 to n on the nums array. So we get the left value and right value. left value and right value is the that is nums of J minus target and nums of J plus target.

[00:25:51]This is the left value and right value for the range for the range in the nums array. Then for this range we have to find the compressed range also compressed range in the in the wells array in the wells array. So we find find iterator of left value using lower bound and then we do well dot begin to make that iterator to iterator to index.

[00:26:15]So this will give us the left range.

[00:26:17]Similarly to find the right range we'll be using upper bound. We'll be using upper bound and then we subtract this from the this from the iterator value that we get. So now we have got we have got the compressed range. We have got the compressed range. So now in this compressed range we'll find our uh max max maximum DP using the query function using the query function we in the compressed range we find our we find our uh what we call best value and then if our best value is not equal to minus1 then we update our DP value as best one right and then we get our best value then we have to update our current value right so Again we have to find the compressed index compressed index for nums of J in the wells dot array and then we update this DP value at that particular index right and at the end we return DP of N minus one. So this way we use segment and compressed indexes uh to solve this question properly. So I hope I'm able to explain you the solution properly. So if you like the video, please make sure to like, share and subscribe the channel.

[00:27:33]Thank you.