Most people use ChatGPT every day without understanding what's actually happening behind the answer. This course builds that understanding from the ground up — AI and machine learning basics, neural networks, deep learning, and large language models — then puts it to work with prompt engineering and hands-on, end-to-end projects, including building your own GenAI chatbot.
ℹ️ No prior AI experience required. This course is independent and is not affiliated with, endorsed by, or sponsored by OpenAI or any mentioned organization. For educational purposes only.
━━━━━━━━━━━━━━━━━━ 📚 Go Further ━━━━━━━━━━━━━━━━━━
💎 Once you understand how generative AI works, the next step is mastering the tools built on it — full library, every major AI tool, taught from scratch, no experience needed. 👉 https://MyAiForThat.com
These are the six topics that we will discuss about this and after we are done with this,
let's go ahead and take a look at some interesting coding interview questions. We'll prepare this
topic so thoroughly that you will be able to solve any coding interview question that deals
with backtracking. So let's get started. The first question which we have over here is
For this, let's take an example to first develop an intuition about this and after that we'll
take a more theoretical view about what backtracking actually is. So over here,
this is a Sudoku board and this I'm sure is a puzzle that you are well aware of,
but quickly talking about the rules that are involved in a Sudoku board, you have to fill
the empty spaces with numbers from 1 to 9. So you have 1, 2, 3, 4, 5, 6, 7, 8 and 9 and the rules
are that firstly in one box, so you can see that you have one box over here, one box over here,
one box over here. So in this manner, there are a total of nine boxes in this Sudoku board and
in each board, you need to fill all these nine numbers and you can fill each number only once.
So for example, you have a one over here, so you cannot fill one in these three empty spaces. So
that is rule number one. The second rule is that this is also applicable for every row. So that
means that in one row, notice that you have nine spaces and you can fill only these nine numbers
once in a row. So again, you have one over here, so you cannot fill one in any of these other empty
spaces. So that is rule number two and rule number three is that the same is true for every column as
well. So for example, in this column, notice that you have nine spaces and you can fill each of
these nine numbers only once over here. So for example, you have nine already filled over here,
so none of these empty spaces can be filled with nine. So these are the rules about the
Sudoku board or the Sudoku puzzle. Now let's use this and try to think about what backtracking is.
Now over here, let's go ahead and try to solve this Sudoku board. So over here, we have an empty
space. And again, as we have discussed, the possibilities are one, two, three, four, five,
six, seven, eight, nine. And among these, let's eliminate whatever is not allowed based on the
three rules that we discussed. So first, let's take a look at this box over here. So we already
have a nine and hence we can eliminate it. We cannot fill nine again over here. Similarly,
we have seven and four. So let's eliminate that as well. And I have six, one, and two.
So let's eliminate that as well. And I'm left with three, five, and eight. Now let's take a
look at this row over here. I have nine, which I've already eliminated. I have six, I've already
eliminated six, and I have one and four. And I've already eliminated one and four as well. So there
is nothing more to be eliminated over here based on the row. And then let's take a look at the
column over here. So in this column, notice that I have nine, four, and six. So these are also
already eliminated. So there's nothing more to eliminate. And you can see that I am left with
three values, which can be filled over here. And the values are three, five, and eight.
All right. So I've identified that over here, I can fill either three, five, or eight. Now let's
go ahead and fill three over here. So I filled three over here. And after I'm done with that,
I proceed and try to fill the next position, which is empty. But again, as I go on in this manner,
notice that for this particular box over here, the second box, I cannot fill three over here,
because this empty space cannot be filled with three, because three is already there in this
row. Similarly, I cannot fill three in this empty space over here, which is again in box number two,
because three is already there in this column. Let's take the help of the diagram that we have
previously drawn, right. So this will help us to keep track of the recursions that's happening.
Now let's say we have passed in this array over here, one, eight, and seven. Now let's walk
through the code with this. Now we call the function and we pass this array over here. So
nums is one, eight, seven over here. And then we initialize output to be an empty array. So let
this be our empty array, which is the output. Now we come over here, we have our helper function
defined. And then we come over here and the helper function is called, we pass in the array one,
eight, seven, and the index zero is passed. And then our subset at this point is an empty array.
So we come over here. Now at this point, I is equal to zero. So I is not equal to nums dot
length, which is three, right? So the length over here is three. So we come over here. All right,
so this is the part where we are in this diagram. And then we are going to call recursively the
same helper function. And we are passing the array one, eight, seven, and I at this point is
equal to one, and the subset at this point is empty. So you can see that we came over here.
All right, so at this point, I is equal to one. Now, again, we come to the helper function,
and I is equal to one at this point, you can see we are over here, and I is not equal to three.
So again, we come to this part where again, we call the helper function, and I is incremented.
So I is equal to two. So we can see that we come over here, right? So I is equal to two at this
point. And again, the subset is the subset array is empty. And we come and call the helper function
again. So we are over here again, at this point, I is equal to two. So it's not equal to nums dot
length. So we come over here. And we call the helper function again with I is equal to three
at this point, which is this over here. At this point, I is equal to three. All right, so we are
again over here, let me just clear this, so that we can keep track of what's happening. So we are
over here, I is equal to three. And at this point, we see that I is equal to nums dot length, which
is three. So we are going to push a copy of what is there in the subset, which is an empty array,
right? So subset dot slice means we're making a copy of this, and we are pushing it to the output
array. So let's write that over here. So we are getting this copy over here. And this is added to
the output array. Now, we are going to return right. So this call ends because we are returning
over here. So the helper function call over here is ended. Now we come back. So we are done with
this call where I was equal to two, right? So I was equal to two. So two plus one gave us three.
And that was this call. So that is over. This is over. Now we come back. Now what we are doing
over here, we come to this line. And at this point, we are pushing nums at I and I is equal to two,
right? So this is zero, this is one, this is two. So we are pushing seven to the subset. So that is
what we are getting over here. And then we are calling the helper function. So this is a helper
function called where the subset is this array over here with which has seven as an element.
And I at this point is two plus one, which is three, right? So we are coming again, we are
calling the helper function, we are coming again over here. And we see that I is equal to nums dot
length. So we are going to push a copy of the subset, which is this over here to the output
array. So we are getting seven over here. And then we are returning. So this call ends over here.
So we are done with this and we're done with pushing seven to the subset, we call the helper
function with the subset having the element seven. So that is also done. Now we come out. So because
this returns over here, right? So we come back over here. Now at this point, we are going to pop
seven. So we added seven to the subset. Now we're going to remove seven from the subset. So again,
our subset at this point becomes an empty array. So we are doing this because we're going to use
the same subset array. So we don't want to make copies, right? So when we push to the
output array, we make a copy. But again, throughout this, we're going to use the same subset array.
So we have popping seven. And this is how our subset looks at this point. And we're done.
Right. So this part over here is done. Now, this was part of the call where again, let me just
clear this up so that we can keep track of it. So we came to this part as part of this call,
right? So it came from eyes. I was equal to one. I was equal to one. And one plus one gave us two.
So that is how we came over here, right? So that is how we came over here. And once we came over
here, we recursively called the helper function and came here and then here. So this is done.
Now we come again over here. So this part over here of this call, right? Again, we can we have
to visually track this because this is a recursive solution. So to make it intuitive, that's why I
have this diagram over here. So this part over here, this call is done. So this line over here
is done right now. We are going to push nums at I and I at this point is equal to one. So eight,
eight is pushed to the subset. So our subset looks like this at this point. And then we are going to
have a helper function called right. So again, this is done. This is done. This this line over
here was done. So now we are having this call over here where the subset is an array with eight
and I at this point is one. So we are passing one plus one, which is equal to two. Right. So we are
coming again to the helper function because this is called. Now, once we are over here, we check
whether I is equal to three. No, I is equal to two at this point. Right. So we passed one plus
one. So I is equal to two. So we come over here. Now we are going to again call the helper function
and we are passing this. This is the subset at this point and I is going to be incremented.
So that is this call over here. So we come over here. I is equal to three. Again, we come over
here. We see I is equal to three. So we push to the output array what we have over here. So we
get comma eight the array with only element eight over here. So this call is also done because it
returns over here. So this is also done. Now we are done with this call where I was equal to two.
Right. So this is the call where I is equal to two. And we did this call. So this one over here
that is completed. So we come over here. Now we are going to push to this nums at I and I is equal
to two. So nums at I is seven. So we are going to push seven to this array over here and we get
eight comma seven. And with this, we are calling the helper function and incrementing I. So I over
here is three. And this is how our subset looks like. Again, we come over here. I is equal to
nums dot length at that point. So we push eight comma seven, the array eight comma seven to our
output array and we return. So this is also done. Now, at this point, this this this is this is
completed. Right. It's left and it's right or adding and not adding and adding is completed.
So we come over here and we pop. Right. So at this point, when we come out of this,
we just added seven. So we pop seven. So we remove seven from this. Now, when we come out of it,
we added eight. So at this point, we had added eight. Right. So again, over here,
we are going to remove eight also and we get back to this place. So this is, again,
how our subset looks like. Let me just clear this so that we can keep track and we can continue
tracing the algorithm. All right. So now we have completed this call. Now, what do we do after
this? Now, over here, it was part of this call. Right. All of this, what we did was part of this
call. Right. Which was when we passed the empty subset and I was equal to zero. So we passed zero
plus one. So it was part of this call, whatever we did so far. And that part is completed. So we
come back to this. Now we are going to push nums at I and I is equal to zero. So we are going to
push one. So we are going in this direction. We are going to push and then we are going to make
the helper call. So this is this helper call. All right. So where the subset is an array with
only one and I is incremented. So I at this point becomes equal to one. So zero plus one. It's one.
So we we have this call. So this part is completed. So we have this call.
And as part of this call, again, we come to the helper function. We move to the left. Right. So
we increment I and we don't add anything to it. So that is this call. And again, as part of this
call, we come back to the helper call function. We again call it without with incrementing I and
without adding anything, which is this call, at which point later we have I is equal to three.
Similarly, after that is done again, we push nums at I, which will be seven at that point,
because I is equal to two when we are over here. Right. So we push two and then we make this call,
which adds one comma seven to our output array. So this is also done when it returns.
And after it returns, we're going to pop seven. So we're going to remove seven.
And when we come back over here, we have removed seven. So this is how it looks like. Right. So
the left part, this is done. Right. This is done when I was equal to one. Right. So one plus one
gave us two and we had this call. So now we are going to have the call where we add. So at this
point, I is equal to one. We're going to add eight. We get one comma eight and I is equal to
two at this point. Again, we go left. So we add one comma eight and this call is done and we come
back and we add seven. So that also is added to the output array at this point. We remove seven.
We come back over here. We remove it. We come back over here. And finally, we remove one, which is
this over here when we had added. So when this was adding one, when we come back to that call.
Right. So once that this call is completed, we come back and we remove one also. So we get our
output over here. And this is how this function works. Now, let's just summarize what is happening
over here. So we can see that if we trace the algorithm on a high level, what it is doing is
first it comes over here. Then we recursively call it again. We come over here at this point.
This is added. Then we add seven. Then we come back. We add eight. Then we print it over here.
Then we add seven. So you can see that this is how the algorithm works. Then we go all the way up.
We go this way. We go this way and we go this way. We have added it over here. Then we add
this one over here. We come back. Then we come over here and we come over here at that point,
which we add the array one comma eight. And then we come over here. And at this point,
we add one comma eight comma seven. And that is how we are getting the output. Now, let's take a
look at the space and time complexity. We have already discussed that. But let's just quickly
take a relook at it over here. We can see that the input array had three elements at this point
and the power set will have two to the power n elements, right, which is eight. So we can see
that there are eight elements over here. So that is true to the power n. Now, for each of these,
what the number of times we are pushing elements into these subsets and range from zero at this
point is zero one one two one two two and three. So it's ranging from zero to three or zero to n.
So on an average, we are doing n by two times pushing to a subset. So that's why we can say
that the time complexity is of the order of two to the power n into n by two. And again,
this is a constant so we can just avoid it. That's why the time complexity of this algorithm
is of the order of two to the power n into n. And the space complexity is also of the order of two
to the power n into n. Because we can see that in these subsets, right, there are two to the power
in subsets. And on average, we can say there are n by two elements per subset, because it is ranging
from zero to n. So again, it's two to the power n into n by two, and I'm just removing one by two
because it's a constant. That's why the space complexity also of this solution is
O of two to the power n into n. Two aspects in this statement. The first aspect is jump
to the furthest reachable index. And the second aspect in this statement is from each reachable
index. Now let's try to understand these two pieces to thoroughly understand this approach.
And for this, let's take an example. Let's say the array which is given to us is two zero one
three two. And I've also written the indices over here, which span from zero till four. Now we start
at index zero. And the furthest reachable index from this index over here would be zero plus two.
Okay, that's taking a jump to this index over here. So from index zero, the furthest reachable
index is index two. Alright, now we move to the next index. And we see that this index over here,
first of all is reachable, which is the second criteria over here, because you can just take
one step from this place to reach over here. So this index over here, first of all is reachable.
And once you reach this index over here, you cannot take any jump, you can't move forward.
So the furthest reachable index from this index is one itself. Okay, so we have covered these two
aspects, when we consider this index. Now let's go ahead and go through the remaining indices,
so that this becomes very clear. Now we come to this place over here, this index,
first of all, we see that this index, which is index two is reachable, because you can just take
two steps from index zero to reach index two. So index two, first of all is reachable. And once
you reach index two, the furthest reachable index from index two would be index two plus one, which
gives you three. Okay, so again, we have covered these two aspects. Now we move to the next index.
So we come over here. And again, we see that this index, which is three is reachable, because you
can take one step from this place over here. So this index is reachable. And once you reach over
here, you can reach the last index, because you can take up to three steps. And you just need to
take one step to reach the last index. And therefore, at this point, we can just return true
because we have seen that yes, I can reach the last index of the array which is given to me.
So what we have seen over here is that we just need to iterate through the indices over here in
the array which is given to us. And we need to keep checking whether that particular index is
reachable. Now if it is not reachable, we would just return false because we would not be able
to go further. And I'll show that to you in one more example. But if it is reachable, we will
also calculate the furthest reachable index from that particular index. And we'll keep doing that.
And if we see that at some point, we are able to reach the last index of the array which is given
to us, then we will just return true. Now let's take a look at one more interesting example to
thoroughly understand this approach. So let's say this is the array which is given to us. And the
indices span from zero up to nine. And again, we start at index zero. Now from index zero,
the maximum reachable index is zero plus two, which gives me two. Okay. And I proceed to the
next index. Now I see that index one is reachable, because I can take one step from index zero.
And the maximum index that I can reach from index one would be one plus three, which is equal to
four. We proceed to the next index, we see that two is reachable, because the maximum reachable
index at this point is four. So anything up to four is reachable. Okay. So two is reachable.
And the maximum that you can reach from index two would be two plus one, which is three. Again,
we come to index three, three is reachable. And from three, the maximum that you can reach is
three plus zero, which is three itself. And four is also reachable. So we have seen that over here.
So up to four, the indices are reachable, but starting index five, the indices are not
reachable, right? Because notice all of these values are zero. So the maximum that is reachable
from here will be three itself. And the maximum index that is reachable from this position over
here will be four itself. So the indices beyond four, which are the indices starting at five,
and going up to nine are not reachable. And for that reason, we are not able to go beyond index
four, which means that we are not able to reach the last index of the array which is given to us.
And hence, we can just return false. Okay. So again, these are the two aspects of this algorithm,
we need to jump to the farthest reachable index from each reachable index. Now, if you see that
at some point, the index where you reach is not reachable. And that would happen in this example,
once you keep iterating over the indices, you start over here. And then once you reach over
here, you would have reached an index which is not reachable. And at that point, you can just
return false. So this is the first approach which we will use to solve this question.
And notice that this is a greedy algorithm. So what are the different choices that we have over
here? So as we have seen over here, when i is equal to zero, the different choices for j was
zero, one and two. So the choices are for j to take the values from i to length minus one. So
for j is equal to i to length minus one. And then over here, the next part in our blueprint was we
need to check whether that particular choice is valid or not. But in this case, because we're
just finding all the permutations, all these are actually valid cases, right? So j taking zero,
one or two, all of these are valid. So we don't need to check this in this question. Alright,
because everything is valid. So let's proceed. Now, if things are valid, we need to proceed
to this part of the blueprint, where we make a choice, which in our case is swapping the elements
at i and j, and then recursively call the same function again, and then revert the changes for
the backtracking step. So let's write that in our pseudocode. So making the choice is swapping
the elements at index i and j. And then we are recursively calling the function again,
passing an index, which is i plus one, a higher index, because over here i was zero. Then when
we recursively call it, we want to pass i equal to one. And over here, when we again recursively
call the function, we want to pass i is equal to two. So that's why over here, the input parameter
is i plus one. And once we're out of this, we want to swap the numbers at index i and j again back,
because again, we're implementing a backtracking solution where changes are made in place. So this
is going to be the backtracking step. Alright, so we have discussed the pseudocode, we have
successfully written the pseudocode using the blueprint that we have discussed previously.
Let's now trace how the algorithm would solve this. Because when we came up with the recursion
tree, we drew it out in a more intuitive manner so that we could easily understand it. But now
let's see how the algorithm would approach it. So initially, we would call the perm function.
And at this point, i is going to be equal to zero. And then this is going to call the perm function
recursively with i equal to one. So over here, i is zero, and j is zero. And over here, i is one,
and j is one. And then it would again call the perm function recursively, at which point i is
going to be equal to two. And when i is equal to two, we'll hit the base case. So this over here
is going to get added to the results array, the final array that we will be returning, which has
all the permutations. And after that, it would just return. So when it returns, we would again
come over here. And we would come to this line over here, where we again swap the elements at
one and one and we'll be back over here. Now, let's trace this part over here to understand
it in a better manner. Because over here, even though we did some swaps, the array does not
change right because we were swapping zero with zero and one with one. So once we are back over
here, and we call the perm function recursively. And at this point, i is going to be equal to one,
but j is going to be equal to two. Okay, so we're going to swap the elements at one and two,
and one, two, three becomes one, three, two. And again, it will call the function perm recursively
and i will be equal to two, and we will add one, three, two as well to our results array.
So at this point, one, two, three, and one, three, two gets added. But then notice that
once this is done, it's very important to do the backtracking step, where we again swap the
elements at index one and two. So this is index one, this is index two. By doing this,
the nums array again changes from one, three, two to one, two, three. Now this is important
because over here, when we want to swap the elements at index zero and one, we have to ensure
that we are starting with the nums array in this manner itself one, two, three, so that when we
swap the elements at index zero and one, this changes to two, one, three. So this is why the
backtracking step is very important. So next we come over here. And then we come over here, we add
this to the results array. Again, we come back. So when we backtrack, again, over here, we can't
see it, but it's to reverse the change, revert the change that we did. So again, we come over here,
notice two, one, three changes to two, three, one, we add this to our results array, and then
we revert the changes so that two, three, one again becomes two, one, three. And we come back
again. When we come back over here, two, one, three changes to one, two, three. This is again
important. Notice, because if we did not change this to back to one, two, three, then this would
not work, right? But because of backtracking, again, at this point, the nums array becomes
one, two, three. And when we swap the elements at index zero and two, it changes to three, two, one.
So this is how the backtracking algorithm works. And notice that the changes to the nums array
are made in place over here. The Tower of Hanoi problem is a classical problem where we can use
recursion to come up with solving the problem. But in this video, let's try to think together
about how can one identify that recursion is a good technique to solve this question.
For this, let's think whether solving a subproblem can help us to solve the original problem.
Now, over here, for example, we have three rods and we have, let's say, n discs. What would be
a subproblem for this? Of course, the rods are not going to change. Even for a smaller problem,
the number of rods is going to be the same, but the number of discs is going to be lesser.
So, a subproblem could be having n minus one discs. Now, let's say we have n minus one discs
over here. So, notice I have removed one disc. So, we have n minus one discs. Now, let's think
whether if we could move these n minus one discs or if we had the solution to move these n minus
one discs to a required rod, could we use that to solve the original problem, which is to move
n discs from R1 to R3? Now, notice that if I could move the n minus one discs from this rod over
here to this rod over here, it would look like this, right? So, I'll have all the n minus one
discs over here. Now, if I could achieve this, then I could just move this disc from rod one
to rod three and then these n minus one discs could just be placed on top of it and that would
help me solve the question, right? So, notice that by solving a subproblem, I was able to solve
the original problem, okay? So, again, but there is an interesting observation over here. We are
not moving the n minus one discs from rod one to rod three because in that case, we would have all
these over here and then the biggest rod could not be placed on top. So, again, it's this question
over here is not having something called optimal substructure, which is something that we will
discuss when we discuss dynamic programming. Now, because it does not have optimal substructure,
we cannot use dynamic programming for this question. But again, this is just a side note.
But over here, we are just trying to identify that we can use recursion to solve this question. So,
we were able to solve the original problem by doing something about the subproblem and hence,
we have seen that we can solve this question using recursion. In the next video, let's try
to understand the approach which can be adopted to solve this question and let's also develop the
intuition behind that approach as well as the recursive case. Now, the base case would be the
scenario where i, which is the index that is passed to the helper function is equal to the
last index of the nums array. Because if that is the case, as you discussed in the previous video,
there's no value beyond it. So, there's no point swapping the element at that particular index
with anything else because there's nothing beyond it. So, if i is equal to the last index, which is
equal to n minus one, if n is the length of the nums array. So, let's write that over here.
So, let's say let n is equal to nums dot length. So, if this is the case and if i is equal to n
minus one, we would have hit the base case. So, there's no more swapping to be done and all that
we need to do is, we just need to make a copy of the current state of the nums array and push it
to res. Okay. So, I can say res dot push and over here, we're going to make a copy of the nums array
at this particular state. And again, the reason why we need to do this is because this is a
backtracking solution. So, as we have discussed, we'll be making changes to the state of the
problem in place. So, at a later stage, the way that the nums array looks would be different.
So, that's why we're making a snapshot or we are making a copy of how the nums array looks at this
particular point and we are pushing it to the results array and then we can just return. Okay.
So, we are stopping going further down that particular branch of the recursive tree
and we are returning. Now, if this is not the case, then we proceed to the recursive case.
Now, this is the case where i is not equal to n minus one. And in this case, we need another
variable. Let's call it j and j will take the values starting at i and it will go up to the
last valid index, which is n minus one. Okay. And for each value of j, we are going to do three
things. First, we're going to swap the elements at index i and index j. So, I can say nums at i
comma nums at j is equal to nums at j comma nums at i. Okay. So, I've swapped these two elements
and then we'll go deeper down that particular branch of the recursive tree. So, for that,
I'll recursively call the helper function and we'll be passing i plus one to it. Now, after we come
back over here, that is after we have gone down all the way till the base case in that particular
branch on the recursive tree and we get back over here, then we'll have to proceed and do the
backtracking step. Okay. And remember, this is important because we're making changes to the
state of the problem in place or we are changing nums, the nums array itself to get the various
permutations and then to explore another branch in the recursive tree, we need to keep reverting
the changes we have made. So, that's what we're doing over here. So, I can say nums i comma nums
j is equal to nums j comma nums i. Okay. So, again, we are reverting the changes that we made
in this line of code over here and this is the backtracking step. All right. So, that's it. So,
this should solve the problem. Now, let's go ahead and run this code and see if it's passing all the
test cases and you can see that it's passing all the test cases. In case you're stuck and need help,
do make use of the user logs which are provided over here for every test case. Welcome back.
Now, let's discuss how we can solve this problem. Now, for this, let's take an example. Let's take
this example itself. Right. We have one two, then the next element is an array three comma four
and the next element is an array and that array again has another array as its element, which is
this two over here. So, this is the input. Now, we need to write a function. So, let's call this
function some power. All right. So, we have function some power and we will be passing the
array to this function. Right. So, let's pass the array over here. And then initially, as we have
seen, this level over here is one. Right. So, the power to which we will raise these elements one
plus two plus this equivalent value plus this equivalent value is going to be one. Right. So,
the initial power is one. So, let's pass that also. All right. Now, once we have the array,
what is the output that is requested from us? It's the sum of the elements to the power which
we have passed over here. Right. So, we will be returning the sum of the elements and we will
raise that sum to the power which is passed over here. So, this is a basic understanding. Right.
So, this is something that we understood because we have understood the question.
Now, let's proceed and see how we can solve this problem, actually. So, we will be having this
input array and we will need to traverse it. Right. So, let's say we are traversing it in
this direction. Now, what we will do while traversing this array? We will take each
element and we will check whether this element is an integer or it's whether it's an array.
All right. Now, if it is an integer, then it's very easy. Just add it to the sum. Right. So,
at the beginning, we will have some let's say we initialize some to zero. So, sum is equal to zero.
Right. So, let's just write that over here initially. And then if we found that that
particular element is an integer, then we just add it to some. So, that's not difficult. Right.
So, we can just add it to some. Now, if we see that the element is not an integer, but an array,
then what do we do? We need to get its equivalent value. Right. And you can see that based on the
way this is constructed, we can get the equivalent value of this array by passing this array to
another sum power function. Right. So, we can recursively call the same function sum power,
which is this function which we are writing over here itself. And we will be passing the particular
array which we got over here. Right. So, this array would be passed over here and the power
will be incremented by one because let's say we got this element over here. At this point,
we will be passing three comma four as the array to the recursive call of the same function and the
power will be one plus one, which is two, because this is in level two. Right. So,
these brackets are level two. And then again, the same thing happens. We check the next element.
If it's an integer, we add it to the sum. If not, we will again recursively call the function.
Right. So, what happens when we recursively call the function over here? What happens is it will
find whatever is going to be returned over here. It will come back. Right.
And once it comes back, we can just add it to some. All right. So, let's walk through this
example over here. Now, let's say initially some is equal to zero. All right. So, we have some
equal to zero. And now we are going to check this logic over here, which we have written.
Right. So, if it's an integer, we add it to some. If it's an array, we will recursively
call the same function. So, let's walk through it. Now, we take the first element, which is
equal to one. And we see that it's an integer. So, we add it to the sum. So, zero plus one
is equal to one. So, the sum at this point is equal to one. Again, we proceed further.
We look at the next element, which is two over here. And we see that it's an integer. So,
we add it to the sum. So, we do one plus two. All right. Now, we take the next element,
which is an array. Right. So, we see that it's an array. So, we call the some power
function recursively and we pass the array three comma four and the power at this point is equal
to two. Right. So, again, what will this call do? Right. When we are inside this call, we are going
to repeat the same logic. Right. So, we will take the first element. Sum is now zero. And we will
take the first element. And at this point, this is an integer. Right. So, we add three to zero
and we get the sum as three. Now, we move we move the pointer and we check the next element.
We again see that's an integer. So, we add it to the sum. So, three plus four is equal to seven.
And once we have the sum, we just return the sum of elements, which at this point is seven
raised to the power. Right. And the power we have passed over here is equal to two.
So, we will be returning seven to the power two. Right. So, this function over here,
what it does, this call, what it does is it will return three plus four to the power two,
which is equal to forty nine. Right. So, this will be returned. And we are back again in the
first call. Right. So, at this point, we have one plus two plus forty nine. So, we are we have done
with this element, this element and this element. Again, we move to the next element, which is this
one over here. We see it's an array. And hence we recursively call the sum power function.
So, let's write that over here somehow. And we are passing these two. Right. So, we are passing
this element over here. Right. So, that the element over here and the level was one initially.
So, we increment that level by the power was one. Right. So, level was one. So, power was one.
So, we increment that and we change it to two and we recursively call this function.
Now, once we are inside the function, what will happen? The array now which we have is this over
here. Right. This one over here. We again check. We take the first element. We see it's not an
integer. This is again an array. Right. So, what happens? We will again come over here and
recursively call somehow. Right. So, after this call, again, we will recursively call somehow.
And at this point, we will just pass array two, which is this element over here. Right. And the
power will be again incremented from two to three. Right. Again, we are inside the function over here.
Now, sum is again zero. Now, when we look at the elements, we see that the element over here is
just two, which is an integer. Right. So, we just add two to zero and we get the sum as two.
So, sum of elements at this point is equal to two and the power is three. So, we return
two to the power three, which is equal to eight. Right. So, this eight is returned. All right. So,
we found eight. So, it's returning back. It's returning back. And we will put eight over here.
Right. Again, in this call, we got this as eight. Now, we can just calculate this over here. Right.
And the array is just eight and the power is two. Right. So, to calculate this again,
we come inside the function over here. Sum is zero. We look at the first element,
which is just an integer. So, we add it to sum. So, zero plus eight is equal to eight.
And then we raise it to the power, which is equal to two. So, eight to the power two gives us sixty
four. That's what's returned over here. Right. Sum of elements is eight and power is two. So,
eight square, which is sixty four is returned back. Right. When we call this. So, the return
function gives us six. The return statement over here returns sixty four. So, over here we have
sixty four. And now we just add that to the existing sum. The sum so far was one plus two
plus forty nine. And we add sixty four to that and we get the answer as one one six. And again,
when we return, this is the sum of elements, which is one one six. And we raise this to the
power one, which is again one one six. And we return it. And this is how we are going to solve
this question. So, let's quickly recap. We are going to solve this using recursive function
calls. So, we traverse the given array, input array, and we are going to check whether each
element is an integer or an array. If it's an integer, we will just add it to the sum.
If it's an array, we will recursively call the same function and pass this particular array.
And we will increment the power and we will pass that over here. And once it is returned,
like, for example, it returned over here forty nine. Again, we will look at the next element.
Again, we recursively call the sum of functions till it returned the value sixty four. And that
is again added to the sum. And that gives us the final sum, which is one one six. And that would
be raised just to the power one, because at this level, the level is one. So, the power is just one
and we have our solution. All right. Now, let me just clear this up and let's quickly look at the
time and space complexity of this solution. Now, when it comes to the time complexity,
you can see that we have to traverse this array once. So, the time complexity over here is O of
n. But remember, n over here is not one, two, three, four. The initial array, which is given
to us has four elements. But that is not this n over here. This n is the total number of elements
in the main array and all subarrays because we have to traverse through all of these elements.
Right. So, in this case, what is the total? What is n in the example which is given to us?
We have one, two. Right. This is one. This is two. This element over here is three.
And inside this, we have two integers. So, this is four. This is five. Now, this element over here,
this one over here is six. So, this is one element. Now, inside this element,
we have this array. Right. So, this is seven. And inside this, we have one element. So, this is
eight. So, in this case, in the example which we have over here, n is equal to eight. So,
the time complexity is O of n. And in this example, n is equal to eight. And n over here,
it's important. Remember, in the interview, you have to explain what you mean with n.
So, in this case, n is the total number of elements in the main array and all subarrays,
which we have seen over here is equal to eight. All right. So, the time complexity is O of n.
Now, let's look at the space complexity of this solution. Now, the space complexity will be the
number of recursive calls in the call stack, the maximum number of recursive calls in the call
stack at any point of time. Right. Because we are not using any extra space apart from that.
So, we are going to use space because this is a recursive solution. So, the space complexity over
here is O of d, where d is the maximum depth of the call stack. Right. So, this is the maximum
depth of the call stack, which is the maximum number of recursive calls at a particular given
time. So, it should be at once. So, in this case, we have three levels. Right. So, this is level one.
This is level two. And over here, we have level two and level three. So, the maximum depth will
occur over here. And that would be three. Right. With dynamic programming. Now, for discussing this,
let's take an example. Let's say the array which is given to us is this array over here,
which is two, three, one, zero, four. And let me write the indices which go from zero up to four.
Now, we start at index zero. And because the value over here is two, it means that I can make a jump
of up to two indices. OK. So, I can go from here to here or from here to here. So,
these are the two places that I can reach from this index over here. So, notice choices are
involved over here. I can either choose to come to this place or I can choose to come to this
place over here. And when we discuss dynamic programming, this was one of the hints that
indicate that probably we can use dynamic programming. Now, there is another interesting
thing that we can see over here. We start at index zero. And if I make a jump of one unit,
I reach index one. And if I take a jump of two units, I reach index two. OK. And notice we are
having branches over here. This is another interesting hint that we are discussed in
dynamic programming, because whenever you have branches like this, there is a high chance for
overlapping subproblems. Now, again, just to take this a little bit deeper from index one,
we can either take a jump of one, two or three. OK. So, that means I can reach indices two,
three or four. So, these would be the branches. And notice we have two over here and we have two
over here, which indicates the presence of overlapping subproblems. And again, remember,
this over here represents whether we can reach the last index starting at index two. So,
that's the subproblem over here. And that's the same thing that we have over here, whether we
can reach the last index starting at index two. So, we have overlapping subproblems. We have
branches. We have choices. And all of this indicates that probably we can use dynamic
programming to solve this question. Also, notice that this question has optimal substructure. And
with that, I mean that we can use solutions to subproblems to identify the solution for the
original problem. Again, for example, notice a subproblem could be whether you can go to index
four from index two. OK, that's what we had over here. And we can use these to identify the
solution to the problem. OK, another example would be if I know the answer to the subproblem,
which is that I can go from one to four. OK, and I can do that because I can just take a jump of
three units. So, I can go from one to four. So, knowing this subproblem, OK, which is this over
here helps me solve the original problem, which is whether I can go from zero to four, which is
what we have over here. And again, notice I can go from zero to four if I can go from one to four
because I can just go from zero to one. That's also possible. Right. So, again, notice knowing
the solution to subproblems helps me identify the solution to the original problem at hand.
And therefore, this question has optimal substructure. And we've already seen that
there's a high chance that it has overlapping subproblems. And in fact, we did validate that
there are overlapping subproblems. And for these reasons, we can use dynamic programming to solve
this question. Now, a quick side note, OK, we will not be covering the dynamic programming approach
in detail in this video, but we'll just build the approach over here. And I'll give you a separate
article in this section where the dynamic programming solutions will be mentioned.
All right. Now, let's take the example where the array which is given to us is two, three, one,
zero, four. OK. And the indices start from zero and go up to four. Now, if I were to draw the
recursive tree over here and again, remember, whenever you start with dynamic programming
and when you're dealing with a new type of question, always first come up with the recursive
solution, then memorize it, and then you will be in a position to even write the tabulation approach.
So if we take a look at the recursive tree over here, I'm starting at index zero and from zero,
I can get to index one or two. And from index one, I can get to index two, three and four.
We have already discussed that previously. Now, notice what's actually happening over here is that
we are following a backtracking or a recursive approach over here. And again, it's not typically
backtracking in the technical sense where we are making changes to the state of the problem in
place. But rather, technically, it's just a recursive approach where we will be exploring
all the different paths possible until we either get true or we have explored all the possible
paths and we see that it's not possible. Right. So this would be the recursive way of solving
this question. And then you can memorize this by just having a DP table. So over here, you have
five elements. So in the DP table, you'll also need five cells and you will fill every cell
with either true or false. And again, what would each cell represent? For example, this cell over
here would represent whether you can get to the last index from this cell. So if you can do that,
we will fill true over here. Otherwise, we'll have the value false over here. So this is how
you can memorize this. And if you can write the memorization solution for this problem,
you can definitely write the tabulation approach or the bottom up approach as well. Now, again,
as I've mentioned, we're not going to discuss this in detail over here because we are dealing
with the greedy approach. But I will provide you an article with the dynamic programming
solutions as well. All right. So let's get back. We have seen that we can solve the jump game
question using dynamic programming. Now, let's discuss why we can solve this question using the
greedy algorithm. First of all, notice this is an optimization problem because we had discussed that
the greedy approach is used for solving optimization questions. Now, how is this an
optimization question? We're just trying to see whether you can get to the last index when you
start at the first index. How come this is an optimization problem? Right. So again, you can
think of this as maximizing the reach within the constraints provided by the elements of the array.
And again, with maximizing the reach, we mean whether you can reach this position or not.
And the constraints provided by the elements of the array is the value in the array at each
position because that determines the number of positions you can jump. So that's why this is an
optimization problem. All right. So this is an optimization question. Now, what else is there
that can help us identify that this is a question that can be solved using the greedy algorithm?
Let's think about that. So the next thing that helps us identify this as a question that can
be solved using the greedy algorithm is the fact that this problem follows the greedy choice
property. And again, why is that the case? This is the case because making locally optimal solutions
will help us arrive at the global optimal solution, which is to identify true or false.
And again, we're just trying to understand whether we can reach at the last index,
starting at the first index. Now, what is the locally optimal choice or the greedy choice
that we will be making at every index? The thing that we will be doing is to jump to the
furthest reachable index from each reachable index. We will soon discuss this in detail when
we discuss the greedy approach for solving this question. Now, if this is not clear to you,
let's just assume that this is true, because this will soon become clear to you in the next video
when we discuss this in detail. But because this is true, and we're just assuming this to be true
at this point, the question follows the greedy choice property. And this also helps us understand
that this is a question that can be solved using the greedy algorithm. Alright, in the next two
videos, let's discuss two greedy approaches that we can use, which are pretty similar,
with the only difference that in one case, we will be going from the beginning to the end,
and the other case, we will be going from the ending of the array to the beginning. Okay.
So, let's discuss two greedy approaches for solving this question.