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)
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 🤞🍀🙏
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
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 😇
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
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;
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 ❤❤❤🩹❤🔥
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 ?
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; }
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 ?
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
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.
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){
@@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?
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)
Get well soon sir .
No problem bhai, get well soon, I'm sure you have a full time job+ making avg 2-3 videos everyday, take some rest!
Get well soon, bro! Without you, solving this question wouldn't have been possible. Thanks.
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❤❤
Thanks Jyotishmoy ❤️
This is the cleanest explanation for this Qn. I should have come here directly instead of going to Leetcode discuss
A very underrated channel!
The best explanation for this question on youtube!!
Thank you so much Karan ❤️❤️❤️
How easily you went through his man. This is a beauty ❣
I feel sad I couldn't even think of BFS
Splendid and loved your explanation bhaiya. I love how you teach us like big brother. Hats off!!
Thank you so much 😀
thankyou sir , it was initially hard question for me but after ur explanation its easy for me
Glad to hear that 😇🙏
Best channel for coding😍
Means a lot 😇🙏
this is the best video with best explination i was stuck in this problem for so long ........
thanks
i think you should be mentorship in any plateform you r amezing
your way of teaching is omg fabulous....Also your voice is too good. You are too good.
Thank you. Means a lot 🙏😇
This guy is gifted literally
When I hear you, then I read the Qn it seems so so easy
Happy that it's a long video as I need more in-depth knowledge on how these Qns are solved.
Outstanding explanation. Thanks a ton.
I don't see video length before watching your video. It's all worth it!!
It means a lot. Thank you so much 🙏❤️
very nice and smooth explaination. You taught with so much patience. Thank You
You are welcome! 😇🙏
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 🤞🍀🙏
❤️❤️❤️
True
i used map for coordinates...loved your mathematical approach
I really hope your channel reaches greater audience, and you have all your wishes true!!
You made my day.
Thank you so much for your kind words ❤️❤️❤️🙏👍🏻👍🏻
Thanks sir. It's my first video here. But you were marvelous
Welcome to my channel Sanskar ❤️
I hope we learn and grow together
Thanks sir, I am waiting for you video
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
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 😇
So glad to know 💕
maza aagya explanation dekh k
what a question with a beautiful explanation 👏
Glad you think so! 😇🙏
You are simply shockingly amazing
Great video bhaiya , awesome
was waiting for whole day
what an explanation man ! great
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
Thank You so much for your great explanation😁
soo well explained!!!!
Code Quality 🔥
Great explaination as always...❤
Get well soon bro ❤️
Osm explanation 💣
This is a masterpiece 🔥
yes mic bhai BFS KA khaandani code hoga maza aagyi 😂😂😂😂
amazing explanation.
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;
}
}
❤️❤️❤️
You are a gem. Thanks For JAVA
@@codestorywithMIK thank you bhai, means a lot ♥
Thanks for java
Best😇
Was waiting for this video
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 ❤❤❤🩹❤🔥
So so happy to hear
Thank you so much 😇🙏
Also, Today’s POTD just being uploaded now 🙏🙏
Sir can u explain the intuition behind the formula used for rows and columns
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.
mind blowing
Thanks a lot
After seeing this channel - "Bawaal cheej hai be"
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 ?
Please paste the Recursive solution as well.
Also, get well soon:)
you ar greate
Thanks a lot ❤️
my doubt in this question is why we are not making visited of board[r][c] value not true when the val!=-1
🔥🔥
Bhaiya, How can the same question be asked Or some modified version of the same) to test DFS concept?
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;
}
I think there is a small issue there :
row = (n-1) -(value-1)/n
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
Both can be done simultaneously.
Time management will play a key role here. However it will be a tight schedule
@@codestorywithMIK Thank-you
Why DFS is not working here?
1st like & comment...
Sir can you explain Median of a row wise sorted matrix Please
Sure ShaShank.
Let me add this to my list too.
Soon coming.
Can you share the link of the qn
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 ?
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
Bhaya ye condn khri h ki no subsequent ladder
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;
}
};
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.
Thanku bhaya for helping me out
Finally
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;
}
If we solve it by dfs the time complexity will be 6^n. ?
6^n*n
@@AnandKumar-kz3ls whats the other n for
@@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
Can this question be considered as backtracking question as well?
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.
@@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?
Hmm 🤔 , you can say so
please post java code also or explain during video
Sure thing 🙌
In current videos, i now also post JAVA code as well.
support++
dude's a fuckin legend!!!
Was waiting for this video