Furthest Building You Can Reach - Leetcode 1642 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/furthes...
0:00 - Read the problem
0:20 - Drawing Explanation
8:08 - Coding Explanation
leetcode 1642
#neetcode #leetcode #python

[@sandeepsaluru6587]

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 😅

[@ayushprakash95]

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

[@csam11100]

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

[@gmh14]

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?

[@HtotheG]

That's a great thought process, I too took a second to think about greedy vs dynamic programming but what gave it away for me personally was realizing that the ladders were always best to use on the highest climbs. Once you make that conclusion, you realize that you shouldn't equally think about each choice at every index, the state transition formula for D.P. is not straightforward if you have to go back and take a ladder from a previous climb. We could think about a recursive solution considering both bricks and ladders at every position but what gives away that won't work is the constraints of the problem. When the array can be as big as 10,000 elements, that is a give away the time complexity will be close to O(n) where here it's O(n*log(ladders)). However, from my experience in Heap problems doing the Neetcode 150, I had a lot of experience maintaining the top k elements in a heap where here k is the number of ladders in my solution of the number of bricks in Neetcode's solution and it's actually the bottom k elements. I'm not saying it's an intuitive conclusion but the more problems you do the more it helps you see patterns. Hope this helps!

[@HtotheG]

I have the formula of 10k elements - probably O(n) or n log something, 1k probably best is n^2, less than that probably either n^3 or 2^n or n!

[@aryanshroff8653]

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 !

[@aryanshroff8653]

@@HtotheG 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 !

[@MP-ny3ep]

Another great explanation as always. Thank you

[@IK-xk7ex]

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.

[@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

[@amineguettaby5507]

the same solution ❤

[@KeyanSong-br5li]

Thank you so much! you are the best

[@harshithdesai9989]

As usual wonderful explanation by neetcode!!!

[@chaunceyzhang6595]

Excellent video! Keep going on this!

[@marcoaraujo9446]

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

[@Amy-601]

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

[@razataggarwal7365]

I even used a largestJump variable but then realised it should be maxHeap

[@Amy-601]

@@razataggarwal7365nice 😊

[@aryanshroff8653]

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 !

[@NeetCodeIO]

With knapsack there are two different things you have to consider, e.g. maximizing the profit while minimizing the weight. This problem is more simple, we only optimize for one thing, going as far right as possible.

[@Ashley-sd5xn]

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

[@user-vu4ng4rb8k]

my humble request also post leetcode biweekly contest questions

[@nuggs_]

you are a beautiful human being

[@liangyu3771]

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

[@SlateCode]

Leetcode weekly contest also please

[@k.alipardhan6957]

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

[@kirillzlobin7135]

This is soooooooooooooo ammmmmmmmmmmmmazing

[@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.

[@QwertyQwerty-so4kw]

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?

[@QwertyQwerty-so4kw]

oof nvm I thought we always will have just 1 ladder to use. But we can have more than 1 ladder also.

[@rgndn_bhat]

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

[@dumbfailurekms]

GOATED

[@pastori2672]

i made the exact same solution but in the for loop [(1, len(heights)) with diff = heights[i] - heights[i - 1])] wont work but [(len(heights)) with diff = heights[i + 1] - heights[i]] would work ? i just dont see the difference ?

[@GeorgiosKritsovas]

You need to return i-1 instead of i then. Since you start one position ahead basically: your i is equal to 1 on the first iteration whereas his was 0.

[@pastori2672]

@@GeorgiosKritsovas ohhh got it thqnks ;qn

[@nikhil199029]

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

[@thiagot7706]

Can someone explain what is wrong in the monstrosity I have written? It fails in the testcase around 70 class Solution: # def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int: def furthestBuilding(self, heights, bricks, ladders): pq = PriorityQueue() i = 0 while i < len(heights) - 1: curr = heights[i] nextt = heights[i + 1] if curr >= nextt: # no need to use bricks or ladders i += 1 continue diff = nextt - curr if diff 0 and ladders > 0: # See if we can use the ladder to replace the bricks bricksInPQ = pq.get() if bricksInPQ + bricks >= diff: bricks += bricksInPQ ladders -= 1 bricks -= diff # Take the difference pq.put(diff) else: pq.put(bricksInPQ) ladders -= 1 # We can't replace, Use ladder elif ladders > 0: # Use ladder ladders -= 1 else: return i i += 1 return i

[@aryanshroff8653]

``` class Solution { public: void useLadder(int &ladders, int &bricks, priority_queue &maxh) { int bricks_Needed_For_Highest_Climb_Till_Now = maxh.top(); maxh.pop(); ladders--; bricks += bricks_Needed_For_Highest_Climb_Till_Now; } int furthestBuilding(vector &heights, int bricks, int ladders) { priority_queue maxh; int diff = 0; int i = 1; int repl = 0; int n = heights.size(); while (i < n) { diff = heights[i] - heights[i - 1]; // if diff is postive we have climbed , for diff negative we can ignore if (diff > 0) { bricks -= diff; // we have usd diff amounts of bricks in current session , to be uploaded in pq maxh.push(diff); } // status(i, ladders, bricks, maxh); if (bricks < 0) { // we have to use a ladder if (ladders == 0) { // we cant use the ladder and cant climb the previous building as well with negative bricks in hand i--; bricks += diff; // since we moved back to previous building we gained the bricks used to climb this one break; } else { // we have ladders in hand so we can undo the highest climb done by bricks and use a ladder instead to get those bricks useLadder(ladders, bricks, maxh); // now we have got our bricks back } } i++; } if (i == n or bricks < 0) { i--; } return i; } }; ```

[@kirillzlobin7135]

I came up with the recursive solution, but it does not pass time limits for this task

[@user-xm7hx8tz9o]

Same)

[@colindubzak4178]

I did the dp with caching "solution" intuitively and got TLE :(

[@shitluna50kgonedogegogogo87]

func furtherest_building(arr []int, bricks int, ladders int, idx int) int { if idx >= len(arr)-1 { return len(arr) - 1 } if arr[idx] >= arr[idx+1] { return furtherest_building(arr, bricks, ladders, idx+1) } if arr[idx] < arr[idx+1] { giving_bricks := idx if arr[idx+1]-arr[idx] 0 { giving_ladders = furtherest_building(arr, bricks, ladders-1, idx+1) } return max(giving_bricks, giving_ladders) } return idx }

[@user-xz5iw1wf9w]

How to know when to use dp or greedy approach 😢

[@qx-jd9mh]

Reoccurring subproblems (find a recurrence relationship) -> dp

[@mihaiandrei3144]

Am I the only one for whom this algorithm didn't passed all tests?

[@darrowthered7665]

I came up with the same approach and coded it in Java. Passed all cases.

[@mihaiandrei3144]

hmm. then it's me who's wrong somewhere. ty

[@dipakmaity2205]

i used minheap but great soln