LeetCode Day 25 - Jump Game (DP or Greedy?)

Elements of the array tell us how far to the right we can jump. Can we get to the end?
Educative giveaway - gleam.io/lMAUx/errichto-educa...
Grokking the Coding Interview Course - www.educative.io/courses/grok...
Leetcode April Challenge - leetcode.com/explore/featured...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming

[@Errichto]

Educative giveaway winners were contacted via email on May 2. You can also see a censored list of winners at the beginning of this stream kzbin.info/www/bejne/l3KnlHWur759b5Y

[@nissal7033]

I appreciate that your explanation are so intuitive. Almost making logical reasoning seem instinctive

[@ishaangupta4125]

Solving the minimum jumps you inadvertently solved jump game 2 problem on leetcode

[@jimwoodward7293]

Thanks Errichto -- these videos so good!

[@yunjiehong4649]

Some people look down on these problem, meaning it’s too easy. But there are many ways to achieve the goals, and implementing quickly is a challenge. Love your videos which are very inspiring

[@camper8650]

hey you got some money dude ! congrats !

[@Errichto]

And you get free courses ;p

[@navneetarya4398]

@@Errichto haha... thank you so much

[@miteshkumar3183]

@@Errichto POSITINO

[@mohdar2061]

@@Errichto win win

[@joaquinlopezmunos4013]

@@Errichto bro how long have u been coding? i meen since when? how can you be so op?

[@abhaypatil2000]

2:54 cutest kamil😂😂😂

[@rentib9136]

At first i did it with segment tree to mark at which stone i can arrive, then I understood that the total interval must be continous. It made it much easier. int m = 0; //the last stone you can get to for(int i = 0;i < nums.size();i++){ if(m < i) return 0; m = max(m, i + nums[i]); } return 1;

[@5888joseph]

Brilliant!

[@waatup]

Love your videos, I just subscribed!

[@flamendless]

I like that pun in the intro

[@ZzwhiskeybkszZ]

Can you be a bit slower at time and space complexity analysis please? Love this series of yours by the way! Really glad I found your channel

[@front-end-forge]

`LeetCode` is just a great place to learn a lot. And solving programming challenges within time frame is just awesome. This inspired me create my own channel which solves coding problems of sololearn community challenges every weekend. And uploading my next challenge in a while.

[@johncarter3151]

That's great.!

[@unlockwithjsr]

Hmm, Sololearn, I am in there as well

[@rafaeldietrich8050]

Amazing video! Any advice for anyone trying to self teach math? Spec with a programming focus.

[@lolista]

can anyone tell where can I get that timer? looks like it is the same timer that shows up when I google 'timer'... but wanted it to be floating on my screen like Errichto!

[@ArjunSingh-qt5jn]

HI Errichto, I really like the work you are doing, could you please make some videos on Time and Space Complexity?

[@shrad6611]

For Java Programmers, instead of using pair class, we can use two integer variable num1 and num2 and initialize these values with 0,0 and then later in while loop we can update their values as we do for pair class. Easy

[@AmanRaj-ce3lw]

or you can use java.awt.Point

[@conorhynes8633]

Are there any questions that use a similar approach?

[@xmingw]

bool canJump(vector& a) { int n = a.size(); int target = n - 1; for (int i = n - 2; i >= 0; i--) { if (i + a[i] >= target) target = i; } return target == 0; }

[@ivanleon6164]

when i read it i tought they asked if you can reach (exactly) at last index and that you could only jump the number in the current index(forward or backward), lol. i just make things more complicated that actually are.

[@sreyanchakravarty7694]

This is the same question I have so many times. Dp or greedy?

[@RN-jo8zt]

How many hours u were spending on coding sites .when u started solving problem on earlier days?

[@hellowill]

"Make it slightly bigger" has to be in every video

[@hitensharma259]

Your Bear and steady gene problem on HackerRank is killing me

[@qazaqempire2446]

hi from Kazakstan, mr Polish guy.! damn i envy your skills! i do have bachelor computer science degree, however i never practiced algo questions. now i m over 30 and struggling with this.. damn i wish i started it 10y ago! question: how many years have u been practicing algos for?

[@osmanay4301]

BFS (with queue) solution works well for this problem.

[@yinghanma1314]

time limit exceeded

[@lucygaming9726]

Isn't this similar to bfs?

[@poo81]

@Errichto can you please give us a DP solution?

[@siddhantkedia9925]

Errichto making puns 🤣

[@yunjiehong4649]

Siddhant Kedia where are puns

[@shreyansh5964]

@@yunjiehong4649 I am here,no worries

[@whitesalmon0925]

I appreciate you try so hard to think like a normal programmer instead of a pro, I really appreciate it, but can you turn back to pro mode once in a while?? thank you

[@vikasvishwakarma5263]

errichto has some special love with pair :P

[@sacchidanandverma8201]

I solved it with dp without thinking. Thanks for greedy solution.

[@shivamhanda457]

Can u plz tell dp approach

[@yunjiehong4649]

Sacchidanand Verma you’re so brutal. Brute force to solve everything 😆

[@sacchidanandverma8201]

@@shivamhanda457 When you are at index i, if any index from L=i+1 to R=i+jump[i] , can take you to end then this index will also take you to end. To avoid O(n^2) complexity I query(L,R) using segment tree which gives O(n log n) complexity.

[@sacchidanandverma8201]

@@yunjiehong4649 I always start with brute force solution. 😅

[@secretmystery8305]

Hahahah that was nice lesson. Thanks you for this all. And my one question. When you again come on live stream on KZbin. Please reply this comment.

[@Errichto]

I'm streaming live in 1 hour on Twitch :D www.twitch.tv/errichto

[@akshatupadhyay8002]

I did it in O(n) starting from the second last element till the first element and marked last element as "destination". For each ' i' in that range i was calculating the distance from the destination =(destination-i) and if nums[i] >= that distance i updated my destination as i And if at last my destination ==0 then returned true else false

[@twrskshm]

Exactly what I did

[@guilhermecorrea3604]

me too, I went checking if it would fill the "gaps", and if got back to the beginning, return True

[@sangramjitchakraborty7845]

I suppose the checking can be done in O(n) time. The minimization would be O(n^2), but that can be improved using segment trees.

[@vishalmishra1937]

Hey is educative courses are free for every one .I am in need of that also i dont have no money to spend

[@AlexSav]

7:31 in second solution you always do n steps, even if first jump can reach end position.

[@Errichto]

"Premature optimization is the root of all evil" don't add a break if you don't need it

[@balamukundam]

cud u plz upload a video for leet code 306

[@syeda.k.2934]

Increase the font just a little more @Errichto

[@xritzx]

[@consistentthoughts826]

For product array except self I took 3 days to solve How to improve coding skill

[@mohitmotwani9256]

practice

[@shreethejashagrithaya3211]

I challenge you in competitive coding in. Hello world

[@asadbinsaber7260]

What things usually contains a personal competitive programming notebook? What about yours? I am trying to make one, but struggling at starting.

[@Errichto]

I don't know what you're talking about. I don't have any codes. There are some hard algorithms for which I copy-paste the code, like FFT - you shouldn't worry about it as a beginner though.

[@asadbinsaber7260]

@@Errichto Okay, thank you.

[@mohitthorat8580]

Errichto, you didn't submit the second code. The accepted was from previous solution. And I am afriad that code fails when nums[0] = 0. In which case you should immediately return false. But it's possible to return true with that solution(maybe).

[@XxDruidegoxX]

With his second solution, he will return true, this is what is asked to do. i = 0, i

[@mohitthorat8580]

@@XxDruidegoxX Hey Alex, consider this array. [0,2,1]. The answer is false. But his code will return true.

[@andersonandrade644]

@@mohitthorat8580 No, it won't, after the first iteration i becomes 1 and can_reach is still 0, so i

[@mohitthorat8580]

@@andersonandrade644 cool. Looks like missed that condition.

[@BedoEbied]

I went from the end to the beginning, isn't it better?

[@waatup]

Going from end to beginning is Θ(n) where n is the number of elements, while going from beginning to end, with 1 additional check at each step has a worst complexity of O(n) and best complexity of O(1) because you can stop as soon as you know either the current position is unreachable or you can already reach the end. When evaluated across uniformly random non-negative integers inputs, going from beginning to end is much better. Of course the test cases' integers would be heavily skewed towards 0, but in practice going from beginning to end still wins because retrieving vector/array elements from memory/cache is more expensive than doing comparisons in registers; in other words, doing 1 additional check at each step incurs very small penalty, and iterating through the array unnecessarily is more expensive.

[@winning_aadict]

Hi Errichto. I have fulfilled all the requirements for the educative courses. Please help me avail the system design interview as I am preparing for interviews currently and this would really help my preparation. Thanks in advance.

[@ickywitchy4667]

are u the daddy of coding??

[@vishalgoyal9180]

Code is in which language

[@zenzen318]

C++, obviously

[@mridulkumar786]

Most of the comments are from India

[@hacker-7214]

7:38 wont work and you pressed run code and not submit. Edit. This comment is wrong read reply

[@XxDruidegoxX]

False, it will work. The reason why it will work is because of the condition in the loop : i

[@hacker-7214]

@@XxDruidegoxX nvm u're right. I thought it would be an infinite loop for some reason

[@minghuili4254]

3:37 doesnt make sense! I do not understand what are thoes numbers coming from

[@NehaYadav1]

That is just an example Errichto took; not related to actual values in the examples .Suppose the interval is from [5,8] and can_reach= 15, now you can upgrade your interval to [9,15]