Infosys SP & DSE Exam Most Repeated Questions 1-Shot Video | Infosys Exam Questions | OnlineStudy4u

Added: 2026-05-06

[00:00:02]Hello everyone, welcome or welcome back.

[00:00:04]Today we are going to see some Infosys SP and DSC coding questions. As we all know Infosys has started asking DP trees and graphs in your assessment and only DP trees and graphs have been asked mainly.

[00:00:18]So, that is why we have brought today DP trees and graphs. All the topics we are going to cover in this video, okay? So, let's start with the first question.

[00:00:30]These are all lead code medium level questions, okay? Medium to hard.

[00:00:34]Now, this is the house robber three question. There are multiple house robber questions, but this is one of the most trickiest among them.

[00:00:42]Now, what does this say? The thief has found himself a new place for his thievery again, okay? There is only one entrance to this area called the root.

[00:00:54]So, let's see the input. So, you will have a tree and only one place you can enter the tree from, that is the root.

[00:01:02]Besides the root, each house has one and only one parent house. So, each node is having only one parent.

[00:01:10]After a tour, the smart thief realized that all houses in this place form a binary tree.

[00:01:17]So, all the houses are forming a binary tree, that's how your input is being given. It will automatically contact the police if two directly linked houses were broken into on the same night.

[00:01:29]Two directly linked houses were broken into on the same night. What does it mean? If two adjacent houses are being broken into on the same night. Given the root of the binary tree, return the maximum number of money the thief can rob without alerting the police, okay?

[00:01:45]So, the maximum number of amount of money the thief can rob without alerting the police.

[00:01:50]Now, what does the problem say? This is the input, that will be a tree, a binary tree.

[00:01:56]When will the police get alerted? When the thief is robbing two adjacent houses, that means this three node and this three node. If these two nodes are being robbed, then the police will be alerted. But if this three, this three and this one are being robbed, it is not adjacent because there are two nodes in between them, right? Each of between each of them, between this three and three there is two. Between this three and one there is three. So, that means these are not adjacent. And also three and one are also not adjacent because they're not linked together, correct?

[00:02:28]Directly not linked together.

[00:02:30]So, that makes them that makes the thief's work easy.

[00:02:36]Now, this is your input.

[00:02:38]Three, two, three, three, two, three, then null because there is no left child for the node two and there is three and three, null, one. Again, there is no left child for this number three node and there is one.

[00:02:54]Now, the question asks you maximum amount the thief can loot, right? So, maximum amount would be three plus three plus one, that means seven.

[00:03:04]Similarly, over here in another example, you will see three, four, five, two, one, three, one. Right? So, what can be the maximum amount?

[00:03:12]Uh explanation, maximum amount of money the thief can rob is four and five. Why four and five? Because see, these are not adjacent. If you wanted to loot, uh let's say three, four, one like this, then it would have become adjacent. This makes eight, right? But this would have become adjacent. Or let's say three, five, one. This would have also become adjacent. That is why we chose four and five. Now, we will come towards a uh formula how to solve this in our dry run, but the let's see the constraints.

[00:03:42]So, the number of nodes in the tree is in the range 1 {comma} 10 ^ 4 and node values between 0 and 10 ^ 4.

[00:03:49]Now, why did I choose uh these kind of questions from lead code itself? See, lead code has multiple story-based questions and Infosys asks a lot of story-based questions. They don't ask you direct questions, okay? They will not give you a direct graph and say that solve it. They'll ask you story-based questions. There will be a long story and you have to understand things from that story. Half of your time will go during you reading the story itself.

[00:04:15]That is why I took these kind of story-based questions, okay?

[00:04:20]Now, let's see the ideology behind solving.

[00:04:23]First, the greens represent robbing and the reds represent not robbing.

[00:04:30]What do I mean by this?

[00:04:31]You have two choices for every house, right? You either want to rob the house or you don't want to rob the house because they might be adjacent.

[00:04:41]Now, let's come from the lower most node, okay? Let's start from seven, let's say.

[00:04:46]This node in the lower most right corner.

[00:04:50]For seven, you have two options. I have created one array of space two, of length two.

[00:04:57]In this area, I will fill whether I want to rob the house or I don't want to rob the house. If I rob the house, then what is the amount I will get? And if I don't rob the house, what is the amount I will get?

[00:05:10]If I rob the house, that amount is denoted in green and if I don't rob the house, that amount is denoted in red, okay? I have already written everything previously because I don't want to waste my time writing on screen right now because we have to cover a lot of questions and time is less.

[00:05:27]Okay. If we rob seven, then we get seven. If we don't rob seven, then we get zero.

[00:05:33]Let's come to node number eight. If we rob rob this node, we get eight. If we don't rob this node, we get zero.

[00:05:43]Now, let's come to its parent two. Both of their parents are two.

[00:05:49]What if we rob two? What do we get?

[00:05:51]Only two. Not two plus eight plus seven.

[00:05:55]Why? Because we cannot rob adjacent houses. Adjacent of two is eight and adjacent of two is seven. We cannot rob them. That is why our only amount we get is two.

[00:06:05]But what if we don't rob two? If we don't rob two, then we have the opportunity to rob eight and seven. And eight and seven, if you rob eight, we get eight. If you rob seven, we get seven. Eight plus seven, total amount is 15. That is why if we don't rob two, then we get eight plus seven, 15. So, we get a higher amount if we don't rob two.

[00:06:28]So, that is a better uh option for the thief to choose.

[00:06:33]Let Let's come to these nodes, nine and three.

[00:06:36]What happens if we rob three? We get three.

[00:06:39]What happens if we don't rob three? We get zero.

[00:06:45]Let's come to its parent, nine.

[00:06:47]What if we rob nine? We get nine because we cannot rob its adjacent three.

[00:06:52]What if we don't rob nine? Then we have the option to rob three, okay? We are going from bottom to top, okay?

[00:07:00]Now, we have nine and three for these two nodes. Now, let's come to the top most node, that is one.

[00:07:07]What if we rob one? Will we get one? No.

[00:07:12]Why not no?

[00:07:13]If we rob one, we also have options to choose from where we did not rob nine and where we did not rob two.

[00:07:23]What did I mean?

[00:07:24]If we choose one, we cannot choose nine and two, but we can choose three, eight and seven.

[00:07:31]But we don't have to go back to three, eight and seven again because we have already calculated the values for three, eight and seven. The value for choosing three in case of nine, that is when we are not choosing nine, will be three.

[00:07:44]The value for choosing eight and seven when we are not choosing two would be 15, right? So, that means three, eight and seven are already calculated.

[00:07:54]So, what will be my total value for this node one if you want to rob this node one? That is where the thief is entering from. This is the door.

[00:08:02]And the path the thief chooses, that is what we want to calculate.

[00:08:07]So, what does the path that What is the path the thief chooses? 1 plus 3 plus 15. One is for one itself, that is coming from node one.

[00:08:17]Three is coming from when we don't choose nine, that means we choose three.

[00:08:22]And 15 is coming from when we don't choose two. Nine and two are adjacent, so it is 15, eight and seven.

[00:08:30]Okay? So, it is robbing one, three, eight and seven. So, it is 1 plus 3 plus 15.

[00:08:36]Got it?

[00:08:37]1 plus 3 plus 8 plus 7 is one That is how I wrote 1 plus 3 plus 15, 19 because these values are already calculated.

[00:08:45]That is how in case of trees, you can do it.

[00:08:50]Now, what if you are not robbing one over here?

[00:08:53]>> [clears throat] >> We have options to choose from all of the nodes now.

[00:08:57]What do I mean by that? We don't want to go to all of the nodes. We only want to go to nine and two because the previous node values are already calculated.

[00:09:07]If we don't choose one, we have the option to choose from the maximum values of nine and two.

[00:09:14]Whatever max value of nine is there, we'll take that.

[00:09:18]That is nine. Whatever max value of two is there, we'll take that. That is 15.

[00:09:24]So, 15 plus nine gives me 24.

[00:09:27]So, if we don't choose one, we have the option to choose from its adjacent elements. What is the adjacent element?

[00:09:33]Nine and two. And what is the max value they are bringing? Nine and 15.

[00:09:38]Obviously, if you go to node nine, you will not take three, right? Obviously, you will take the most valuable item. If you go to two, you will not take the least valuable item, you will take the most valuable item. That is how it is happening. I'm coming from one, but I am not choosing one. So, I can choose the maximum values from room number nine and room number two.

[00:09:58]Got it? So, room number nine gives me max value nine. Room number two gives me max value 15. That is eight and seven.

[00:10:06]I'll again quickly explain. Seven, if you are choosing seven, we get seven. If we are not choosing seven, we get zero.

[00:10:12]Eight, we if we are choosing eight, we get eight. If we are not choosing eight, we get zero.

[00:10:18]Two, if we are choosing two, we get two because we cannot choose the adjacent elements eight and seven.

[00:10:24]If you are not choosing two, we can get eight and seven. So, eight plus seven gives me 15. Red is for don't rob. Two is for rob.

[00:10:32]I mean, green is for rob.

[00:10:35]Similarly, for three, if we choose three, we get three as the amount. If we don't rob three, then we get zero. In nine, if we rob nine, we get nine. If we don't rob nine, we get three.

[00:10:47]Because we cannot choose the adjacent element.

[00:10:50]In one, that is the topmost node, if we choose one, if we rob one, we get one plus the values where we don't have nine and two.

[00:11:02]Where we don't rob nine and two. What are the values where we don't rob nine and two? That is the adjacent elements three and 15 written in red. So, one plus three plus 15 gives me 19.

[00:11:14]What if we don't rob one? Then we can choose from the maximum values of nine and two. Maximum value of nine is nine.

[00:11:21]Maximum value of two is 15. So, it is 15 plus nine 24. Got it?

[00:11:26]Now, let's come to the general formula which we will be in using in our code.

[00:11:39]So, we have three nodes.

[00:11:41]The topmost node is A. Then we have two children B and C.

[00:11:45]We have two options for both of the nodes. One is either we can rob B or we can skip B.

[00:11:53]Rob C or skip B. Similarly, rob A or skip A, right? For every node, we have two options.

[00:11:59]Now, this single nodes we already know.

[00:12:02]Either we rob B or skip B. Rob C or skip C. What happens when we come to that parent? Parent also has rob A or skip A, but that depends on B and C. When can we rob A? Only when we skip B and C, right?

[00:12:18]Only when we skip B and C, we can rob A because these are adjacent.

[00:12:24]>> [cough and clears throat] >> And when can we skip A?

[00:12:27]We can skip A when we can if we skip A, not when we can skip A. If we skip A, then we can take the maximum value from B, that is either rob B or skip B.

[00:12:39]Whatever will be the max, we will take it. Or plus we can take the maximum value from rob C or skip C. That means what? When we are skipping A, we will take the maximum value from both its children. Maximum value of B, maximum value of C.

[00:12:56]>> [clears throat] >> I hope that is clear.

[00:13:00]Now, let's see the code.

[00:13:03]Let's not look into this first. Let's come to this travel method.

[00:13:07]Private int travel. It is int. It is returning something. We'll see what it's returning.

[00:13:12]TreeNode, I passed the root over here inside this travel method.

[00:13:17]If my root is equal to equal to null, that means there is no tree, right? If there is no tree, there is no house, there is no colony. We cannot rob anything. So, we'll just return one empty array. Return new int So, we are returning one empty array.

[00:13:32]If there is a tree, first that was a general check. If there is a tree, we'll do normal traversal.

[00:13:39]Int, we'll take a left choice array.

[00:13:43]>> [clears throat] >> And we take a right choice array.

[00:13:46]Travel root.left. Recursively, we are traveling in the whole left side of the tree. And travel root.right, we are traveling in the whole right side of the tree.

[00:13:57]Int choices equals to new int two. So, we have taken another array choices.

[00:14:02]What is choices? This. C rob, C skip. B rob, B skip. This is my choices.

[00:14:07]After left choice, right choice, that is traveling in both left and right is done. Inside this choices array, what we will do? If we rob it, the first one is for rob. B rob, B skip.

[00:14:19]If we rob it, choices equals to choices zero, that is the first index, we will add my root value. Root.value plus plus left choice one, right choice one.

[00:14:33]Why?

[00:14:34]If we take the root value, we cannot take its adjacent element. Adjacent means what? Its children.

[00:14:42]So, if we take the root, current root, we cannot take its left child and right child. Left child and right child is present in left choice zero and right choice zero. If we cannot take that, we have to take the case where we have skipped the left and right side. That is left choice one plus right choice one.

[00:15:02]Is that clear?

[00:15:03]This is the same thing we did over here.

[00:15:06]If we take if we are robbing A, we will take skip B and skip C. When we don't rob B and C. That's the exact same thing we are doing over here.

[00:15:18]So, choice of zero is robbing A.

[00:15:21]If we are robbing it, we take the root value plus my left choice one plus right choice one.

[00:15:28]That means we are not looting its two children plus taking its own value, root value.

[00:15:36]Now, choices of one. What happens in choices of one? That is when we are not looting it. When we are skipping the current node, then we will take the max value of left and plus max value of right.

[00:15:50]Math.max of left choice zero {comma} left choice one. That means B rob {comma} B skip. Max value between them plus Math.max of C rob {comma} C skip. Right choice {comma} right choice one. Okay?

[00:16:07]After we are done with everything, that means whole traversal is done.

[00:16:11]Obviously, in between these recursive things, every traversal will be done. Whole tree will be covered. Then we are going to return the final. Which one we are going to return? This one.

[00:16:23]A rob.

[00:16:24]We are going to return this final list of choices. Return choices. That is going to go where? So, where did we call our travel method? Public int rob TreeNode. There was one method. Inside this, we have created one array int options, which is going to take the array we are returning from travel.

[00:16:44]Travel root. Here we had passed it. Here we had called this method we just saw.

[00:16:49]This return choices is going inside this particular array we have taken and then return the max between the two options. So, what did we see over here?

[00:16:59]Obviously, we are not going to take the minimum value. Just because it is in red doesn't mean you're not going to take it. It is in red, but it is also the max value, right? So, that means it is better.

[00:17:11]I'll say.

[00:17:12]So, that means it is better. 24. Okay?

[00:17:18]Okay.

[00:17:21]So, we took the max between them. Max between 19 and 24 is 24. Similarly, return Math.max of options zero {comma} options one. This This choices we are returning to this options in this rob method is the last choice. That means it is this choice we are returning, 19 24.

[00:17:39]This last array is what we are returning. And that array we are continuously replacing, right? Here are multiple arrays. These arrays were continuously replacing and at last we have got 19 24.

[00:17:49]Okay?

[00:17:52]Yeah? So, that is how you have got your final answer. That is 24. Okay. Now, time complexity and space complexity would be you're only traveling once, so it will be O of N. Space complexity, you're taking one array, so it will be O of N.

[00:18:05]Okay?

[00:18:06]Uh I've also given the C++ and Python code. Let's uh look into the C++ code first.

[00:18:12]Uh it will be the same thing only. Class solution public. There is a method rob.

[00:18:17]It is taking one TreeNode and the root value of it. And then we are calling this travel method. We'll come to this travel method. As we saw, we are returning a pair of int array. That is the array in case of Java.

[00:18:30]And we are passing the TreeNode. If the root is empty, that is not root. If it is empty, then we'll return one empty array.

[00:18:39]Return zero {comma} zero.

[00:18:41]Else, if there are there is value inside that uh tree, then we are going to travel in the left side first. Travel root.left.

[00:18:50]And right side, root.right. We have already traveled through my tree now.

[00:18:55]Now, what will happen? If we want to rob it, in rob, then we'll do root plus left.second, right.second. That means the second value.

[00:19:04]If you want to skip it, then we'll take the max between left max between the left and max between the right and add them. So, max of left.first {comma} left.second plus max of right.first {comma} right.second. And then we'll return this uh rob {comma} skip. So, that array we are going to return, the rob {comma} skip. That array is going to go over here. Auto result equals to travel.root. From travel.root, we are going to get it inside result. And then we are going to print whichever value is maximum from them. Return max of result.

[00:19:38]dot first {comma} result.second. That means that you the maximum value. Let's quickly see the Python one as well.

[00:19:45]Class solution.

[00:19:46]Um We are robbing. There There is a function called def rob.

[00:19:52]We are passing the root and we are traveling inside the root. If it's null, then we are going to return a empty at a 0,0. We are traveling in the left and traveling in the right by calling it recursively. If we are robbing, then it will be node plus left of one, right of one as we saw when we are skipping left and right. And if you want to skip that current node, then we'll take max of left plus max of right. And then we are going to return drop comma skip as an array.

[00:20:21]And take the maximum from drop comma skip.

[00:20:25]What does this mean? Return max travel root. That means whatever it is returning from travel root, drop comma skip, will print the maximum from drop comma skip. Okay?

[00:20:35]Fine. Now, let's come to this rotting orange in this question.

[00:20:43]Hm, okay. Now, you're given a matrix, m comma n grid, where each cell can have one of three values.

[00:20:52]There is a matrix. Let's see what the matrix is. See the grid. 2,1,1, 1,1,0, 0,1,1. Now, what does these things represent?

[00:21:02]There are three values inside my array.

[00:21:04]Zero represents an empty cell.

[00:21:07]Okay. So, wherever zero is present, that means that area is empty.

[00:21:11]One represents a fresh orange. Wherever one is present, that orange is fresh, good to eat.

[00:21:18]Two representing a rotten orange.

[00:21:21]So, that means wherever two is present, we will have one rotten orange.

[00:21:25]Every minute, a fresh orange that is four directionally adjacent to Every minute, any fresh orange that is okay, four directionally adjacent to a rotten orange becomes rotten. We'll see what it means. Return the minimum number of minutes that must elapse until no cell has a fresh orange. So, all the oranges in my matrix must be rotten. Only then I can return how long it takes for my whole matrix to get rotten. But if it is impossible to get all of my matrix to be rotten, then we'll return minus one.

[00:22:00]Can there be chances where it can be impossible? Obviously, if one orange is kept at a distance very at a higher distance than other oranges, it'll impossible to rot. That means if it is not four directionally adjacent. What does four directionally adjacent mean? See.

[00:22:18]There is one example.

[00:22:20]>> [clears throat] >> These are the oranges.

[00:22:22]Uh 2,1,1. You know how to write a grid, right? Two means over here, this is rotten. That's why there is a cross.

[00:22:30]1,1. We have filled it. This is row one.

[00:22:32]Second row is 1 1 0. We have filled the one one with oranges and zero is empty.

[00:22:38]Second is 0 1 1. This one is empty and 1 1 we have filled with orange. Okay?

[00:22:43]Now, this one is rotten.

[00:22:45]How can it four directionally populate its rottenness?

[00:22:51]At the right side, it can go and rot this orange. Downwards, it can go and rot this orange. But on the left side and upper side, it cannot go because there are no oranges, right? If there were oranges over these two areas, then it could have rotten these two as well.

[00:23:06]So, what does it mean? It can go up, right, down, left. Okay?

[00:23:12]The first minute, only one orange is rotten.

[00:23:16]The moment the next minute elapses, because every minute one orange is rotting the other oranges four directionally, right?

[00:23:25]So, in the next minute, these two oranges get rotten on the right side and on the downward side. Left and up, we don't need to see in this case.

[00:23:36]Minute two. Already three oranges are rotten. In minute two, what happens? The other two oranges, which we had gotten rotten in the previous session, previous minute, they will rot their four in four adjacent directions they're going to rot.

[00:23:53]This orange, that is the second orange, will rot this one and downward direction. So, this is rotten and this is rotten. And this orange already sees that this orange has already got rotten. So, it doesn't need to rot it anymore. Okay?

[00:24:08]So, now five oranges have been rotten.

[00:24:11]Minute three, what happens?

[00:24:14]This orange we got new, right? Also, this orange is new. So, this rightmost, topmost, rightmost orange can also rot other oranges, but there are no more oranges left to rot. Because this cell is empty and these this left orange has already been rotten.

[00:24:31]What happens when this middle orange is rotten? In the previous minute, this middle orange got rotten.

[00:24:38]So, we are going to rot the downward orange, which is present in the downward direction. In the left direction of this middle orange, it is already rotten.

[00:24:47]Right direction, there is nothing. Cell is empty, so we cannot rot. And upward direction also, it is rotten. So, in minute three, another orange is rotten.

[00:24:55]What will happen in minute four? This orange previously got rot rotten. So, this is going to rot this orange, the corner most lowest orange. Okay?

[00:25:05]This orange is getting rotten by this one.

[00:25:08]All the oranges have been rotten over here in this cell. That means all the values have become two.

[00:25:14]You understood, right? That means all the orange It's not going to become two.

[00:25:18]We are going to use some other approach.

[00:25:20]Because we need to calculate how many minutes it it took as well. So, we cannot turn all the oranges into two.

[00:25:27]Just in case you were thinking, okay, all the crosses there is the We can just Wherever we see one, we'll do two. Turn them into two.

[00:25:36]We have to find the number of minutes elapse as well.

[00:25:40]Fine. All the oranges are rotten and the minutes elapse, that is 1 2 3 4, is four.

[00:25:46]How are we going to find it? Okay. Also, there is another case where oranges might not be rotten. See, 2 1 1, 0 1 1, 1 0 1. There is one left corner orange that is never rotten. If you draw in the copy, I'll show you how we are doing it. If you draw in the copy, you'll understand that one orange is never rotten. That is why there is minus one as in one example. Okay?

[00:26:11]So, m is grid length, n is So, rows, columns, and between one to 10 the rows and columns. Okay? And the values are 0 1 and 2.

[00:26:20]Now.

[00:26:22]How is my rotting taking place?

[00:26:27]2 1 1, 1 1 0, 0 1 1. Now, let's draw the oranges first. Only one rotten orange is there as we can see, two. So, we have indicated this rotten orange in red.

[00:26:38]Okay? And the other oranges, 1 1, that means here two oranges will be there and 1 1, two oranges over here. Zero is empty. Again, zero is empty and two oranges over here. Okay? Green are the good oranges.

[00:26:50]Why have I denoted everything with infinity?

[00:26:54]You can denote it with anything else as well. But for me, denoting it with integer.max value is easier. Because later on, I want to check if any of the cells has still been infinity. How did I say that this lowermost left corner orange can never be reached? That's why we are returning minus one.

[00:27:15]That means it can never be rotten. When can it never be rotten? When it can never be reached, right? If I'm out of reach from a rotten orange, I will not be rotten, right?

[00:27:25]So, I cannot reach it.

[00:27:27]How do I identify I'm not being able to reach it?

[00:27:30]By seeing whether any one of the cells is having integer.max value as its uh value, right? Which I had populated previously.

[00:27:41]So, this will be my time grid. Why time grid? As I said, we need to calculate how much time has elapsed.

[00:27:48]That's why I said that we cannot put 0 1 and 2. We have to have higher values as well. Till two, we cannot restrict ourselves. So, we are converting this orange matrix into a time matrix. We have populated everywhere into a time integer.max value, that is infinity. All the oranges, not just the fresh oranges, but the rotten oranges too.

[00:28:12]Now, we are going to start our iteration.

[00:28:14]In the zeroth iteration, what will happen? That is when we are not not yet started.

[00:28:19]We have to mark our rotten orange. So, I have this leftmost, topmost corner as rotten. So, I marked it as zero.

[00:28:27]Now, since I placed this rotten orange over here, it will rot its four directional adjacent places as well.

[00:28:35]So, I am going to rot this place and then this place.

[00:28:38]When?

[00:28:39]In the next minute. When is the next minute? This rotten orange was already present. That's why it's the zeroth minute. That's why I'm not written one.

[00:28:47]These are not iterations, but these are minutes elapsed.

[00:28:51]In the zeroth minute, this was rotten.

[00:28:54]Then in the next minute, that is 0 + 1, oneth minute. Why I'm saying 0 + 1? You will get to know. Current + 1. Current is zero.

[00:29:03]Current + 1. 0 + 1 is my one and one.

[00:29:07]So, these two oranges are also rotten over here. Let's come to the next iteration. These two oranges were rotten. Okay?

[00:29:15]Again, another minute has elapsed. It was the first minute. Now, again, another one minute will be elapsed. The current time was one.

[00:29:23]In the next minute, current + 1 becomes two. Again, two more oranges have been rotten. When we go in this direction, two gets rotten. And downward direction also, two gets rotten. Similarly, for this also, two gets rotten.

[00:29:37]So, current + 1. 1 + 1 becomes two.

[00:29:41]Two more oranges are left. We come to the next iteration.

[00:29:45]This second orange is going to rot my this orange. Current time was two. Two plus one becomes three. So, right now in the third minute, my this orange has been rotten.

[00:29:59]We come to the last iteration where only one integer.max value is remaining. This This cell is only remaining over there.

[00:30:08]Again, when we traverse in the right direction from this rotten array from third minute's array cell, we get this orange and rot it.

[00:30:17]So, this is my fourth minute. Current plus one time, that is three plus one, four. Okay?

[00:30:24]Uh sorry, I've written days. It will be minutes. So, what is the max number of minutes it takes for oranges to get rotten? Four. How did I get? I just search the max value from my whole index. That is very easy, right? It's just um searching in my matrix which is the max value.

[00:30:40]So, four will be my max value in case of Okay.

[00:30:45]Now, let's see the code.

[00:30:48]>> [clears throat] >> There is one method, public int rotting oranges, and we pass our grid.

[00:30:58]Grid means what? This one we pass, 21111001.

[00:31:02]Okay?

[00:31:02]This matrix we are passing inside my method which is returning one integer value. What is that integer value?

[00:31:10]The minutes which have elapsed till all of my oranges have rotten.

[00:31:15]If my grid is none or my grid.length equal to equal to zero, both are same.

[00:31:20]That means we are returning minus one.

[00:31:23]There are no oranges. So, we don't know how long it will take to rot the oranges. It is impossible to calculate because there are no oranges.

[00:31:31]So, we'll return minus one. That's what was asked in the question.

[00:31:35]We calculate the rows of the grid. Rows equals to grid.length. Columns equals to grid zero.length. Okay?

[00:31:42]We take a time matrix as I said over here. This is the time matrix, not this.

[00:31:48]This is the grid.

[00:31:49]Oranges, this is the grid. And this is the time matrix. When we start filling it with infinity. So, it's a different matrix.

[00:31:57]Int time equals to new int rows and columns. It will be of the same size as that of grid because obviously like how to compare the last orange if you don't take the same size.

[00:32:11]Now, we're traversing all of the whole array. For I equals to zero, I less than rows, I plus plus. And Arrays.fill each row time of I with Integer.MAX_VALUE.

[00:32:22]You can also do it by like in two inner loops as well, but this is a easier way because we already have two parameters inside Array.fill.

[00:32:32]So, why not?

[00:32:33]Okay, so we're traversing towards row by row and filling all the rows with Integer.MAX_VALUE. That means infinity.

[00:32:40]Integer.MAX_VALUE can be considered as infinity. Okay?

[00:32:44]Now, all of my array has been in in this format. This format. Okay? This is the format of my array.

[00:32:51]What will happen after that?

[00:32:53]For I equals to zero, I less than rows, I plus plus. Each row. For J equals to zero, J less than columns, J plus plus.

[00:33:01]So, we take the first row and inside that first row we are traversing all of the columns. Simple as we do in case of 2D array.

[00:33:09]If my grid of I, J is equal to equal to two, that means if it is a rotten orange.

[00:33:16]If we get a rotten orange, we will go to our DFS method. DFS and we are passing what? The grid. Grid means my orange array. Then my time, that is my array having all the infinities currently.

[00:33:32]I value, that is row value. J value, that is column value. And zero. What is this zero?

[00:33:39]Current time, right?

[00:33:41]The first current time would be zero.

[00:33:43]After that it will be zero plus one.

[00:33:45]Then it will be one plus one, right? So, that is why current time we have to pass.

[00:33:50]DFS grid, time, one, J, zero. I, J, zero. Let's come to the DFS method.

[00:33:58]Private void DFS int grid, int time, int I, int J, int current time.

[00:34:05]Now, obviously the edge cases we have to tackle, right? So, if I is less than zero or if I is greater than equals to my grid.length. If J is less than zero or if J is greater than equals to my grid.length. Obviously, these are index values. Can't be less than zero. Can't be equal to the length. Okay?

[00:34:22]If grid equal to equal to zero, that means empty. Uh no, if grid equal to equal to zero, that is the value in place of that element. That is empty cell. Not empty array. Empty cell. If my cell is empty or if my current time is greater than my time present in my array. Is that possible?

[00:34:43]Can your current time be greater than what time it is present in your array?

[00:34:48]Is it possible that your upcoming time is greater than Sorry, if your current time is greater than what is in your See, what is present in your array?

[00:34:59]Whatever time has elapsed that is present in your array.

[00:35:03]So, there is no way your current time can be greater than your array time, right? That is why current time greater than equals to time is also there. these things are there, we will directly return from that.

[00:35:16]Uh okay. Now, why am I saying this? See.

[00:35:19]Uh where did it go? Ha.

[00:35:22]One one. See, this one is populating this two, rotting this two, and also rotting this two. So, we don't have to consider this one and rot this one as well. That is why we have taken this condition, current time greater than time I, J.

[00:35:38]And return from there. Okay?

[00:35:41]>> [clears throat] >> Now, let's come to the actual See.

[00:35:44]Time I, I, J is your current time. What does it mean? The first time when we had filled the zero, right? That is my current time.

[00:35:55]After this, we will fill this one and one using this zero. How?

[00:36:00]First, we have filled our current time.

[00:36:02]Time I, J equals to current time. Now, we are traversing in all of the four directions. What are the four directions? I minus one, J. I plus one, J. I, J plus one. I, J minus one.

[00:36:17]DFS grid, time, I minus one, J, and current time plus one. So, that zero plus one, that is coming from here.

[00:36:26]Current time plus one. All right.

[00:36:28]One plus one, two. That is coming from here.

[00:36:31]I minus one means what? Go above one row. That means top.

[00:36:36]I plus one means what? Go down. That means below.

[00:36:40]I, J plus one. Row remains constant.

[00:36:43]Row remains constant. Column plus one.

[00:36:46]That means go to the right side.

[00:36:48]Row remains constant. Column minus one.

[00:36:50]Go to the left side.

[00:36:52]So, these are the four DFS cases we have to uh traverse.

[00:36:57]We are using depth-first search over here. If I had taken a bigger matrix, you would have understood how depth-first search. But from here also you can understand, right? Zero and one.

[00:37:06]Then again, we come to the downward direction from one to two. Then from two to three. Then from three to four. This is DFS, sorry.

[00:37:14]Whatever value will be coming from this DFS, okay? All of the array will get populated from here. Just like we did over here. From zero it became one one. Then from one it became two two. From two it became three. From three it became four. Okay?

[00:37:30]This value will go over here. What did we call it? If my grid is equal to equal to two. That means for each Now, now let's say there are two rotten oranges.

[00:37:40]What will happen?

[00:37:42]The directions of rotting will happen from two places, not just one place. So, if my first orange rots my entire grid, my second orange will also rot my entire grid.

[00:37:57]What am I trying to say?

[00:38:01]If there is only one orange, it will take a lot of time for If there is only one rotten orange, it will take a lot of time for it to rot my entire grid, right?

[00:38:11]But if there are two rotten oranges, the time will be comparatively relatively less.

[00:38:16]If one orange was rotting it in four minutes, two oranges might be rotting it in two minutes.

[00:38:22]Why?

[00:38:24]First orange will rot it and let's say the max value is four. If there is another orange which is rotten, then like rotten from previous only, then it will again start a DFS from the lower most corner and it will go up up up, but it will not increment like we were doing current time, right? It will not increment it that way. Current time for the next rotten orange would be zero only because it is rotten.

[00:38:51]If it's rotten, the current time would be zero only. What am I trying to say?

[00:38:55]Grid I, J equal to equal to two, DFS grid, time, I, J, zero.

[00:39:00]We are passing zero as the current time for each rotten orange.

[00:39:05]So, let's say this was one rotten orange and here, let's say in the corner most position, there was another rotten orange. As we saw, this Let's say this had already become three. But if in this four area, there was a rotten orange, this three it would have replaced with one.

[00:39:24]So, that means what am I trying to say?

[00:39:27]The highest value which was present over here would not be highest anymore because it will keep decreasing because this orange is also rotting the other oranges. Ultimately, might be the maximum value will only be two or the maximum value will only be one. But you have to calculate and see. I'm not doing again.

[00:39:44]You're understanding my point, right?

[00:39:46]It's very simple. It's there only in these two lines itself. Each time we encounter a rotten orange, we are passing the current time as zero. So, no matter what the grid value is, if there is a rotten orange from previous transaction, that is from previous value itself, not from what we are populating, but from previously itself, then we are going to pass zero for it every time.

[00:40:12]Okay?

[00:40:14]After all of this is done, that means my whole array has been rotten, or if it's not rotten, we'll see what to do. If it is That means my whole array has been traversed. That's what I'm trying to say, whole matrix.

[00:40:26]We will declare a variable called time required.

[00:40:31]A variable called time required, which is going to calculate the maximum minutes passed before all of the oranges are rotten.

[00:40:38]We will traverse through my array. I equals to zero, I less than rows, I plus plus. J equals to zero, J less than rows, J plus plus. Simple way of traversing a 2D matrix. If my [snorts] grid I J equal to equal to one, what does it mean?

[00:40:55]That means one array has not been traversed itself. One orange has not been traversed itself, right?

[00:41:01]If grid of I J equal to equal to one, sorry, it's a fresh orange. So, this is grid. That means it is the oranges array, not that time array.

[00:41:11]Oranges array. If it's one, that is if it's a fresh orange. For every fresh orange, we are going to see if my time value for that corresponding array is equal to infinity or not. That is integer.max_value or not. Why?

[00:41:25]If it is integer.max_value, as I said previously, that means we could not reach it. It is still fresh. If it is still fresh, that means my whole matrix has not been rotten yet.

[00:41:36]If my whole matrix has not been rotten yet, then it is impossible to rot the whole matrix, so we return minus one.

[00:41:44]So, for each fresh orange, we are checking if the time is infinity. If it is infinity, we return minus one. If not, then we calculate the required time for it. Time required equals to math.max of time required {comma} time of I J.

[00:42:00]That means the maximum value from my time matrix and my required time, whichever would be the max value. Here only in this one for loop, this for loop only we are calculating that time, and later on we are returning that time itself.

[00:42:15]I hope that is clear. Now, let's see the time complexity. Obviously, we are taking inner loops, so M into N, row into column, O of row into column would be our time complexity. And also, we are taking a fresh array, int of time, which is also of length rows into column. So, that is why space complexity is also O of M into N. Got it?

[00:42:39]Uh >> [clears throat] >> Now, let's see the C++ and Python solution.

[00:42:44]This is C++.

[00:42:46]Uh class solution, public There is one method called oranges, where we are passing the grid. And if the grid is empty, grid means the oranges grid only.

[00:42:56]If that orange grid is empty, we return minus one.

[00:43:00]If my oranges grid, uh sorry, we return minus one, and then we calculate the row length and column length. Grid.size, columns equals to grid zero.size. We get the row and column length.

[00:43:14]And we declare one array, that is vector of vector int, 2D array, of course.

[00:43:21]And that name is time.

[00:43:23]Rows {comma} vector of int columns int max. So, we are already populating the array with infinity over here. We have already The moment we declared the array, we have also passed infinity in all of the cells inside that array.

[00:43:37]Now, for int I equals to zero, I less than row, I plus plus. Int J equals to zero, J less than row, J plus plus.

[00:43:45]If grid I J equal to equal to two, that means if we are getting one rotten rotten orange, then we are going to DFS.

[00:43:55]DFS grid time I J zero is my current time. Come to DFS over here. In the right side, we have DFS. Private void DFS vector int, uh we are passing the grid, time, I J, and current time.

[00:44:09]Here again, we have calculated the rows and columns of the grid. If my I is less than zero or greater than equal to row, wrong. If J is less than zero, J greater than equal to column, wrong. If grid is equal to equal to zero, that means we have right It is an empty cell right now, then it is wrong. We don't need it.

[00:44:28]And if my current time, that is already covered, equal to greater than equal to time, that means if it's already covered, then we return from there. We don't have anything to calculate. We return from that function.

[00:44:40]If not, then we have the time I J equal to current time.

[00:44:45]Okay? So, we put that current time in my matrix, as I explained previously. I'm not going to the diagram again.

[00:44:52]And then calculate the DFS for that particular value. That means top, right, left, and down, we rot the oranges. We pass the grid time. I minus one is left, I plus one is right, uh sorry, I minus one is top, I plus one is down, J plus one is right, J minus one is left.

[00:45:13]And increment the current time and put inside that cell. Okay?

[00:45:18]So, this is done. From here, we'll come back to our previous function. And here, if grid I J for each two value, we have got the DFS value.

[00:45:30]And we declare this time required variable, and we traverse in our array.

[00:45:33]I less than row, J less than column. If we have a fresh orange grid I {comma} J equal to equal to one, then we see if the time is infinity or not. For each fresh orange, if my time is infinity, we will return minus one.

[00:45:48]The moment we get a fresh orange and the time is infinity, we return from there and return minus one. If not, then we calculate the final time required, which will be the max value between time required and the time in my cell in the matrix. Okay?

[00:46:04]The max value from that will be calculated after the entire uh loop has been completed, and then we return the time as our answer.

[00:46:13]Got it?

[00:46:14]Now, let's go to the next last question.

[00:46:18]Oh, sorry, we have Python as well, right?

[00:46:20]Class solution, uh define oranges rotting, and we pass our grid. If the grid is empty, we return minus one. We calculate the rows and columns using the length grid and length grid zero. And we declare one time array, float infinity, we pass over there.

[00:46:39]Uh for in rows and columns, for each row, we pass the infinity value inside our uh time matrix.

[00:46:48]Uh Now, we have a DFS method as well.

[00:46:57]I {comma} J current time. When we are calling the DFS method, let's see that first. Come down. Come below. For I in range rows, for J in range columns, that means we are traversing through the array. If my grid is equal to equal to two, that means we have found a rotten orange.

[00:47:13]Go to DFS method I J zero. I'm going to my DFS method. Def DFS over here. I hope you can see the mouse. Def DFS I J current time. If I less than zero or I greater than row, J less than zero or J greater than equal to column, these two are wrong. If grid of I {comma} J is zero, that means it is an empty cell, or if current time is greater than my time present in the index, then return from there. If not, then put the current time in that particular index, and calculate the DFS for I minus one, top, I plus one, down, J plus one, right, J minus one, left, and put the current time plus one in that particular index.

[00:47:55]After everything is done, we'll come to this portion portion, and define a variable time required with zero. And traverse through the array. For I in range rows, J in range column. And if my In my grid, if I still have one, that is one fresh orange. I'm explaining a bit fast, because we need to cover another question.

[00:48:14]If grid I J is equal to equal to one, then in time I {comma} J, if we have infinity as well for that particular index, that means we could not reach that orange. That orange is still fresh, so we failed, so we'll return minus one. Else, we will calculate the maximum time. Time required equals to max of time required {comma} time I {comma} J. For this whole iteration, it will find the maximum.

[00:48:40]That means the maximum element in the whole matrix, okay? And return the time required. Got it? Did I say the time complexity? Yeah, M into N, O into N.

[00:48:50]Uh M into N for both time and space.

[00:48:53]Okay, let's come to our last question.

[00:48:58]Coin change. Okay?

[00:49:00]You are given an integer array of coins.

[00:49:04]So, you're given an array over here.

[00:49:06]Representing coins of different Okay, uh one second. Some people might say you just said that only we get DP trees and graphs. Then why are we doing array questions?

[00:49:17]DP is array only, by the way.

[00:49:20]It's just an advanced version of array.

[00:49:22]I'm saying that you don't get straightforward questions from array, strings. I mean, that's what we saw in the previous year pattern, okay? So, I hope this year also like same only, tough questions only they are going to ask.

[00:49:35]Because the package is also high, okay?

[00:49:38]So, you're given an integer array coins representing coins of different denominations. Okay? Multiple coins are there over here. One rupee coin, five, six, nine, 10, just like you have in real life. And an integer amount representing total amount of money.

[00:49:54]So, what are the two inputs we have over here? One array having all the coin numbers and one integer amount representing total amount of money.

[00:50:06]That means total amount of money we have to make up with.

[00:50:09]So, let's say that is 10 and we have five rupee coins and 10 rupee coins. How can you make 10?

[00:50:18]Two ways. I can take two five rupee coins and make 10. Or I can take one 10 rupee coin and make 10.

[00:50:25]If you had one rupee coins, you will take 10 one rupee coins.

[00:50:29]Or you can combine five rupee and one rupee. Right?

[00:50:33]So, like that multiple ways might be there to make up amount. Return the fewest number of coins that you need to make up that amount. Fewest number of coins, how many? 5 + 5 is two and 10 is one.

[00:50:47]So, I'll choose 10 rupee coin only. Only one coin I need.

[00:50:51]If that amount of money cannot be made up by any combination of coin, that is if that amount of money is not achievable by the um coin denominations given then we're going to return minus one.

[00:51:04]You may assume that you have an infinite number of each kind of coin. Okay, so there is no restriction for each kind of coin. We have an infinite number of ones, fives, whatever amount will be given. Let's see the input value, okay?

[00:51:18]So, the coins are one, two, and five in infinite amounts. You're understanding, right? Infinite amount of ones, infinite amount of twos, infinite amount of fives. We have to make 11.

[00:51:30]How can we make 11? Output is three.

[00:51:33]How? 5 + 5 + 1. That is how we get 11.

[00:51:38]Example two, only two rupee coins are there. Amount is three. How can you make three using two rupee coins? It's not possible, right? So, we return minus one.

[00:51:47]Coins is one, amount is zero. We don't need any coins to make zero amount. That is why we have written zero, not minus one.

[00:51:55]Now, some people when they see this example, right? Amount 11, 1, 2, 5. We have taken five, five, that means 10. 11 minus 10 is one, so we take one. That is how people think. We will take the highest number and then whatever will be remaining from that highest number, we'll keep on adding the highest coins and then the last amount we'll take and then we'll get the minimum number of coins. Is that what you think?

[00:52:21]Then let me prove you wrong because greedy won't work in this case. Why it won't work? Let's say you have four coins. One rupee coin, five rupee coin, six rupee coin, and nine rupee coin.

[00:52:38]And you have to make an amount of 11.

[00:52:42]How to make that 11? Well, you'll say let's take the highest amount, nine.

[00:52:47]After that nine, we are left with two.

[00:52:49]11 minus nine, two. So, since two is not present, let's take two one rupee coins.

[00:52:55]So, in three coins we have made 11. Wow.

[00:52:58]But you also have five and six, right?

[00:53:01]If you took five and six using two coins, you could have made it.

[00:53:05]But when you took nine, you also had to take two one rupee coins.

[00:53:09]And you made using three coins. But if you took five and six, you could have made it using two coins.

[00:53:15]This taking highest value is called the greedy approach. You're being greedy.

[00:53:20]You're taking the highest number. But that is not going to solve this question.

[00:53:24]This will be solved using again memorization.

[00:53:28]The ones which we are doing, DP.

[00:53:32]Let's see this example only. Let's see how many coins to make 11. 1, 5, 6, 9.

[00:53:38]These many coins we have. 1, 5, 6, 9.

[00:53:41]Keep it in mind because we have multiple slides to cover over here.

[00:53:47]We are taking one table. Make a table.

[00:53:51]This is not a table, by the way. This is your DP. Okay? This is your DP. The indexes of the DP is your amount.

[00:54:02]And the value inside your DP is the minimum number of coins required to make that amount.

[00:54:12]Got it?

[00:54:13]This is your DP.

[00:54:15]The index in your DP is the amount which you want to make, not the amount given in the question.

[00:54:23]If you are given 15, let's say. You will take a DP of size 16 from zero to 15.

[00:54:29]Till 15 you have to count each and every denomination, each and every amount. How many minimum number of coins I need to make that amount. Why I'm saying that?

[00:54:41]Because we will come back to these um amounts lesser than 11 as well. Using these lesser amounts only we are going to make 11. That's why we need each and every value over here, not just 1, 5, 6, and 9. We need 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, everything. Why? Let's see.

[00:55:03]For zero, how many coins you need?

[00:55:05]Nothing. Zero only you need, so that's why I put it up. Dash. For one, how many coins you need?

[00:55:11]Lowest number is one over here. So, using one you can make one. So, only one coin we need.

[00:55:17]Two, how many coins you need?

[00:55:20]You have to take the lowest possible present. How many coins are lesser than two over here? One only, right? 5, 6, and 9 are greater than two. So, you take one plus DP of 2 minus one. Look over here. DP of 2 minus one is what? One.

[00:55:34]So, that coin one has only one coin, okay? This is not the numeric value one, okay? This is the how many coins, like I mean, not how many coins, like coin one. This is coin. The circle represents coin, okay?

[00:55:49]All the circles over here represent coin. Okay? The value of this one is one. DP of one, which we have put over here. So, that means we are fetching values from the DP. You're seeing, right? So, we are going back and back again towards our previous values.

[00:56:05]Minimum coins I needed to make one was one. So, 1 + 1 is two. I have got my minimum value for minimum coins required to make two is two.

[00:56:16]Come to three. What is the minimum number of coins required to make three?

[00:56:20]You'll see why I have drawn this in written this in two different colors.

[00:56:25]Minimum coins to make three is what?

[00:56:27]Obviously, the lowest number is one over here. Five is greater than three, six is greater than three, nine is greater than three. So, we have to take one.

[00:56:35]We take coin number one plus DP of 3 minus one.

[00:56:41]Coin number one plus DP of two. DP of two value we already have over here.

[00:56:46]Take this two. Coin number one, only one coin plus two equals to three.

[00:56:52]So, three coins are required to make amount three.

[00:56:58]Come to four.

[00:56:59]What is the minimum number of coins required to make four? How to calculate?

[00:57:03]Again, four is lesser than all the values except one. So, we have to take one plus one plus DP of 4 minus one. Remaining value is three.

[00:57:14]I hope you're understanding why we are doing DP of 4 minus one, right? Because we have already taken one coin. So, the remaining value is three.

[00:57:22]So, remaining value three, how can I make minimum number of coins for three is already calculated in the DP. That is why we are doing DP of three.

[00:57:31]Which is three. Again, 1 + 3 is four.

[00:57:35]Okay? Put four over there. Now, let's see this five.

[00:57:40]I hope it is visible.

[00:57:43]This five, how many coins can we use? What were the coins present? 1, 5, 6, 9. So, we can use one and five to make five, right?

[00:57:53]Not one and five together, I mean. There can be two cases. I can choose one as well. I can choose five as well.

[00:58:01]Right? If I choose one, what is the remainder? DP of 5 minus one is four.

[00:58:07]1 + DP of four. Four is four. Minimum coins to make four is four. We have calculated over here. 1 + 4 is five. So, five coins we need to make.

[00:58:18]But if we use five coin, coin number five if we use, 5 + DP of 5 minus five is zero. 5 + 0 is zero. Nothing. We need don't need any coin to make zero. So, only one coin.

[00:58:34]See, five plus zero is one I've written.

[00:58:36]Don't think I've written something wrong. Five means coin number five, not amount of coins, okay?

[00:58:43]Only one coin of denomination five we need, okay?

[00:58:49]So, one coin only needed. So, minimum value from five and one is one. So, we have put this one over here in in place of five.

[00:59:00]Got it?

[00:59:01]Now, let's make six.

[00:59:04]Now, let's make six. How can we make six?

[00:59:08]Let's come to this page.

[00:59:11]When we are choosing six, what were our coins? 1, 5, 6, 9. How can we make six?

[00:59:17]One is less than six, five is less than six, six is less than equals to six. So, we can take these three values. Nine we cannot take.

[00:59:25]1 + DP of 6 minus one. 1 + DP of five.

[00:59:29]What was DP of five? One. So, we take 1 + 1 = 2. Using two coins, I can make 6.

[00:59:38]What is How can we make using five again?

[00:59:42]5 + DP of 6 - 5. That means five only one coin is there. DP of 6 - 5 is 1. For one answer, minimum coins is 1. So, that means 1 + 1 2.

[00:59:54]Another way, how can we make six?

[00:59:56]Six, coin number six we'll take and DP of 6 - 6 is zero. Six coin plus zero gives me only one coin. Only one coin needed. So, one is the minimum value between two, two, and one. So, we put one over here.

[01:00:10]In in in index number six.

[01:00:12]How can we make seven?

[01:00:15]One, five, and six we can take.

[01:00:17]For one, if we take one, we'll do DP of 7 - 1. 1 + DP of 7 - 1, that is six, is 1 + 1 = 2. Why one? Because six, the minimum number of coins required to make six was one.

[01:00:30]So, 1 + 1 = 2.

[01:00:33]If we take fifth coin, then 5 + DP of 7 - 5 will give me DP of 2.

[01:00:40]For five, how many coins per se? For five, five was only one coin, right?

[01:00:45]Five, we have only one coin is taken plus DP of 7 - 5 is 2. How many coins to make two? Minimum coins is two. So, 1 + 2 is 3.

[01:00:54]What if we take six?

[01:00:56]6 + DP of 7 - 6. 1 + DP of 1. For one, we had to take only one coin.

[01:01:02]Sixth coin, that is 1 + DP of 1 is 1, which gives me two.

[01:01:05]Which is the lowest among two, three, and two? It is two. So, put two in place of seven.

[01:01:11]Let's calculate eight. I'm explaining in a very simple way, so you should be able to understand. There should not be any sort of doubt.

[01:01:20]One, five, six.

[01:01:23]1 + DP of 8 - 1, that is 1 + DP of 7.

[01:01:28]What was DP of 7? Two. Minimum value was two. So, it will be 1 + 2 = 2 3.

[01:01:34]For five, it will be 5 + DP of 8 - 5. 1 + DP of 3. What was DP of 3? Three. So, we'll write 1 + 3 = 2 4.

[01:01:43]6 + DP of 8 - 6.

[01:01:46]1 + DP of 2. Two was two only. 1 + 2 = 2 3.

[01:01:50]Lowest among three, four, and five is three. So, we put three in place in eight index. Okay.

[01:01:57]Calculate nine.

[01:01:59]For nine, how many coins did we have? 1, 5, 6, and 9. So, all the coins we can take. So, four cases can be present in case of nine. If we take If we take one, 1 + DP of 9 - 1, that is 1 + DP of 8. Eight we had just calculated, which is three.

[01:02:16]1 + 3 = 2 4. If we take five, 5 + DP of 9 - 5. Five only one coin is there. DP of four, four is giving me minimum coins four only. So, 1 + 4 = 2 5.

[01:02:29]If we take six, then 6 + DP of 9 - 6, that is 1 + DP of 3. Three is three only, so 1 + 3 = 2 4.

[01:02:37]Nine, if we take 9 + DP of 9 - 9, that is DP of zero. Nine means only one coin.

[01:02:42]DP of zero means zero coin. So, one coin is the minimum value. We put in place of nine.

[01:02:48]Now, how to calculate 10?

[01:02:52]10 also we can take 1, 5, 6, and 9.

[01:02:54]Obviously, it has increased from nine, so now all the coins we can take.

[01:02:58]If we take one, 1 + DP of 10 - 1, that is 1 + DP of 9. Nine right now we calculated from the table, we get one. 1 + 1 = 2 2.

[01:03:07]If we take five, 5 + DP of 10 - 5. 1 + DP of 5. 1 + 1 = 2 2. See, DP of 5 is 1, that's why.

[01:03:16]Um 6 + DP of 10 - 6. If we take the sixth coin, 1 + DP of 4. 1 + 4 = 2 5. DP of 4 was giving me four. Okay.

[01:03:28]If we take the ninth coin, then 9 + DP of 10 - 9. Remaining is one. 1 + DP - DP of 1. 1 + 1 = 2 2.

[01:03:36]11th, again we can take all four coins.

[01:03:39]Four cases will be there.

[01:03:41]If we take one, first coin, then remaining If we take one rupee coin, remaining is 10. DP of 10 is DP of 10 is two. See, DP of 10 is two.

[01:03:53]So, we are taking one rupee coin and we are taking a 10 DP of 10. That means 1 + 2 = 2 3.

[01:03:59]Okay.

[01:04:01]If we take a five rupee coin, only one coin we are taking. DP of 11 minus five, that means six is remaining. What is the minimum number of coins to take six?

[01:04:11]If we make six, only one coin is required. So, previously five we took plus one equals to two.

[01:04:16]If we take six, one coin, DP of 11 minus six is five.

[01:04:21]For making five, we require only one coin. Previously, six also we have taken, so 1 + 1 is two.

[01:04:26]If we take nine, DP of 11 minus nine is two. So, one coin we have taken and minimum number of coins to make two is two. So, 1 + 2 is three. Which is the minimum among three, two, two, three?

[01:04:37]Minimum is two. So, that's why we have put two in place of 11. And what will be your answer?

[01:04:44]The DP of amount, that means the value present in the amount index, that means the input which you have got to calculate, that will be your answer.

[01:04:56]Two coins you need. Got it?

[01:05:00]I have explained in a very easy approach, so you will should be able to get it.

[01:05:05]Okay. Let's see the code. Public int coin change int coins {comma} int amount. So, they have passed the coins matrix, that is 1, 5, 6, 9, this matrix, and your amount, that is 11, which you have to make.

[01:05:19]If my amount is less than one, that means if it's zero or negative, we don't need any coins to make it, right? So, zero coins.

[01:05:28]Then we will take one DP. Int minimum coins equals to new int amount plus one. Why amount plus one? Because we are starting from zero, because we need zero as well. For example, when we are taking ninth coin for amount nine, 9 - 9 becomes zero. So, we need the zero index as well. That is why we are taking amount plus one.

[01:05:49]This is the memorization concept. Okay.

[01:05:52]For int i equals to one, i less than equals to amount, i plus plus.

[01:05:55]Obviously, we only need the from the first amount we need to calculate, that is why we are taking i equals to one.

[01:06:01]Till my amount index. Okay.

[01:06:04]And we are filling everything with infinity.

[01:06:08]That case I have not shown. Why I have not shown? You'll see later on what we are doing with infinity over here.

[01:06:14]Fill everything with infinity first.

[01:06:16]After that, traverse in your entire coins array.

[01:06:20]For each coin, for int coin of coins, for each coin in my coins array, this is a for each loop.

[01:06:27]If my coin is less than equals to i, that is if my coin value is less than equals to my current amount, not 11, but my current amount for which I am filling my DP right now. I have not filled my DP yet. I am filling. I am in the process of filling it.

[01:06:48]That means one, then two, then three, then four, the way we are filling right now, right? This uh Oh god.

[01:06:58]Mhm.

[01:06:59]This uh chart we made right now.

[01:07:06]This chart we made right now, right? 2, 3, 4, 5, 6, 7, 8, 9, like this we were filling one by one. That same thing we are doing over here.

[01:07:14]If my coin is less than equals to my amount and my value in that particular index of my DP min coins i minus coin is not equals to my integer.max_value, that means if i means what? The current amount minus my coin value.

[01:07:35]That means 9 minus five, 9 minus six, DP of 9 minus six, DP of 9 minus five, which we were doing right now, right?

[01:07:42]The remaining amount. If that remaining amount is not equals to max value, that means if my remaining amount has been calculated, it is not empty. It has been calculated.

[01:07:54]When can this case be valid? In case of zero, right? Even if we have one over here, 1 - 1 will be zero. Zero is already calculated. The value is zero itself, right?

[01:08:04]So, we can If it's not equals to max value, min coins equals to math.min of min coins {comma} 1 + min coins of i minus coin.

[01:08:15]What does this mean?

[01:08:17]Whichever will be the minimum between the min coins of i, if anything is present in my i-th index, that means when we were making five, we already have five as our coin, right? So, we can directly do min of five.

[01:08:32]Then we will getting the math.min and plus 1 + min of i minus coin, that is remainder. If we take five, plus whatever is remaining over there. That means zero.

[01:08:44]Whatever will be the minimum value among the two, we are going to store it inside this min coins array.

[01:08:51]So, int First, it will be infinity, right? Among infinity and among 1 + minimum coins in i minus coin. Pardon? Whichever will be the minimum value, the same thing which we are doing in DP. I cannot explain again. 1 + DP of 10 minus five. The same thing. Five coin plus DP of 10 minus five. That means 1 + DP of five. 1 + min coins of i minus coin. Same thing. This is remainder.

[01:09:17]And maximum value, that is integer or which is previously present in that min coins i. Whichever will be the minimum, we are going to put in this min coins array index.

[01:09:28]Using this for loop, your whole DP will be traversed. That means your whole this table using this one loop, I have done this whole table would be created.

[01:09:41]This is the concept of memoization.

[01:09:44]Whole table is created using your previous values itself. Nothing you have to do.

[01:09:49]After we are done creating our whole table for each amount. So, for one, we have created. For two, we have created.

[01:09:56]For three, we have created. Similarly, the whole table has been created.

[01:10:00]Then, we come out of this loop. And now, let's see what is the actual significance of this infinity. Firstly, we are doing this math.min, right? So, if you put infinity in one case, it becomes easier for you to calculate the minimum value.

[01:10:16]If any of the cells still has my max value, that means my amount cell.

[01:10:21]If my 11th cell my index value 11, that is what we were trying to calculate, right? If min coins of my amount, as I said, min coins of amount would be your answer, DP of amount. If it is equals to integer.max value, still if it's integer.max value, that means we were unable to calculate or we were unable to come to a solution using only that those few coins, 1 5 6 7.

[01:10:47]If we were unable to come to that solution, it will still remain as infinity and will return minus one because that's what the question had asked.

[01:10:55]If not, we'll return min coins of amount, okay?

[01:11:01]Let's go to the next Okay, this is done. So, Java Java code is done. I hope you understood. We are going to return the min coins of my amount. Again, let's see the C++ code.

[01:11:12]int coin change, vector of coins we are passing and the amount we are passing. If my amount is less than one, that is zero, we return zero. Then, we take a DP amount plus one is my number of size of the array and put infinity inside that DP and traverse from one to that amount. And for each coin in my coin array, that coin is less than equal to that current amount. And if my DP of current amount minus coin value is not equals to infinity, then DP of that particular index will have the minimum value between DP of that index and one plus DP of I minus coin. That means we have already taken one coin, right?

[01:11:55]And remaining DP of amount minus that particular coin, whichever minimum value, minimum coins required to make that amount is there, we'll add it with it. You see the dry run, you'll easily understand it. After all of this is done, we come out of the loop and return if my DP amount is still integer max, that means we could not calculate it, return minus one. Else, return our DP amount, okay? Whatever value is present over there. I hope you know this. This is ternary operator.

[01:12:23]Let's see the Python code as well.

[01:12:26]Um solution uh define coin change uh and pass the coins and the amount. If my amount is less than zero, return zero. And formulate a DP first having amount plus one as the size and populate it with infinity.

[01:12:43]And now, we are going to traverse in that um array, I comma amount plus one in that whole array. And for each coin in my coins array, if it's less than equals to current amount and my DP of current amount minus coin is not equals to infinity, then DP will contain the minimum value between DP and one coin plus DP of amount minus that coin. Minimum value required to make that amount.

[01:13:10]Return minus one if DP of amount is still infinity, else return the DP amount, okay?

[01:13:16]So, yes, these were all of the questions asked in Infosys SP and DSP. DP, trees, and graphs mostly will be asked.

[01:13:23]Yeah. So, yes, let's keep the video short. Um all the best for your exams. Thank you.