Furthest Building You Can Reach - Leetcode 1642 - Python

0:00 - Read the problem
0:20 - Drawing Explanation
8:08 - Coding Explanation

leetcode 1642

#neetcode #leetcode #python

[sandeepsaluru]

Hi, personally I believe you are providing great content. I have one request, can you please also solve weekly leetcode challenges as well. This will help us a lot, there are not many channels that provide good explanations for these problems. Kindly upvote if you all agree

[HtotheG]

This problem was surprisingly fun, made me think of shoots and ladders, used a min heap and always tried using a ladder first but realizing it totally doesn't matter 😅

[ayushprakash]

wow! The intuition u gave to solve the problem is remarkable!

[gmh]

Great video! In such problems, I would like to see you comment more about the decision making process of the approach we should use.

Specifically, here, I naturally started the DP vs Greedy debate in my head. I thought Greedy wasn't possible because at any index, choosing ladder or bricks would depend on future indices. I couldn't bridge the gap and think we could retrospectively change our decisions; how do we know in a problem if this "retrospective change" is possible, thus making greedy the most optimal way (over recursion)? I've seen many other problems where `because we don't know future choices, we need to do solve this recursively` is what eliminated the Greedy approach from contention, but here, that wasn't enough. Why couldn't we do this in those problems?

[tusov]

add the current gap in heap is tricky but elegant, thank you neetcode

[marcoaraujo]

Yeah, I was caught on the DP bait :(
But your thought is very clever. Nice job, thank u for doing all these dailies resolutions ❤👌👌

[IK-xkex]

I tried to solve it by myself using dfs approach but couldn't pass time limits with input close to 1e9. So the problem should be definitely solved using min heap approach.

[Amy-]

This is brilliant!! I didn’t use recursion at first, but a maxHeight variable instead of heap - womp! Womp! Only 68/75 TC passed. I was struggling and wondering if I should use recursion. Thank you 😊 for demo’ing the right / sensible way to do this! - Amy

[LlamaBG]

thanks for the videos, man, they're very helpful; i always feel like i come up with the ideas myself because you lead up to them so well

[Logeshwar-sm]

my humble request also post leetcode biweekly contest questions

[MP-nyep]

Another great explanation as always. Thank you

[QwertyQwerty-sokw]

sorry not able to understand. why do we need min heap or max heap? We just need the previous largest gap where we used brick s (and replace it with ladders). can we not simply store just the largest value so far in a single variable, instead of accessing it through max heap?

[harshithdesai]

As usual wonderful explanation by neetcode!!!

[aryanshroff]

for every climb user has a choice whether to use brcks or ladder, just like a 01 kp problem where the thief has a choice whether to put the current item in bag or let it go
every choice user makes directly affects his ability to make choices in future buildings (example if all ladders used initially he cannot climb further when differene>bricks in hand)
thus to generate that optimal combination one has to kinda know the future i.e those particular indices where ladder must be used

this directly brings me to the conclusion that one has to explore all the possible routes 9and use caching to prevent solving the same subproblem again)
from where did the idea of useage of a heap arrived


would like to know the thought process / intuition
was array size the only giveaway that dp is not encouraged

also what seperates this question and 01 kp such that 01kp cant be solved by the same heap approach like this one !

[liangyu]

yeah I tried dp and failed. Thanks for the video!

[shandilyacodes]

So my mistake was that I was thinking like a human as in once I used ladder there was no going back to get it to swap with place where I should have used bricks instead. Even if I thought that my brain was resisting the thought of going back since, if I chose to go back, I'll have to climb buildings again to get them ladders. I think I am stupid, or super fixated at minute details.

[k.alipardhan]

This is quite easy.
List didnt work due to long compute time.
You need to use a heap (like in this video)

[Ashley-sdxn]

Yep I used backtracking and didn't realize it was wrong until I got TLE

[rgndn_bhat]

tried the dp with caching, didn't work. memory limit exceeded

[nikhil]

Can't we do greedy approach? Like use brick whenever possible else use ladder.