Snakes and Ladders - (Microsoft, Amazon, Adobe..) : Explanation ➕ Live Coding

[@jyotishmoydeka6804]

Don't ask for apology bhaiya.. You are doing so much for us.. WE all will forever be grateful to you.. Take care and get well soon❤❤

[@codestorywithMIK]

Thanks Jyotishmoy ❤️

[@codestorywithMIK]

Sorry for delay as I am not well. Got cold :-( Time Complexity : Since in worst case, we will visit all the cells and there are n^2 cells, so time complexity will be O(n^2) Space Complexity : We took visited array of size n^2 and also in worst case, our queue will have n^2 elements. So Space Complexity will be O(n^2)

[@yashaggarwal825]

Get well soon sir .

[@atifhu]

No problem bhai, get well soon, I'm sure you have a full time job+ making avg 2-3 videos everyday, take some rest!

[@ayusshrathore]

Get well soon, bro! Without you, solving this question wouldn't have been possible. Thanks.

[@nagmakhan672]

This is the cleanest explanation for this Qn. I should have come here directly instead of going to Leetcode discuss

[@kj1250]

A very underrated channel! The best explanation for this question on youtube!!

[@codestorywithMIK]

Thank you so much Karan ❤️❤️❤️

[@souravjoshi2293]

How easily you went through his man. This is a beauty ❣ I feel sad I couldn't even think of BFS

[@shabananoor9423]

This guy is gifted literally When I hear you, then I read the Qn it seems so so easy

[@sakshamlatwal3926]

this is the best video with best explination i was stuck in this problem for so long ........ thanks

[@gaurimandot5788]

Best channel for coding😍

[@codestorywithMIK]

Means a lot 😇🙏

[@shivsakthi37]

Doing videos for students continuously irrespective of likes subscribers shows your efforts bro hope you continue to provide the content for long run even after getting subscribers unlike many 🤞🍀🙏

[@codestorywithMIK]

❤️❤️❤️

[@AlishaKhan-ww3io]

True

[@souravjoshi2293]

Happy that it's a long video as I need more in-depth knowledge on how these Qns are solved.

[@rounaq_khandelwal]

I really hope your channel reaches greater audience, and you have all your wishes true!!

[@codestorywithMIK]

You made my day. Thank you so much for your kind words ❤️❤️❤️🙏👍🏻👍🏻

[@k-CE-OmkarPathak]

I don't see video length before watching your video. It's all worth it!!

[@codestorywithMIK]

It means a lot. Thank you so much 🙏❤️

[@lavishalakhmani1211]

your way of teaching is omg fabulous....Also your voice is too good. You are too good.

[@codestorywithMIK]

Thank you. Means a lot 🙏😇

[@honey6567]

i think you should be mentorship in any plateform you r amezing

[@rashisingh902]

very nice and smooth explaination. You taught with so much patience. Thank You

[@codestorywithMIK]

You are welcome! 😇🙏

[@Rajat_maurya]

i used map for coordinates...loved your mathematical approach

[@iamnoob7593]

Outstanding explanation. Thanks a ton.

[@doomhead9109]

Thank you soo much for giving this much efforts , I can't express my feeling how much clarity I got and I have already read the solution on gfg watched 2-3 videos on youtube and finally now I understood again ThankYou 😇

[@codestorywithMIK]

So glad to know 💕

[@sanskardhyani4112]

Thanks sir. It's my first video here. But you were marvelous

[@codestorywithMIK]

Welcome to my channel Sanskar ❤️ I hope we learn and grow together

[@karankulshrestha4708]

Thanks sir, I am waiting for you video

[@iWontFakeIt]

I think we can do this in a simpler way by storing all the values in a single array and then traversing the array, then we don't have to find coordinates every time class Solution { public: int snakesAndLadders(vector& board) { // seems like MSBFS should be applied int n = board.size(); vector vBoard; for(int i=n-1; i>=0; i--){ vector temp = board[i]; int diff = n - i; if(!(diff & 1)){ // right to left // reverse it reverse(begin(temp), end(temp)); } for(auto& e: temp) vBoard.push_back(e); } vector visited(n*n, false); queue q; q.push({0, 0}); visited[0] = true; while(!q.empty()){ auto f = q.front(); q.pop(); int node = f.first, dist = f.second; if(node == n*n - 1) return dist; // visit neighbours for(int move=1; move

[@39_jatinjain4]

what a question with a beautiful explanation 👏

[@codestorywithMIK]

Glad you think so! 😇🙏

[@pritishpattnaik4674]

Great video bhaiya , awesome

[@udaytewary3809]

You are literally legend bhaiya first I am not able to understand the question but seeing it's big statement and then the moment you explain about the question it got very clear to me. Just one doubt bhaiya can you please explain how you created the visited array and the concept of row top and bottom And you Said it right bhaiya hme Ratna nhi haa indpeth samajhna aur isiliye hme aape pura bharosa ki apke padhane se saare doubt clear ho jayenge

[@AlishaKhan-ww3io]

You are simply shockingly amazing

[@aftereffectstraining7668]

maza aagya explanation dekh k

[@GeneralistDev]

was waiting for whole day

[@mdkashifraza2603]

Thank You so much for your great explanation😁

[@yashnarkhedkar3734]

Code Quality 🔥

[@shivsakthi37]

Get well soon bro ❤️

[@prnvsgr]

Was waiting for this video

[@MrKalwar]

what an explanation man ! great

[@arjunsolanki752]

Great explaination as always...❤

[@Mohit-uq7hq]

soo well explained!!!!

[@waqarhashim8673]

yes mic bhai BFS KA khaandani code hoga maza aagyi 😂😂😂😂

[@DevOpskagyaan]

This is a masterpiece 🔥

[@JJ-tp2dd]

Thanks bhai again. Below is the Java solution: class Solution { int n; public Pair getCoordinate(int num){ int RT = (num - 1)/n; int RB = (n - 1) - RT; int col = (num - 1) % n; if((n%2 == 1 && RB%2 == 1) || (n%2 == 0 && RB%2 == 0)) col = (n - 1) - col; return new Pair(RB, col); } public int snakesAndLadders(int[][] board) { n = board.length; int steps = 0; Queue q = new ArrayDeque(); boolean[][] visited = new boolean[n][n]; visited[n-1][0]= true; q.add(1); //bfs while(!q.isEmpty()){ int N = q.size(); while(N-- > 0){ int x = q.peek(); q.poll(); if(x == n*n) return steps; for(int k = 1; k n*n) break; Pair coordinate = getCoordinate(val); int row = coordinate.first; int col = coordinate.second; if(visited[row][col]) continue; visited[row][col] = true; if(board[row][col] == -1) q.add(val); else q.add(board[row][col]); } } steps++; } return -1; } } class Pair{ int first; int second; Pair(int first, int second){ this.first = first; this.second = second; } }

[@codestorywithMIK]

❤️❤️❤️ You are a gem. Thanks For JAVA

[@JJ-tp2dd]

@@codestorywithMIK thank you bhai, means a lot ♥

[@wearevacationuncoverers]

Thanks for java

[@AnkitSingh-tm5dp]

Osm explanation 💣

[@harikeshsingh93]

amazing explanation.

[@NatureLover-oq6uc]

Best😇

[@EB-ot8uu]

mind blowing

[@Imrockonn]

1st like & comment...

[@shashanky1502]

🔥🔥

[@yuvhrajverma9665]

Sir can u explain the intuition behind the formula used for rows and columns

[@tutuimam3381]

Thanks a lot

[@HealthyOm]

really really i enjoying ur vedios bhaiaya ur really god for us .... u truely removed fear of programming from us .... love love love u big love u bhaiaya love u ❤❤❤‍🩹❤‍🔥

[@codestorywithMIK]

So so happy to hear Thank you so much 😇🙏 Also, Today’s POTD just being uploaded now 🙏🙏

[@gui-codes]

After seeing this channel - "Bawaal cheej hai be"

[@husler7424]

Please paste the Recursive solution as well. Also, get well soon:)

[@honey6567]

you ar greate

[@codestorywithMIK]

Thanks a lot ❤️

[@lockyer8315]

Doubt: Why only the tail ladder box is marked visited and not the head ladder box? considering tail and head being two ends of a ladder/snake.

[@karandhiman6510]

can anybody explain me how this is handling the case where we have continuous ladder or snake like from 1 to 7 and then from 7 to 15 its mentioned in the question that we should only take one ladder or snake per move ?

[@jatingarg5846]

my doubt in this question is why we are not making visited of board[r][c] value not true when the val!=-1

[@shabananoor9423]

Finally

[@manishasaini307]

Hello Bhaiya ek suggestion chahiye thi ki development or dsa ek sath nhi ho skti kya. Ya phle ek kro phir second pe focus kro

[@codestorywithMIK]

Both can be done simultaneously. Time management will play a key role here. However it will be a tight schedule

[@manishasaini307]

@@codestorywithMIK Thank-you

[@drbullah1388]

Bhaiya, How can the same question be asked Or some modified version of the same) to test DFS concept?

[@shashankshandilya1517]

Sir can you explain Median of a row wise sorted matrix Please

[@codestorywithMIK]

Sure ShaShank. Let me add this to my list too. Soon coming. Can you share the link of the qn

[@akki8534]

Why DFS is not working here?

[@whatstoday209]

Why does this give a runtime error when finding row and column? int row = (n-1)-(value-1/n); int col; if(row%2 == 0) { //even row->right to left col = (n-1)-(value-1)%n; } else { //odd row -> left to right col = (value-1)%n; }

[@codestorywithMIK]

I think there is a small issue there : row = (n-1) -(value-1)/n

[@udaykulkarni5639]

dude's a fuckin legend!!!

[@adhikari669]

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder ..... bhaya is cond ko kaise handle kr rhe h ?

[@codestorywithMIK]

If you notice, we never visit a cell again ever. With the help of visited array. So it’s guaranteed we won’t visit any cell (be it snake or ladder) again

[@adhikari669]

Bhaya ye condn khri h ki no subsequent ladder

[@adhikari669]

class Solution { int n; public: void get (int s,int &row,int &col){ row = n-1-(s-1)/n; col = (s-1)%n; if((n%2==1 && row%2==1)||(n%2==0 && row%2==0)) col = n-1-col; } int snakesAndLadders(vector& board) { n=board.size(); vectorvis(401,0); int row,col,step=0; queuemy; vis[1]=1; my.push(1); while(!my.empty()){ int l= my.size(); while(l--){ int curr=my.front(); my.pop(); if(curr==n*n) return step; for(int i=1;in*n) break; get(curr+i,row,col); if (vis[curr+i]==0){ vis[curr+i]=1; if (board[row][col]!=-1 && vis[board[row][col]]==0) my.push(board[row][col]); if (board[row][col]==-1) my.push(curr+i); } } } step++; }return -1; } };

[@codestorywithMIK]

Yes, it means that when you encounter a ladder, you go to certain cell, then from that cell again if you see subsequent ladder you don’t jump again at that time. So if you notice, when you push elements in queue, for a value x, you only find the value where it goes and just put it in the queue (see the else condition), you don’t further put the element where the subsequent ladder take you further at that moment.

[@adhikari669]

Thanku bhaya for helping me out

[@dikshantyadav1110]

Can this question be considered as backtracking question as well?

[@codestorywithMIK]

I think not. In backtracking, we consider a cell and then don’t consider it as well. And explore both paths. Here we are not doing that.

[@dikshantyadav1110]

@@codestorywithMIK okay. Just an example, if we solve this question by iterating from 1-6 and get the minimum from each of the paths provided from 1-6. So with the help of memoization would then be backtracking right bro?

[@codestorywithMIK]

Hmm 🤔 , you can say so

[@piyushacharya7696]

support++

[@maheshvarandani1308]

If we solve it by dfs the time complexity will be 6^n. ?

[@AnandKumar-kz3ls]

6^n*n

[@maheshvarandani1308]

@@AnandKumar-kz3ls whats the other n for

[@AnandKumar-kz3ls]

@@maheshvarandani1308 for each cell we have 6 possibilities to explore in worst case so time complexity would be 6^n*n where is length of board

[@AnandKumar-kz3ls]

i spent so much time how to get indexes from number but not able to comeup with approch so i decided just make another vector and store the values bool flag=true; int cnt=0; for(int i=n-1;i>=0;--i){ if(flag){ for(int j=0;j=0;--j){ dest[++cnt]=board[i][j]; } } flag=!flag; }

[@Shreyachoudhary13]

please post java code also or explain during video

[@codestorywithMIK]

Sure thing 🙌 In current videos, i now also post JAVA code as well.

[@souravjoshi2293]

Was waiting for this video