LeetCode Day 18 - Grid Minimum Path Sum

[@nikhilgautam2857]

Supporting errichto from bottom of my heart for being honset with community and giving knowledge ,far better than scammers selling paid courses with shit content. Keep up bro

[@Errichto]

Thanks :)

[@hshhsjhahsvs7728]

One of the few channels that doesnt waste my time. Thanks!

[@i_vikassharma]

More than the solutions, its always delight to understand your thought process. Your approach and content is extremely helpful. Thank you so much!

[@bogetutzu]

I feel so good that I found you, Errichto. Even if some problems are far over my knowledge, I know I'll get there. Thanks for those nice videos with great explanations :)

[@youarecorrectiamwrongbecau1338]

Hey Errichto! Yours and mine rank was same today for almost the first hour. You started with the last problem. I started with the first. My rank didn't grow after that though. congrats! Double digit rank. CJ20.

[@ishaangupta4125]

Can you discuss about the bottom up dp solution for valid parenthesis string problem from 3 days back? Top down dp was easier to code and visualize but bottom up solution in editorial was insanely hard to understand

[@Errichto]

If you want to learn iterative dp, watch my dp lectures ;)

[@ishaangupta4125]

I was hopelessly stuck trying to figure out even a top down dp solution. I watched 2 of your videos but still couldn't make headway. Gave up after 2 days. The problem is iterative dp solution is not properly explained. Would love it if you explain it once

[@Errichto]

@@ishaangupta4125 Do you want me to explain again what happens in the video? dp[row][col] is best path ending at (row, col). To compute it, I use already computed best paths ending at (row-1, col) and (row, col-1).

[@ishaangupta4125]

@@Errichto I'm sorry. I should've been more clear. I wish you could explain the bottom up dp solution for the valid parenthesis string question. I'm commenting on this video because it's easier to reach you on latest videos.

[@leetcodesolver9092]

Nice explanation, I also solved it using Dynamic programming but space complexity is O(M) in my case.

[@Errichto]

Lower memory complexity is indeed possible, good catch!

[@thakararkeval4759]

please upload kick start round b wondering robot problem

[@angiras07]

I aolved it thanks to your lectures

[@vickyandreas1230]

Always see this channel's videos, so informative

[@surajkumarsharma5796]

From where you have learnt analysis of algorithms To find which algo is efficient All of time complexities and so on

[@Errichto]

Watch a video on "how to start with competitive programming" kzbin.info/www/bejne/rnLImouvbZJsj5o basically, solve problems and you will learn things.

[@dhananjaysonawane1996]

#errichto What could be the approach if grid has -ve numbers as well? My intuition : we need to move in all 4 direction.

[@agent0zer0]

This approach works for negative numbers as well. We shouldn't move in all 4 directions because the question instructions say that we can only make a down/right move.

[@Errichto]

Negative numbers change nothing here. But if we were allowed to move in all 4 directions (without repeating the same cell), that's an NP-hard problem. EDIT: it's just Dijkstra if we have posivitive values and can move to all 4 neighbors.

[@pqrabcd]

Why does this need DP? Can it not be done using BFS with min-heap to give shortest next index? Is it not similar to Dijkstra's shortest path algorithm?

[@ashish1122000]

Could you do a video on the problems in today's CJ Round 1B please? The problems were really interesting and can be great learning tools.

[@sasankasekharde9835]

Why don't you do a video on the gear that you use to code/build anything? We would love to see it.

[@oziomaogbe8665]

please which screencasting software do you use?

[@esbanarango]

@Errichto Thank you for all your work! I really enjoy your videos! I was wondering if you will do a video of CodeJam Round 1B 2020?

[@athenanouhi]

@Errichto, thank you for the video. How about if the question is finding the actual paths that lead to the minimum sum path? This is an interview question and has been puzzling me.

[@karanh]

Can you explain the else part of the solution? Especially where you compute the min()

[@karansagar7870]

Can u make video with bigger font or more zoomed version ?

[@gladwinrojer273]

Please improve video quality atleast 720p

[@iamsuperwen]

What if it can also move up and left? Thanks in advance.

[@aryanlohani622]

It would always increase the sum

[@zacklee2510]

Then you would have to represent this as a weighted graph and run some shortest path algorithm like Dijkstra’s

[@Danzlh]

@@aryanlohani622 not neccesarily. in small grid that might be the case, but you can try to construct a 5 x 5 example where moving up/right produces a smaller sum.

[@rentib9136]

@@aryanlohani622 nope and here is an example 1 9 1 1 1 1 9 1 9 1 1 1 1 9 1

[@rentib9136]

Just like Zack Lee said it will be enough to run Disjkstra on the grid, I dont think there is any way to solve it faster than O(n * m * log(n * m))

[@israkulhaquetusher3256]

what will be the recursive approach ??

[@aparna8338]

Your videos are soo helpful

[@999ggod]

Hey @errichto I got a similar question in my interview but couldn't solve All the grid cells have an arrow directions, if we move along arrow direction then cost is 0 else cost is 1. Find min cost to reach bottom right from top left. You can move in all 4 directions Please help!

[@arthak2475]

Arrows were only in right and down direction or all 4 direction?

[@ZeeshanHussain12]

use Dijkstra to solve it, for every node you can move in all 4 direction. Weight for every node will be 0 where the arrow is pointing and for rest it will be 1. It will take nlogn but there is a better solution in o(n) using 0-1 bfs

[@999ggod]

@@ZeeshanHussain12 thank you my friend 01 bfs does look like the correct approach

[@TheJoker-cm5mf]

Stupid question. What’s the difference between x++ and ++x?

[@rentib9136]

++x (preincrementation) means: x = x + 1 and then do sth; x++ (postincrementation) means: do sth and then x = x + 1

[@nguyenhoanvule5755]

Which keyboard are you using for coding?

[@sounishnath513]

can we apply BFS like yesterday problem?

[@agent0zer0]

You can BFS every possible path in the grid but you will be searching many paths that are not required. This is a standard DP problem where there is optimal substructure and overlapping subproblems. Therefore, DP is the most efficient way to solve this problem.

[@israkulhaquetusher3256]

i have applied bfs and got WA :-(

[@devanshmaurya9928]

I applied DFS and got TLE

[@sounishnath513]

@@agent0zer0 hmm. Later I understand.. but. I interest in how to implement.

[@Errichto]

How would BFS use values from cells?

[@9MAS91]

was waiting for this video, did not expect it to be so fast

[@seaorz]

Did you cleared Codejam Round 1 2020?

[@FazeelUsmani]

Hey! Errichto, every time you pre-increment variables, why? Is it any time-saving trick?

[@moby_vyk]

pre-increment is usually faster (does not need to store a temporary). Let's say you want to implement it. The code is simply: int pre_increment(int& i) { i++; return i; } While for post-increment is : int post_increment(int& i) { int temp = i; i++; return temp; }

[@FazeelUsmani]

@@moby_vyk Wow! nice. Thanks! for the explanation

[@rustmc]

@@FazeelUsmani tbh with primitives like int it doesnt really make a difference, but its good practice anyways and it expresses what you are trying to do better

[@FazeelUsmani]

@@rustmc okay, I'll make use of it. Thanks Fox

[@mkgcodes]

For 2 days I cannot access LeetCode.

[@dominikwawszczak523]

Could you make a video about debugging? I mean about this stuff like debug()

[@nikhilgautam2857]

You don't need that level of debugging code to debug your code it is for complex problems like Np hard and bigger lines of code

[@dominikwawszczak523]

@@nikhilgautam2857 How do you know what I need?

[@nikhilgautam2857]

LoL if you needed it that badly you'd had that already Ps:- I got it in first try of Google it's not even that hard

[@dominikwawszczak523]

@@nikhilgautam2857 I don't think I need it "that badly". I just believe it's gonna help me a lot.

[@alimodz6253]

video is done and im still trying to understand the question

[@huoyuhao167]

I made an achievement of trying hours to derive a solution for this, but still wasn't able to....and I can't understand your approach....😥😢

[@sacchidanandverma8201]

When I opened the problem it was already solved 😂

[@arpitdixit9619]

@@vk-vz8qo It's fun vk

[@fiziblank2609]

sir, which keyboard do you use?

[@MatteoYTGaming]

Logitech UltraX Premium

[@jonathanharder8284]

What is the name of that cute teddy in the background, I'm asking for a friend.

[@mikemihay]

Python version please :D

[@bethsuni4011]

> INF = 1e9 + 5 I often see this when I watch competitive programming streams but I haven't figure out yet what it means. Can you please explain? (I mean what's so special about 1e9 + 5, and not say 1e9+4 or 1e9+6)

[@learnfromarandomguy7026]

Maybe this is also related to the number 42. The Answer to the Ultimate Question of Life, The Universe, and Everything.

[@mohamedelkaramany9863]

INF = 100005;

[@rentib9136]

5 is a magic number, the same goes for 7

[@bethsuni4011]

@@rentib9136 why not use 1e9 instead?

[@rentib9136]

sue gondeese, lets say that you have array of n numbers where it is said that array[i]

[@PavanKumar-jt5mq]

where is the timer?

[@Errichto]

I'm not using it this week. I can be calmer and explain more. I'm not saying that I explained things in detail in this problem :D

[@ChandraKanth7]

A better solution will be in O1 space

[@Errichto]

How do you want to do it in O(1) space?

[@ChandraKanth7]

Errichto Yes I guess you can keep the same array and keep updating it instead of creating another array. Then return the last value of the 2D array. And that is O(1) space.

[@Errichto]

@@ChandraKanth7 we keep and use the input array, so I would say it's O(H*W) anyway. But yeah, sometimes leetcode problems are about modifying the input without using extra space.

[@elandor3084]

errichto can u pl explain the algorithms ? i'm a begninner i would like to learn

[@rentib9136]

cp-algorithms.com/ thats a cool website with good descriptions of algorithms and nice implementations

[@openworld7585]

Please make a video talk to your subscrbers

[@openworld7585]

thank you so much

[@hassambitw]

what if we wanted to find the shortest path from every row instead of just the first one

[@Errichto]

In O(N*M) you can find distances from chosen starting cell to all other cells. If you want to do it X times, multiple the complexity by X.

[@syedmrinmoy6382]

Boss#errichto

[@vishalchaurasia96]

#errichto great Competitive Programmer

[@rentib9136]

not great but the greatest xD

[@ТимурИонов-я8б]

so, it’s just a Dijkstra algo