• 1 day ago
Transcript
00:00What do I have done in the code?
00:01I have defined total number of rows
00:04which is n which is 3
00:05and total number of columns
00:07which is m which is also 3
00:09I will create a function
00:10public static int
00:13because I have to return an integer
00:15count ways
00:16or grid ways
00:19I have the current cell number
00:23which I am standing on
00:24if my current cell is i
00:25i, j
00:26and I have total number of rows
00:28n and m
00:30So what I am going to do?
00:32I will call grid ways
00:34which I will start from 0,0
00:37because I have to return from the starting cell
00:39and I will pass
00:40n and m
00:42Now what do I have to do?
00:45What was my total number of ways?
00:47One was v1
00:48v1 says that you have to remove grid ways
00:51for i plus 1 and j
00:54and the other
00:54the other was v2
00:56that you have to remove grid ways
00:57for i and j plus 1
00:59Now as I have to return
01:04w1
01:07w2
01:08as my final answer
01:09and what will be the base case?
01:11My base case will come here
01:13This will be the base case
01:14that if I have to do
01:24this is my condition
01:27this is my condition
01:28for last cell
01:30I am standing on the last cell
01:31so what will I do?
01:32I will return from here
01:34because there is one way
01:35Now here I will cover another
01:37corner case
01:38or base case
01:40condition
01:41I will do else
01:46if
01:47if
01:48if i is equal to n
01:50or j is equal to n
01:52then I will not do
01:53any recursion
01:54If I go right
01:55then I will go out of my grid
01:57or down
01:58then I will go out of my grid
01:59then I will go down
02:02or right
02:02then I will go down
02:03or right
02:04in this case
02:04I will simply return 0
02:05I will return 0
02:06So, if i has crossed the boundary
02:08or column
02:10crossed the boundary
02:11then I have 0 ways
02:13I have to return 0
02:14So, I have simply returned 0
02:15So, I have two base cases
02:16One is the last cell
02:18and one is the boundary
02:19cross the condition
02:20This is my boundary
02:23cross condition
02:26and I have left both grid ways
02:27and then I have added both
02:29Now I am going to run this
02:31for 3 x 3
02:32So, how many ways
02:34I have total
02:356 ways
02:36How many ways
02:37come out of that?
02:38One time we run dry
02:39I have to take
02:40I have to take
02:42ways
02:42from this 0,0
02:44to my
02:45This is 3 x 3
02:46So, this will be
02:472,2
02:49Here
02:50I know
02:51that I have here
02:51one way
02:52Why is one way?
02:53Because
02:54how many ways
02:56one way
02:57I will go up one way
02:59because
02:59right is 0
03:00down
03:02Here
03:02one way
03:03will come
03:04down
03:05will come
03:06If I want to run
03:07out of that
03:08here
03:08I have 1
03:10down
03:10will come
03:11then
03:11this will be total
03:122 ways
03:12If I run out of that
03:14right is 0
03:15down
03:15will come
03:15down
03:16will come
03:17total
03:17one way
03:17If I run out of that
03:19right
03:19down
03:20will come
03:21total
03:21total one ways.
03:22If I take this,
03:23right will be two,
03:24down will be one,
03:25total three ways.
03:27If I take this,
03:28right will be one,
03:29down will be two,
03:30total three ways.
03:31And if I take this here,
03:32right will be three,
03:33down will be three,
03:34total six ways.
03:36So what should I have to do with my final answer?
03:38Final answer should be six.
03:40I mean, I have to go here,
03:41I have to go here.
03:43In fact,
03:44I can make those six ways,
03:44I can make you for your own.
03:46The first way will be right,
03:48right,
03:48down,
03:49down.
03:49The second way will be right,
03:51down,
03:52right,
03:52down.
03:53The third way will be right,
03:55down,
03:56down,
03:56right.
03:57The fourth way will be down,
03:59right,
03:59right,
04:00down.
04:00The fifth way will be down,
04:02right,
04:02down,
04:03right.
04:04And the sixth way will be down,
04:05down,
04:06right,
04:07right.
04:07So this way is six possible ways to go from this source cell to my target cell.
04:13Now if I will analyze this question that I have to analyze the time complexity,
04:16then the first thought that I have come to my mind is that it is what is one,
04:20what is a 2D matrix.
04:23So first of all,
04:24in our mind,
04:25because it is a 2D matrix,
04:27so what should our time complexity be equal to n square?
04:30So first of all,
04:31the time complexity comes to big of n square,
04:35or big of n cross m.
04:37but this code's time complexity is a lot more than it is.
04:41How is it more than it is?
04:42Because if I talk about levels on every level,
04:47I have two choices on every level.
04:48The first choice is to go right,
04:51the second choice is to go down,
04:53the second choice is to go down.
04:53And how many levels do I have?
04:55And how many cells do I have?
04:57The first choice is to go right and go down,
05:00the second choice is to go right and go down,
05:03the third choice is to go right and go down.
05:06So how many cells do I have in this way?
05:08The total of a grid is to go down.
05:12n plus m.
05:13In any 2D matrix,
05:15the rows plus columns are equal to total number of cells.
05:18Now I can say that,
05:19whenever I have to go to the source,
05:22I have to go to the source,
05:24then I have to go to the source,
05:25I have to travel my M,
05:29which are my columns,
05:31I have to travel here.
05:33So I have to take one right here,
05:35then take down,
05:36then take another right here.
05:38But I have to take two right.
05:40If I go here,
05:40then I have two right here.
05:42If I go down here,
05:43then you have two right.
05:44If I take one right here,
05:46then take the right again,
05:47then take one right here,
05:48then take one right here.
05:48If I go down here,
05:50then one right here,
05:51one right here.
05:52So I have to go in any way,
05:54whatever way.
05:55My total number of right turns,
05:59that will be equal to my number of columns,
06:03that will be equal to n.
06:05And I will do anything,
06:06any way,
06:07I have to take the source,
06:09If I go to target, the total number of down turns will be my total number of rows
06:18That will be equal to n, columns is m
06:21So right turns, I always have to take m right turns and down turns also I have to take n
06:26So every total turns that will be n plus m
06:32So I can say that if I have two choices in every cell
06:36One goes right and one goes down
06:38And I have to choose a total number of cells
06:41I have chosen a single path
06:43N plus m cells
06:44So my time complexity will be graded away
06:46Big of 2 to the power n plus m equal
06:49So this is exponential time complexity
06:51And this is a very bad time complexity when it comes to time complexities
06:55So the code will run very slow
06:57And n and m should be very small
07:01As compared to 1,000,000,000
07:04If we keep value, the code will not be able to run
07:06It will take a lot of time
07:08If you participate in coding code disk
07:10And the value of n
07:12We gave 10 to the power 5
07:14And the value of m was 10 to the power 5
07:15In that case, our code will not be completely clear
07:18I can say that it will be slow
07:20It will be a very unoptimized code
07:22But what is the time complexity of grid waste here?
07:26To the power n plus m
07:27Which is an exponential time complexity
07:30So the ways complexity
07:31C
07:31C
07:31C
07:31C