Shortest Path to Get All Keys II BFS II Bit Manipulation II BFS Visit More than Once II Leetcode 864

[@ARYANMITTAL]

Do Comment, uptill where you guys were able to think for this problem & what you guys learned in today's Problem ❤!! Checkout DSA-169 Series: kzbin.info/www/bejne/a3PYfImJYruhrdU Problem Link: leetcode.com/problems/shortest-path-to-get-all-keys/description/ Code & Notes: drive.google.com/file/d/1OxGaZe2jH-lXo1ry7Ay0UN_MIBnrLyvE/view?usp=sharing

[@GodOfFaith]

hey aryan i wanna ask you something thats very off topic , why don't you join google as an SDE ? i mean you can get referrals much easily as you are working in goldman sachs.... your coding skills are so good.... and thats why i was wondering.

[@morrisonsempire9354]

Can you please explain this doubt in the while loop if i dont use that size loop and direcly doing the increment of steps during popoing the element as i generally do any of bfs kind of questions then it is giving wrong answer in first 2 test case why?? while (!q.empty()) { vector curr = q.front(); q.pop(); ++steps; if (curr[0] == (1 = 0 and newrow < n and newcol >= 0 and newcol < m) { char ch = grid[newrow][newcol]; if (ch == '#') continue; if (ch >= 'a' and ch (ch - 'A') & 1) == 0) continue; if (!visit.count(to_string(keys) + " " + to_string(newrow) + " " + to_string(newcol))) { visit.insert(to_string(keys) + " " + to_string(newrow) + " " + to_string(newcol)); q.push({keys, newrow, newcol}); } } } }

[@Yashcolab]

that 9:21 moment came and i was totally unprepared for it lmao XD

[@sherlockjunior8612]

Why is no one talking about what he says here: 9:18 XD

[@tejuschaturvedi6234]

excellent explanaton for such a tough question .

[@SurajYadav-py1do]

amazing explanation bro

[@anexocelisia9377]

was waiting

[@muskankashyap1776]

code is failing at test case ["@...a",".###A","b.BCc"]..

[@adityaanand799]

yess it is failing on this

[@adityaanand799]

@ARYANMITTAL

[@a.yashwanth]

It's passing for me. Here is my java code. class Solution { public int shortestPathAllKeys(String[] grid) { int m = grid.length, n = grid[0].length(), totalKeys = 0; Queue q = new LinkedList(); int[][] dims = new int[][]{{-1,0}, {0, 1}, {1, 0}, {0, -1}}; for(int i=0;i= 'a' && c

[@dewanshpatle9056]

man those jokes in middle are really awesome, you are a great explainer. Thanks for all the hardwork ❤.

[@ankurchaudhary924]

Note::: that the goal is to obtain all the keys not to open all the locks.

[@aryamanagarwal1977]

Sir I saw your baap graph series and legit it was the best graph plyalist I have seen so far , and I was able to solve this question myself Great work sir BTW I am also from mnnit (cse)😅😅😅

[@hitengoyal5457]

Why can't we apply dijkstra algorithm?

[@SachinKumar-cd1sg]

here the graph is not weighted so need to apply dijkstra

[@sahilyadav5662]

why you have used the loop for(int i=0;i

[@yugaanshgautam6893]

to update steps efficiently, you require one step to proceed to the next level in the graph.

[@beinghappy9223]

Toughest question I faced so far Btw amazing explanation .

[@jagratgupta8392]

Very tough ques bhaiya 😅😅...got the intuition but solving and checking each and every thing was really confusing and tough ....you explained really well❤❤

[@asthajain2511]

Cant we apply dfs here ??

[@ARYANMITTAL]

Nopes, forget keys, locks and obstacles, if i had asked you give me shortest path to reach from x1,y1 to x2, y2. How will you have solved it via DFS? It just traverse the path depth wise, thus only making sure that we reach that point, and not in shortest time/distance.

[@anexocelisia9377]

@@ARYANMITTAL can we apply bfs everytime we need to find the shortest path?

[@raunakkumar6144]

@@ARYANMITTALWe can use dfs with backtraking to solve it write ,yeah it will be exponential complexity ,but we can right?

[@a.yashwanth]

@@raunakkumar6144 Yeah you can but you'll get tle cuz you for sure will traverse more than the optimal number of steps for each path.

[@pool477]

Future striver

[@a.yashwanth]

Much better than striver. Striver explains basic concepts well but aryan explains advanced concepts and shortcuts.

[@animesh414]

kya ham dfs se ye problem solve nhi kr skte kya ?

[@shlokjhunjhunwalakol]

Can anyone tell me why my code is giving tle 😭😭😭 class Solution { private: bool isValid(vector& grid, int i, int j, int m, int n, vector& keys){ if(i=n || grid[i][j]=='#')return false; if(grid[i][j]>='A' && grid[i][j]

[@gyanaranjansahoo6258]

if (c >= 'A' && c > (c - 'A')) & 1) == 0) { continue; } in this part can't we do ((1 >> (c - 'A')) & 1) == 0 insted of ((keys >> (c - 'A')) & 1) == 0 ?

[@koushikboddapalli4400]

Whats wrong with this code...please figure it out... thanks in advance vector directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int shortestPathAllKeys(vector& grid) { int n = grid.size(); int m = grid[0].size(); int x = -1,y = -1,max_len = -1; for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) { char c = grid[i][j]; if(grid[i][j] == '@') { x = i; y = j; } if(grid[i][j]>='a' && grid[i][j]=0 && nx < n && ny>=0 && ny < m && grid[nx][ny]!='#'); }; int steps = 0; while(!q.empty()) { int size = q.size(); for(int i = 0;i < size;i++) { int keys = q.front().first; int curr = q.front().second; q.pop(); if(keys == (1 = 'a' && c

[@CristianoRonaldo-ku1uz]

Can you help me with the code. Getting WA on TC-13 I think I have to do backtracking properly but not getting how to do it. class Solution { public: int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; vector grids; multiset st; void help(vector&vp, multiset stcpy, int &i, int &j, int &ans,int sol,vector vis){ if(vp[i][j]==INT_MAX){ return; } if(vp[i][j]==INT_MIN && stcpy.find(grids[i][j]-'A')==stcpy.end()){ return; } if(stcpy == st){ ans = min(ans,sol); return; } vis[i][j] = 1; for(int l =0; l=0 && sti=0 && stj=0 && vp[sti][stj]

[@a.yashwanth]

For shortest path problems we do bfs. Why did you start solving with dfs?

[@shwetanshusood9450]

Can you help me with this code.. i am not getting how to do it The general public often body shame the people who are obese or not beautiful as per their standard of weight. They do not even consider that it might be a medical condition for some people. Because of this, the people start doubting themselves and start cutting them off from the general discussions or the public places. To fight body shaming and spread awareness about the issue, an event is conducted in the city where people are participating and are ranked according to their weights from highest to lowest. The people with the same weights are ranked the same. There are N people who have already participated. The official has noted their weight and has ranked them. The problem is, he has fallen sick and there are still P people who are left to rank and participate. Considering this, you are expected to finish the process and provide the rank of the P people. Once the person is ranked, his weight is included in the category and the weight of the new person will have to consider this weight also to be ranked. To help you out, the new P people are organized in a queue in increasing order of their weights. Input Format The first line of input consists of two space-separated integers, N and P, number of people already ranked and number of people left to be ranked respectively. The second line of input consists of N space-separated integers arranged in decreasing order, representing the weight of the N people. The third line of input consists of P space-separated integers arranged in increasing order, representing the weight of the P people. Constraints 1

[@namanchandak1532]

What is the error in my code it is failing the below test case ["...#","a..@","#..#","b.#B",".##A"] class Solution { public: int n,m; int dfs(vector& grid,int i,int j,int lock,set&st,vector&dp) { if(i=m || grid[i][j]=='#') return 1e9; if(lock==0 ) return 0; cout

[@shlokjhunjhunwalakol]

Can anyone tell me why my code is giving tle 😭😭😭 class Solution { private: bool isValid(vector& grid, int i, int j, int m, int n, vector& keys){ if(i=n || grid[i][j]=='#')return false; if(grid[i][j]>='A' && grid[i][j]

[@shlokjhunjhunwalakol]

Can anyone tell me why my code is giving tle 😭😭😭 class Solution { private: bool isValid(vector& grid, int i, int j, int m, int n, vector& keys){ if(i=n || grid[i][j]=='#')return false; if(grid[i][j]>='A' && grid[i][j]

[@shlokjhunjhunwalakol]

Can anyone tell me why my code is giving tle 😭😭😭 class Solution { private: bool isValid(vector& grid, int i, int j, int m, int n, vector& keys){ if(i=n || grid[i][j]=='#')return false; if(grid[i][j]>='A' && grid[i][j]

[@shlokjhunjhunwalakol]

Can anyone tell me why my code is giving tle 😭😭😭 class Solution { private: bool isValid(vector& grid, int i, int j, int m, int n, vector& keys){ if(i=n || grid[i][j]=='#')return false; if(grid[i][j]>='A' && grid[i][j]