DSA(LEETCODE 150 CHALLENGE) | Beginner to Advanced

[00:00:00]Let's try to Not very different.

[00:01:40]So let's start the today's session guys.

[00:01:43]So I'm not able to come the last in the live in last two days because of the shifting right. Let's try to see now let's have to solve the last question Right.

[00:02:26]So first we have number of islands.

[00:02:34]So what is question? I think I made it this question. I solve this question within the DFS. You can right like how I solve it. uh like this question say like given you have given 2D matrix 2D grid right which represent the map of one one that means land and zero means water right so what we have to return the number of island okay and island is surrounded by the water formed by connecting all its vertical and horizontal okay adjacent land vertical horizontal we may assume that all the four edges is surrounded by okay outside that means outside from the so if you see the first test case like uh see one so one one one connected and that means this this from here to here from here to here and from here to like I hope you understand here this all are connected So there is only one line right one island and for here we have like we have this much is connected just this four this four so it's one island two island and three island yes so what you have to do just you have to do like uh go start start from the mat travel to the all the matrix That means grid and if you find the grid value is land then you have to just you have to search like how many land are connected through this point right like uh we have going first we are going to find the one now we are trying to see like how much is connected to this in the four side right from the up down left right okay So that's is this I doing I'm doing just like that like uh if it is one I have on the that mean this is the island and call the PFS like all the connected graph should be zero become zero right so I call the DFS and make that grid zero and from that grid we are traveling left right up down all the four direction right and if it is zero we have to just material or invalid right so let let me see let let me show you so it's like if you if it is out of the box this is the condition for checking the out of the box if it is what out of the box we have to just uh not take that and if it is greed is zero we have to not take and if it is one we have to again call the dfs right so we are just like doing that I'm returning the count value so this is the normal df You can use the PFS but I think the more efficient way is DFS here right?

[00:05:54]Yes, we solve. Now, next next question is like now region. Let's see what's your question. Uh I think here given the matrix of X containing the X and O.

[00:06:20]Okay. Capture the region that's rounded.

[00:06:22]Okay. So connect a cell is connected to adjacent cell horizontally or vertically. Okay, horizontally or vertically. That means you have to connect this this to this right vertically. To form a region correct okay to form a region connect every zero cell. Okay. And the round region is rounded if none of the zero cell in this region are on the edge of the board.

[00:06:51]Okay. Excess regions are completely enclosed by the X to capture the region.

[00:06:58]Replace all X all zero with X in place and this is the original board. You do not need to enter anything. Okay.

[00:07:08]But what I'm saying is you have to just capture it. Okay.

[00:07:16]So how can we approach what what is connected to adjust You have traveled all the ages right like uh first row first column last row last column last row last column right and count all the zero four not a zero but four all the four and try to traverse like try to bs like see how much zero is present on the edge and how much How many O that is connected region is present right? If it is if the all the connected region is present with the edge containing four that mean they are the not the rounded line otherwise all the rounded point let's see let's see we have one here so there is nothing connected there you see the one zero is here at zero so there is nothing connected in this way that's why it's become in the final answer is it remain zero but these all are become x that's why we are doing Like if it is first row we are taking and marking digit. If it is last row uh sorry last column we are taking and if it is last that means all the condition we are closing it. Now we are taking the cube and traversing for side from the if it is not zero we have to just continue. If it is zero we marked and proceed to and like and find if it is not if it is dictated we have to mark zero else we have to mark and return just you have to return this is not so much problem if you know the basic bfs and dfs and build like right you can obviously don't like that respect.

[00:09:44]I think I question you have given the graph right you have given graph in the node right you have to just you have to just return right okay in the point that's why I'm going right here like I'm calling from the node if it is not immediate if the node immediate we have to return the right we have to just right like from the perspective see that perspective like one one should be two and four rightfully.

[00:11:13]We have one. So going to one calling two calling and one right this address become 1 2 and address your address we have if it is first time visited we mark to give you and you can say that like the address is first we have to just IP address and final righting.

[00:12:20]Falling calling and returning. Right.

[00:12:39]Let's try next.

[00:12:50]of varation equations and pair of real numbers.

[00:12:57]We are going to assign a given pers and a and b that representable variable.

[00:13:34]What you have to do?

[00:13:37]Where you must find the answer.

[00:13:48]Okay.

[00:13:50]The answer cannot be determined. Return.

[00:13:54]Okay. Let's practice first one.

[00:14:07]Okay. So like 1 / it should be 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3.0 and B / 3 it should be 3.0 0. Right now a / c. That means we have a / c that means 3 / b / okay by What should be six? Okay.

[00:15:01]What's 1.5?

[00:15:24]Okay.

[00:15:27]So what we have to do here? Okay.

[00:15:32]We have to vector. Okay.

[00:15:35]We have a string vector / 2 and / k should be what? 1.

[00:15:54]Okay. Fine. That was good. Now let's see a / b and b / 6 also also divide and 3ide by that's going to happen right you are you are That's not going to happen. That's not going to happen because I just b a divide bid.

[00:16:42]Can I do like that?

[00:16:46]Okay.

[00:16:48]It's continuously just 2 P by A into P by Okay.

[00:17:25]So what we have to do like one of those graphical the graphical way.

[00:17:41]Sorry.

[00:17:46]Okay.

[00:17:52]Okay. Hello.

[00:18:01]A / 2. Okay. And B should be 1 by Z. Okay. Now we have we have now we have B / C should be 3.

[00:18:21]Okay.

[00:18:38]is one.

[00:18:40]Now the question we have we have to find like a b right c2 a we can go like c2. So we have 6 into 6 into a b= 3 into 8 into 3 and 2.

[00:19:20]Okay. So to see first question to C A will not take a parent to see yes I find it can I take like can I do like using the DSL Yes.

[00:19:59]Can I You can do it. Can I put Yes, you can go.

[00:20:19]Can I go? Yes, you can go.

[00:20:23]Now from C to B and from C2, right? So let's try to see let's try to be right.

[00:20:42]This is another max or and work and so let's try to see using DFS right what what I'm trying to say like let's try to see unordered map like un unordered unordered map Take value. End value. Okay. End value.

[00:21:42]And here now the second one.

[00:22:00]Okay. Question. Now get it.

[00:22:20]Okay. So, we have to take a string, right? And we have to take here a string.

[00:22:31]This do one thing we have to take a vector here string and the double double.

[00:22:50]Now how can we approach?

[00:22:55]We have we have to just find the sign. I what I want to Okay. So it should be the equation side.

[00:23:19]Equation side. Right. Now what can be your first like 10.

[00:23:28]Okay. Now we have we have four string right. So take one a what? This would be like an equation like this much equation.

[00:23:44]Equation I and equation I should be okay zero and the string B should be one. Equation I and equation I and one. Right? Now what we have to do just find the double value double what should be values values I correct now we have two questions first first dot post at two values B and the menus values. And the next question instead JSON dot a dot post could be the B could be the A and 1 / B.

[00:25:05]Right?

[00:25:07]We have to list within the graph. This is the graph. Now we have to take a vector vector vector double double answer and you have to just what what should be explain.

[00:25:42]Yeah.

[00:25:51]string just we have we have double b should be helper x x should be zero and x should be 1 one and the red is now we take away and you have to just return the return the answer right now how to write on the right we have a string a string a string This is the target value. So force spring force target and anything else.

[00:27:00]If this if you can't find this you have to return. is for the target is not found.

[00:27:09]Right? The target is not found. If the target is not found, you have to return.

[00:27:17]Yes. is not found. You have to just put back to the DSA here. for here like uh if the if the target if the like uh if the x is called function like if the if the adjacent found src that means not found not found or JSON dot adjac Just one thing here for Can I pass it just like that? I don't think so.

[00:28:36]Let's do one thing.

[00:28:40]Let's do one thing.

[00:29:04]I'm Okay. Now the question next with x0 and x1 and x.

[00:29:21]What should be the one double?

[00:29:27]Now the question is how can we have we first see like first map like map A to 2 and B A 1 by 2 B C B C B 3 and C C P 1 by 3 again next one nothing extra A right. So now A to go A to B. Okay. I'm going to A to B that means taking the value into two. Take the value that mean 1= 2 2.

[00:30:52]Now going from B from B we are going to A so it's not we can't go to the parents it's not so we can't go to parents right so we are taking we can't go to the parent okay parent we can't we have to we have to we have to use that right we have And now this is six. Next click on the six.

[00:31:33]If the target target is you have done the 6 minute This is three question.

[00:32:26]If target you have to just return the for adjacent target.

[00:32:50]one target. What should be written here? We find target.

[00:33:28]Just return one. Okay. Okay. Let's return 1.0 1.0 1.0 Okay.

[00:33:42]Now we have we have two double okay this will be what 1 okay 1 1 x that means yes not if the neighbor we have we ask like a I just remove just try to remove it from just try to remove just take only the pair right.

[00:34:26]So if the P if the driver never should be the first this should be the second parenthe into equal to no discussion into what uh never put second dot second.

[00:35:22]Okay. Second helper helper help first and target and parent will be what?

[00:35:57]Okay.

[00:36:06]Right.

[00:36:09]You have to take a parent here. What is the parent here?

[00:36:20]Here are lower character right making mistake somewhere.

[00:36:49]All right.

[00:37:13]From the map, we can't use the pair anymore.

[00:37:31]back.

[00:37:36]There is no I just like that I don't think so. You have to just you have to just like that. I don't like You have to use you have to take a vector right taking all the vector Uh back getting the vector input both input. Now we have to hear something else like what you subscri This is the vector.

[00:39:39]This is good.

[00:40:00]So let me see first any second particles and I get this question and X1.

[00:40:49]Okay. So, this giving the wrong answer one one we have to call like we are calling like one like we are calling from one to find the direct Okay.

[00:41:20]If again this right answer right answer and what this mistake 1 A to C, right? A= Yes. A to C. A C, right? So, A= to B. Oh, okay. Okay.

[00:42:04]We have B2. B2.

[00:42:08]So and just build a build a map right just again we have we have like a should be and many other ways no should be a then we have 1 by 1 by 2 1 by 2 and this should be c then we We have three.

[00:42:40]Yes. Three. And any other?

[00:42:43]No. Any other? Any other?

[00:42:47]No. Any other? No.

[00:42:50]Okay. And this is so C to B.

[00:42:57]Now B to A. We have B to A. Let's take B to A. So it's like into yes target is fine is fine then we have yes it's like 1 into 1 by 2 into for your life.

[00:43:53]Don't go anywhere, right?

[00:43:57]You have right state somewhere.

[00:44:20]Okay.

[00:44:23]Okay.

[00:44:26]should be the target and also so if that is fine if the file it has register If the target is fine, if it if the target is fine, right? Target is fine.

[00:45:01]You have no return.

[00:45:08]Okay.

[00:45:39]Yeah, I think Okay.

[00:45:50]The target is fine.

[00:45:53]We have the function and the target and the target and and the capacity right if it is if it is if it is greater than 1.0 Z that means the target should be fine right that mean.

[00:46:24]So we have to just do one thing return.

[00:46:55]evidence not We have going we have to target.

[00:47:45]Okay.

[00:47:48]A to B, B to A, right? We have to find we can find this for we have to return the right.

[00:48:05]If you find return, you have to continue the back. Next thing here like if you use the backing like not return one returning the true value here returning the true value here if you find that value okay let's do let's take a double value here setting here like except answer like. So if it is the target is found answer that what and just return the okay and what we have to do if else what will be done here first and the target target Just one second.

[00:50:00]So we have we have that if you have to If it is not enough what value the question that value into what value into what value do Good. Okay. Good.

[00:50:42]Good. 1.0. Good. And just remove the double here.

[00:50:48]And this and it might be good. Now let's try to see this.

[00:51:00]Okay.

[00:51:10]Now why are you giving the wrong answer why should be if it is not present then we have to use -1 what should be any target second.

[00:52:02]But they do not have to help us.

[00:52:32]You're not falling from I think that's not bad.

[00:53:25]Give me Father, very happy.

[00:54:36]Now this target and just like that.

[00:55:01]If it is return that means we can't find the connection between the yes if it return false we can't find the name connection so we have to return the And now the unign And one what should be what should the A and A. What should be the value?

[00:57:05]Repeat into a ting I do like a can I find a I don't think she can find it a A2 If we take a by b and if we take c by a then we can not find h we can't find right a by b a by doing just like else.

[00:58:07]If the sentence else.

[00:58:27]Try to feel like an I think just like so insert removable group is third.

[00:59:11]If it is See here.

[00:59:51]Okay, that's all good.

[00:59:53]adjacent fun.

[01:00:17]Okay. Thank you.

[01:00:20]visited.

[01:00:40]Anything else? No.

[01:00:45]Next model string string string the so we have to run that first practice.

[01:02:11]target.

[01:02:24]You have to find right you have to find like this should be contained then we have to adjent adjent found it's not project now just go and just continue here.

[01:03:09]Finally social cost rejected we have to mark in. Okay. If it is not if it is we have to continue right. If it is not visited, we have to not question.

[01:04:24]total number of you can take you have that for example for example the pair 01 indicate that you have to A 0 in this zero like this is the famous problem of the sort Right? You have to just detect the cycle is there. So either you can use the topological sort. Right? Just like I do logical for topological or either you can use the DFS TFS or cycle detection that just like that.

[01:05:50]So let's try let me just let me just just give you just remove all just remove all right let's try to build it so this is the question total you have taken and you have the area which could be right indicate that you must take you must take you first step like last step uh P B P B P B P B P B P B P B P B P B P B P first. Okay, if you want to have a graph like that 1 0 0 1 Yeah, this is You can't just We have to do this new x and what x right now if save there. So you have to just don't do it now.

[01:07:48]Now return the DFS the DFS. What should be the DFS content? DFS content. What should be the contain? So it should be practic value uh vegetated repeated B and false right and it should be the it should contain the part B and false. Now we have to take like we have to call from node zero node zero node to take a parent. Can I take a parent?

[01:08:38]You have to get right because already you have to get to the detail and the return then this must this one will fra Vector visited vector vector and direction. Now we have dated node and n should be right both should be true.

[01:09:29]Now go to call the neighbor adjacent adjacent node.

[01:09:41]If it is unvisited if it is unvisited unvisited of you have to call the driver function function. What will be fun? neighbor and the path and you if you find the root we have to return to else what we have to do as what what else if the path is true if path is you have to return the return What should we do? If the cycle is detected, then you have to put what you have to return the proof.

[01:10:39]You have to return the proof. At the last you have to return the cycle detection. That means not detected. Okay. Sorry. Edge is now edge.

[01:10:54]And right there what is this? What is this?

[01:11:32]Where I use the vector widget path What are you saying?

[01:12:36]Okay, let us go.

[01:12:48]cycle detection. Why should I explain should be written in vector?

[01:13:04]Yes, this should be written or return vector. Why? Why are you making me like why you you are start talking nonsense talking you start talking to the much so we have to just we have to just apply the topological sort just like I in the previous I have solved this problem right. I solve this problem and previously I solve this problem not present just here I sol this can finish but they change the quality What we have to do like you have to just do like topological sort right we have to do like a topological sort just like that and the previous solution of this like uh this one let us see I solve this Okay fine.

[01:14:43]So you want not want that much you won't want this but so what we have to do we have to just copy from here from here it just do minor changes. Now you are good to go.

[01:15:14]I just any you don't know this.

[01:15:28]Okay. I think I make a mistake here.

[01:15:34]I use the topological right.

[01:15:38]Okay. I made a mistake here. My function that mean I change I say like this function should be this.

[01:15:51]So I I think we have finished activator right and this is if there is for This can go with anyone here in affected parts development learning development. that much.

[01:16:51]Okay.

[01:16:54]So this is the famous cycle detection using right. So what what we have to do uh in the undirected undirected graph if we detect the cycle we have to just use the visited nodes right like uh if we again we get that node we we show that there is cycle but in directed graph there there might be a condition like we there is a complete different node complete different like like 1 2 2 3 and 3 2 4 Okay. 5 to 3. This right now question like we have 1 2 2 3 market all three to four all visited. There is no sacrificing part is already digited that mean that's not we have to maintain another vector like path right that's not the vit but the path should matter here right path should be that's that's why we are doing like path and n should be vited If the united we call that function if it is the path in that direction the path is already legited that means we have found right we are again this and path is also legited that mean there there is detection right else we have to just path for right that means we travel all one path one direction direct direction there is no cycle. That means we mark that all the from the one node we can't go to any cycle. You have to just mark that part.

[01:18:55]False.

[01:18:58]1 2 3 4 false the uh we can't go anywhere. Can't go anywhere. Can't go anywhere. In the last we can't go anywhere. We have to just false return. We can't go anywhere.

[01:19:20]False return. False return. False return.

[01:19:28]We can't go there.

[01:19:33]Yes.

[01:19:46]solve this problem.

[01:19:50]Let's try to solve it backing problem and problem.

[01:20:07]Okay, I have solved this problem.

[01:20:10]Uh I think I solved this problem in previous ABC and you have to start from the zero write the zero and this now you have to just like we have to that mean uh just do like takea 1 a b a By like one from here, right?

[01:20:58]A another four d a e from one like your two we are making like 2 three right two three. So taking one from two a from from two we take a and from D we are matching all this like D E F again from B E F again C D E F try to combine all the characters and all three letter or the four letters of the next right this this this question is this question this question n probleming nq I need to end that no string the solution should be. So this would be the this would be the famous problem of the if you if you solve the hand problem you can solve it both are same problem just you have to just return here like how many and the hand problem and your problem you have to create that one right you have to create one that all the should bear the same name Right? Like you have to place all the right and for this like for this you have to find out how many position we can how many solution we can.

[01:23:03]Now there is n that mean uh 9 into 9.

[01:23:10]Now how we proceed like this? Love and beauty all right.

[01:23:35]Okay.

[01:23:39]4 1 2 3 4 1 2 3 4 Yes. 4 in the morning.

[01:23:46]Thank you.

[01:24:04]What we have to do like so is right. You have to just filter the cell three and print out.

[01:24:19]Okay. Now call the call the help of function with integer value with integer value. Right? With the integer value.

[01:24:28]Now what we have to do?

[01:24:43]We have row number.

[01:24:48]What we have to do for it? The screen should be not present in the same row and not the same column and not the adjacent the right not this column. Can I do Can I do like column?

[01:25:15]Can I use column number? Yeah.

[01:25:20]Just call if then you have to return the one. Okay.

[01:25:33]So what we have to just call the uh like in solver int row vector mode.

[01:25:45]If = n minus one, you have to return uh 4 0 1 2 3.

[01:25:58]No, not last.

[01:26:08]Yeah, it's no should be last. We have done one.

[01:26:15]Now else four column zero column and column ++ if is valid that means we are presenting the mean we are presenting can I take here this is This will be not. This should be not.

[01:26:46]This should be not. Okay. Fine. Fine.

[01:26:50]Fine.

[01:26:54]And column.

[01:26:56]We have to mark that number C plus.

[01:27:13]Yes.

[01:27:27]Let's try to see like how can we approach like what what you are trying to see. Uh we have like a string a string s as a string s vector string as no you want to say like a string the string board the string and and and column right column and return the helper. Solver function. Solver function with the with the row hero and the board and right and just call that same helper fun what in row. Okay. And vector explain in bold and print. Now this you have to give in the row. In the row you have to we have to return one. Else you have to call value column should be and column plus if is valid.

[01:29:04]If it isn't valid row row column hold if it is valid you have to mark sorry row and column Queen win queen helper solver solver solver what solver what solver what should be solver what should be solver right what should be the solver row + one and column from here.

[01:30:08]Gold what? and and what code row and column and final one.

[01:30:39]Now in method int and the vector a string code for example Just you have to travel All right, bro.

[01:31:38]Simple board R and C.

[01:31:48]If the R and if it is row row if it is R I= Okay the same the hold I I and See this queen?

[01:32:26]Yes. You have to see you have that that means that means you have to take the two pointer ex R should be R and C should be C. Now what we have to do here are rater sorry greater than z and then less less than we have to check if if the if the if the four and since queen you have to return the false and rise and again we have to do like while r should be r greater than equal to and cateral.

[01:33:46]You have to change like the board the board R and C is equal to we have to return the statement else we have to just return the statement see this much is passing the test cases or not let's try to say okay so you are saying you can't understand that my solution sir what are you doing you can't understand there is Let's pray.

[01:35:03]Never tell me.

[01:35:28]Four.

[01:35:50]Right.

[01:35:52]This step.

[01:35:58]I think this not right. Next question.

[01:36:28]It's a combination of IS.

[01:36:34]and this question.

[01:36:41]Just like that. We have to solve this question.

[01:37:01]Maximize the number of accusation in S.

[01:37:04]Convert the continuous.

[01:37:20]Okay. Fine. Fine. Fine. Fine. Fine.

[01:37:24]All zero.

[01:37:26]Okay. So maximum one like we have like one one Yes.

[01:38:06]If it if it's one That's not I think the con is 1 one 1 0 1 1 1 0 and it's like a force.

[01:39:15]It's never sir. I solve this problem. Yes. today yesterday I think there's nothing that much you have to just find sum right if the sum is zero you get that value this is this all the standard for right all those standard form right and these all are the standard for like to solve it.

[01:40:15]I saw question.

[01:40:22]How can we approach?

[01:40:28]How can we close? Like uh we have 1 1 0 1 1 0 1 1 0 0 Let's start.

[01:40:50]Can I take like not surface.

[01:41:10]Hello.

[01:41:36]A I a - Y a I + 1 + max Right. So like one one project right here.

[01:42:06]Take one only. Take it.

[01:42:24]Yes. Yes. Yes.

[01:42:32]Zero.

[01:43:01]That means we have if it is one we can go to the next one.

[01:43:13]What we have to do? What we have to do?

[01:43:16]You have to starting index score all the ones.

[01:43:28]Starting index all the ones. All the ones the starting index this much. Let's try the same space as 1 0 0 0 1 0 0 1 6 0 4 1 Bless It's That means that means what?

[01:45:09]That makes sense.

[01:45:40]Just one 1 4 4 4 4 If we take this much.

[01:46:12]Okay.

[01:46:18]Okay.

[01:46:23]Keep repeating.

[01:46:25]We have 0 1 1 0 0 1 1 and 1 2 3 4 5 6 7 8. Now we have 2 three six. We have we have one. So 1 6 we have 1 - 1 and we have one and now what we have to do what we have Is it that much? That's now Uh we are taking that much 6 - 4 taking that one right.

[01:47:59]Okay. Now six we have to give like a six index starting you are taking like starting not starting a starting you have to take like a starting to end like group. You have to take starting from here. Starting ending start only one right 1 0 0 1 1 0 0 1 1.

[01:48:53]Now we have to get 1 2 3 4 5 6 7 8 9 10 11 12 13 14. So it's like 2 three. It's like 6 9. It's like take that much.

[01:49:16]If you take that much this much and what should be the ide different people.

[01:50:05]14 14 - 14 - 6 1 2 3 4 5 3 7 8 9 Now - 15 + 1 0.

[01:50:50]Now we are taking from here 9 - 2 + 1 8 + 14 - 9 14 - 9 from here this Yes, we are taking 14 15 - 5 3 - 3 - 1 from here we from here 6 - let's try to let's try to see right now let's try to say we have to If I come here group SP and SP right and group SP do what? 0.

[01:52:44]uh you have to take a c=0 if the s = 0 else we have to take i and ying and and and= + 1 and now whatever.

[01:53:43]You have to know what you want.

[01:54:04]Go dot post dot post back and I for you have to Just it.

[01:55:00]What?

[01:55:02]What? What?

[01:55:06]What should be the end?

[01:55:16]Now we have to take and max.

[01:55:35]That's we have starting with S and I here we are first one So as 5 Okay.

[01:56:27]Yes, that's all right.

[01:56:41]And next one plus one. Now, now starting from the starting, right?

[01:57:14]This one. This must be the starting start like left should be what? In minus what?

[01:57:26]In minus previous one, right? And right should be what?

[01:57:35]Right should be what? Right.

[01:57:39]In right next and answer and max will be and MX will be maximum of max of left or right.

[01:58:05]You have to return max answer. Sorry, Max.

[01:58:17]Let's try and see.

[01:58:37]Started the group started also started limit. That's it.

[01:59:17]Continue.

[01:59:41]1 comma 1 0 2 0 0 1 and 1 by one or the other one should present that we are wants to present like so we can't take like one can't do like we have to take like one this much we have to do Let's end the session here, right?

[02:01:11]Let's solve it now. Try to solve Yeah, I like myself.

[02:02:43]Let's end the session here.

[02:02:46]Okay. Okay.

[02:02:48]Sorry. Let's end the session here.

[02:02:51]Right.

[02:02:54]Last time.

[02:03:01]Thank you.