Hi everyone, let's do this question.
You are given an array of non-negative integers.
Write a function that will take this array as input and return the sorted array using radix sort.
So over here we are going to learn how to implement radix sort, and also take a note that it's given
in the question that the integers are non-negative.
Now, if it is mentioned that the integers can be negative, then the way you implement the radix sort
will be a little bit different.
But over here in this question we are dealing with radix sort where the integers are non-negative.
Now in this section we are going to have three parts.
First, we will try to develop an intuition on how the radix sort works.
After this, we will go ahead and learn the counting sort algorithm.
And we are learning this algorithm over here because we will be using the counting sort algorithm in
part three to implement the radix sort.
So this is how we will proceed.
Now let's go ahead and develop an intuition on how the radix sort works.
Now for this, let's take an example.
Let's say the array which is given to us is this one over here.
That is 123, 78, 63, 19 and five.
Now how the radix sort works is that first we will sort these numbers only based on the digit in their
units place.
So for example, in 123 the digit in the units place is three.
Similarly, in 78 it is eight, in 63 it is three, and in 19 we have nine.
And over here we have five.
So let's go ahead and see how this works.
So let's sort these numbers based on the digit in their units place.
So we can see that the lowest value is three.
So we have 123 itself over here.
And after this we have 63.
And you can see that there is a tie over here.
Right.
You have three over here and over here.
So in that case the initial relative ordering is maintained.
So we have 123 then 63.
After this we will get five because after three the next greatest value in the units digit over here
is five.
So we have five over here.
And after five we have 78.
Then we have 19.
So we just sorted these numbers which were given to us based on the digit in the units place.
Now what we will do is we will go ahead and sort these numbers based on the digit in the tens place,
which is two, six, zero, seven and one.
And over here there was nothing.
So that's why we have written zero, because we can write five as zero five also.
Now let's go ahead and sort them.
So the least value is zero.
So zero five comes first.
Then we have 19, then one 2363 and then 78.
Now you can see that the numbers are sorted as per their 10th digit.
So zero, one, two, six and seven.
Now what we will do is we will go ahead and sort these numbers based on the digit in their hundredths
place hundredths place over here.
And if there is nothing then we will just mark zero over there because again we can write five as 005
also.
So let's go ahead and do that.
So we have zero zero.
And then we have one over here and over here.
And here also we have zero.
So there is a tie between these four numbers.
So the initial order is maintained.
And then we have 123 coming last.
So when we order these numbers based on their hundredths digit we get 519 6378 and 123.
So this is how radix sort works.
And you can see that these numbers over here are now sorted.
So this was the initial array.
And you can see that the numbers over here are sorted.
Now what did we do.
We sorted the numbers initially based on the digit at the ones place, then at the tenths place and
then at the hundredths place.
Now we did not proceed to the thousandths place because there is no number in the array which is given
to us, which has any digit in the thousandths place, so we can stop at.
So the number of times we have to keep doing is till the largest place in any of the numbers, which
is given in the array.
And you can see that that's the hundredths place over here.
So that's why we had to keep doing it till the hundredths place.
Now why does this work.
We can see that initially when we sorted the numbers based on their ones place, we got this over here.
All right.
Now after this, when we sorted the numbers based on their tenths place, you can see that whatever
was wrong over here with respect to the tenths place gets rectified over here.
Right.
For example, you can see 123 is ahead of zero five.
But that is changed because now you have zero over here and then you have two over here.
Right.
And then again you have 63 over here.
And then you have five.
So this is also rectified over here.
Right.
Because you have six over here and zero over here.
And then finally whatever is wrong over here is rectified by sorting based on the hundredths place.
So 123 came last.
So we shifted its position to the last.
And then this works because if there is a tie the initial ordering is maintained.
So that's the important thing over here.
Now for example notice that we have five and 19 over here.
And we have zero in both the cases in their hundredths place.
And when we sorted based on the hundredths place, we did not change their relative positioning.
So we maintained it.
So you can see that we maintained it.
So if nothing is there any way it's.
Going to be just zero over here and we are maintaining the previous order.
So that's why this is working.
And you can note that maintaining the previous relative positions in case of a tie is a very important
thing to have the radix sort work.
And that's why we will see later.
That's that's the reason that's one of the reasons why we are why we will use counting sort to implement
radix sort.
Again.
We will see that in part two and part three.
Now let's proceed now again just to mention over here to get to this.
That is to sort based on one's digits and ten's digits and hundreds digits, digits.
We will use counting sort.
And we will see that in the latter part of this section.
Again, one more reason why this is being done is that this has good time complexity, the counting
sort.
And this is stable.
And with stable, we mean that in the case of a tie, as in what we have seen over here or over here,
the initial relative ordering is maintained.
All right.
So we are done with step one.
We have developed an intuition on how radix sort works.
So it's not actually going to compare the values of two numbers.
Rather what we are doing is we are going to take first only the units digits and then sort the numbers
based on those digits, then the tens, digits, etc..
So this is how radix sort works.
Now let's go ahead and try to understand how counting sort works.
And then in part three we will use counting sort to implement radix sort.
So let's get started with part two.
All right.
Now we are going to learn the counting sort.
Now we know that for any good sorting algorithm, the time complexity is of the order of n log n.
Now this is the fastest we can sort when we know nothing about the input.
All right.
Now again this is this, this time complexity is achieved which is the best possible in the case of
comparison based sorting.
Now to do better than this we have the counting sort.
And the counting sort is not a comparison based sorting.
All right.
Now let's see how we can do this.
And again the reason why we are attempting this is to do better than o of n log n.
And this is possible when we know something about the input.
Now, in the case where we know nothing about the input, we cannot do better than O of n log n.
But in the case where we know or we have some info about the input, let's see how we can make use of
this information to do better.
The reason why we can use counting sort is because we have some information about the input.
And this information which we have is that the numbers will lie between zero and k.
And what is this?
Why is this so?
Because we are taking only the digits, right?
First we are just taking the digits in the units place, then in the tens, place, etc. now digits
can only lie between 0 and 9, right?
So we know that every digit is going to be between 0 and 9 and both of them included.
So this is what we know about the input.
And we will make use of this information to implement the counting sort.
So let's go ahead and see how we can do this.
Now let's say this is the array which is given to us.
All right.
So this is the input array.
And over here let's say each element lies in the range between 0 and 9.
Now again tying this back to the radix sort.
Remember we are only sorting first for based on what is there in the units place.
So that's just one digit, right?
Even though the number may be something like 123 for example.
And let's say 123, 45, 67, etc. when we only take the units digit, this becomes equivalent to three,
this is five and then this is seven.
Now the position of 123 is just determined by what is there in the units digit.
So that's why we can neglect this.
And we are only focusing on the units digit.
So what we have on the units digit, for example, when we are dealing with the part where we sort on
the basis of the units digit.
So in that case we can say that each integer is represented by one digit, and that will lie in the
range of 0 to 9.
Now let's take an example.
Let's say we have 12345678.
Let's say we have eight numbers to sort.
And let's say we are just considering their digit, right.
One digit at a time.
So let's say the digits are seven, five three, zero, one, three, seven and eight.
Now let's try to keep this apart for a moment, and we will come back and see how we can implement or
make use of the counting sort.
In the case of radix sort.
But over here, let's first try to understand how counting sort is able to sort these numbers.
So let's say these are the numbers which are given to us, which is seven, five three, zero, one,
three, seven and eight.
So you can see there are eight numbers.
Now how do we use counting sort to sort them.
So for this first we will have an auxiliary array.
All right.
And these will have the indices from 0 to 9.
Because we know that the elements or the digits which are there over here can only be in the range of
0 to 9.
So that's why we have the indices 0 to 9 over here.
Now what we will do is we will just loop through the array which is given to us, which is 75301378.
And then whenever we encounter a particular number, we will increment the value in that particular
index.
So for example let's say everything is zero at this point.
All right.
And then when we come to seven we will change that to one.
And when we come to five this also will change to one.
And when we see the second seven this will go to two.
So we are basically so we are just taking the number of times these integers are occurring in this array
which is given to us.
So once we go through the array we will see this right.
We can see that zero is occurring.
Once you can see one is occurring one time and then two is occurring.
Zero times three is occurring twice once here and once here four is occurring.
Zero times five is occurring once six is occurring.
Zero times seven is occurring.
Two times eight is eight is occurring once and nine is not occurring.
So this is what we get now after we have this frequency array over here.
What we will do is we will go ahead and take the cumulative sum.
All right.
So what is the cumulative sum.
We are just going to add these up as we go from left to right.
So in position zero we just have what is there which is one itself.
But at index one we will have the sum of what is there at index zero and at index one.
So one plus one gives two over here.
Similarly at index two we will have this zero plus this two.
All right.
So that gives us two again.
Now at index three we will have this two plus this two which is equal to four.
And similarly at index four we will have four plus zero which is four.
At index five we will have this four plus one which is equal to five.
And in the next position also we will have five because over here we have zero.
And over here we have five.
So we are adding these up.
We are getting five over here.
Then five plus two.
That gives us seven over here.
Similarly seven plus one gives us eight and eight plus zero gives us eight.
So this is the cumulative sum that we have.
All right.
Now we need one more array which is the output array.
The output array is going to have an equal number of elements as the input array.
So over here we have seen it has eight elements right.
So the output array is also going to have eight elements.
So this is our output array.
And let's just say the indices are from 0 to 7.
All right.
So this is the output array.
Now what we will do is we will go backwards.
That is we will start at the end of the given array or the input array.
And we will go backwards.
So we will see why.
This is why we do it in this manner again.
This is useful to maintain the stability or the relative ordering.
So we will see that soon.
Why we do that now for for the moment, let's just go with the algorithm and let's try to understand
how it works.
Now first we take eight.
All right.
We take this value eight.
Now we have to decide where should we keep this eight in the output array.
All right.
Now to identify the position where this has to be inserted in the output array, we will take a look
at the cumulative sum array which we have over here.
And we will take this index over here which is eight.
So we will take a look at this eight over here.
Now at this position eight the value is equal to eight which is this eight inside.
All right.
Now what does this mean.
This eight over here means that there are eight elements which are less than or equal to the value eight
in the array which is given to us.
All right.
So that's the meaning of this.
So if there are eight elements which are less than or equal to eight, then we have to insert it in
in a manner such that this is true.
Right.
So what we will do is we will subtract one from this.
So eight minus one gives us seven.
And we will insert this value eight at index seven.
So that's going to be over here.
This is index seven in the output array.
So we will insert this eight at index seven which is over here.
Now when we do this you can see that this eight has eight elements less than eight.
Right.
So this is the eight over here you can see 12345678.
So there are indeed eight elements less than or equal to this eight.
So that's why we have that's why we have inserted it at seven.
And again we have subtracted one over here because you can see this is zero index right.
So it's starting at zero.
That's why we subtract one.
So we get seven and we insert the value eight which is this one over here at index seven.
This seven over here.
And then let's continue.
What we will do is we will go ahead and take the next value which is seven.
So over here we have seven.
All right now.
You can see we have we have seven.
Let me just circle this.
So we have seven over here.
Now what we will do again, we will come to the cumulative sum array.
And we will take a look at what is there at index seven.
Now at index seven we have seven.
All right.
So this means that there are seven elements which are less than or equal to seven in the array.
All right.
So when when it is sorted so what we will do we will take this value.
We will decrement it by one.
Again.
Why is that so.
Because it's zero index.
We get the value six.
And we are going to insert this seven over here at index six.
All right.
So this is index six.
So let's insert it over here.
Now when we insert it we have seven over here.
Now you can see there are seven elements which are less than or equal to this seven.
One.
Two three.
Four.
Five.
Six.
Seven.
That's why we have inserted it over here.
Again we proceed.
We take the next element which is three.
Now for identifying where to insert this three in the output array we will take a look at index three
in the cumulative sum array which is over here right.
So we have three over here at index three the value is four which means that there are four values four
elements which are less than or equal to three in the output array, which is which is the case when
the values are sorted.
So to find where to insert this particular three, we will decrement this four by one.
So we get three over here and we will insert this three at index three which is over here.
So let's go ahead and insert it.
So we have three over here.
And you can see you have 123 and four four elements which are less than or equal to three in the output
array.
Again we proceed.
We take one over here.
So we take one.
Now we have to decide where to insert one in the output array.
So again we will take a look at the cumulative sum array.
At index one the value is equal to two which means that there are two elements less than or equal to
one in the output array.
Now to know where to insert this one, we will take this value and decrement it by one.
So we get one over here.
And we are going to insert this value at index one which is over here.
So let's go ahead and write one over here.
And we have one over here.
And you can see you have two elements less than or equal to one.
This is the element one.
And this is element two.
So two elements less than or equal to one.
Let's proceed.
We go to the next element which is zero.
And now we have to decide where to insert it in our output array.
So again we take a look at the cumulative sum array.
And we take a look at index zero.
And we decrement the value by one.
So we get zero.
And we're going to insert this zero at index zero.
So you can see there is one element which is less than or equal to zero in the output array which is
this element itself.
Again notice it's less than or equal to.
Now let's again proceed.
So we come to the next element which is three.
Now we have to decide where to insert this three this three in the output array.
Now for this we take a look at the cumulative sum array at index three the value is three.
So we are going to decrease this by one.
And we get two.
And we are going to insert this three at index two which is over here.
So let's go ahead and insert it.
So we get three over here.
And you can see you have two.
You have three elements.
This was three right.
You have three elements one two and three which is less than or equal to this three over here.
Now again let's proceed.
We go to the next element which is five.
Now we have to decide where to insert this five in the output array.
So we're going to check over here five at index five.
In the cumulative sum array the value is five.
We decrement it by one we get four.
And we are going to insert this five at index four in the output array which is over here.
So this is index four.
So let's insert five over here.
Again we proceed.
We come to the next element which is seven.
And we check index seven in the cumulative sum array which is over here.
And we're going to decrement this six by one.
So this becomes five.
And we are going to insert this seven at index five which is over here right.
So that's over here.
So let's insert seven over here.
And yes you can see the elements.
The digits over here are now sorted.
So this is how the cumulative sort works.
All right.
Now let's take a look at an interesting property about the counting sort.
Now the counting sort is stable.
All right.
So that's a very important property.
Now what do we mean with this.
All right.
So let's try to understand what do we mean with this.
Now again this is why this is the main reason why we go in this direction.
Once we have created the cumulative sum and then decide where to insert it.
So let's try to understand why.
Let's take a look at the threes.
We have two threes over here.
So this is one three and this is the other three.
So these are actually equal in value.
But if you take a look at their positioning in the output array you can see that their relative positioning
is maintained.
That is this this pink three is coming before the violet three in the input array.
And you can see in the output array.
Also the pink three is coming ahead of the violet three.
So if there is a tie that's what we mean with stable.
If there is a tie between values the initial relative ordering is maintained.
So that is why we are going in this direction right.
So we encounter this three first.
So that's why we are inserting it over here.
Now if we had gone in this direction then we would have inserted this three at this position.
And in that case it would not be stable.
So that is the reason why we move in this direction.
All right.
Finally, when we are filling the output array and the reason why we can use counting sort for radix
sort is because counting sort is stable.
And again stable means in the case of a tie the initial relative ordering is maintained.
All right.
So we have got a good understanding about how the counting sort works.
And we have seen how to sort numbers where we just had one digit.
Right.
So all the integers which was given to us in this in the input array.
Just add one digit.
So this is going to be used when we implement radix sort.
Now before we go ahead and see how we can use the counting sort in the case of implementing radix sort,
let's take a look at the complexity analysis of the counting sort.
Now what is going to take time?
First let's take a look at the time complexity.
What all things over here is going to take time.
Now over here you can see we have to loop through the input array and identify the frequencies.
That's this step over here right.
So that's going to be an O of N operation because why is that.
So n is the number of elements in the input array.
Right.
So we have to go through the input array or iterate through the input array to be able to understand
how many times each element is occurring.
And to determine the frequency to fill in this array over here.
So that's an O of n operation.
And then we have to form the cumulative sum array.
For this we have to just go through the array which we have formed over here.
That is going to be an O of k operation.
And again remember k is just the range of the digits right.
So we have initially said that every digit will be in the range of zero to k.
Or it can be 0 to 9.
Right.
So again that's that's that's the k over here.
So this over here is going to be of the order of k.
So looping through the array over here and formulating the cumulative sum array is going to be an O
of k operation.
And then we have the output array over here.
Right.
So we have the output array over here which is again going to be forming.
The output array is going to be an O of n operation because we have to again loop through the input
array to determine.
And then we do some constant time operations to to determine where to insert it to the output array.
So you can see the total time complexity of this solution is going to be of the order of n plus k.
Right.
Because we don't need to write two n plus k because that is the constant.
So we can say the time complexity is of the order of n plus k.
And again the unique values over here is in the range of zero to k.
So that's how we get this k over here.
Now what about the space complexity.
When it comes to space complexity.
Let's try to think what all takes extra space, right?
So there is this array over here which we are forming.
So let me just clean this up a little bit.
All right.
Now we have this array over here right.
So that takes k space.
And then we have this output array which again takes n space.
So this over here takes k space because it's going to have elements of the order of k right.
So it's zero to k.
So we can say there are k plus one elements.
But again that does not matter.
One is just a constant.
So the space that is consumed over here is going to be of the order of K.
And then over here we have the output array which is going to take space of the order of n.
So that's why we can say that the space complexity of the counting sort algorithm is of the order of
n plus k.
All right.
Now again remember if k is uh when when we are dealing with decimal numbers we can just say that k is
ten, right.
Because the values is going to be from 0 to 9.
Right.
So in that case we can say k is equal to ten because we are dealing with base ten.
All right.
Now let's proceed and see how we can use the counting sort to implement radix sort.
And the reason why we are using counting sort to implement radix sort is first that the counting sort
is stable, and secondly, we are trying to get a good time complexity.
All right.
And we have seen the time complexity of the counting sort is O of n plus k.
And if you are just dealing with decimal numbers k is going to be a constant.
So we can just say that counting sort is achieving O of n time complexity, and any other good sort
can not go beyond O of n log n.
All right.
So that's the reason why we are using counting sort.
Now let's proceed.
And let's see, let's say the numbers which we have to sort are these which is three 8473, 374, one
8365, 247 and 185.
Now what we will do is, as we have seen in part one, we are only going to take the units digits over
here, which is four, three, four and three, five, seven and five.
Now we are going to sort these numbers based on their units digit.
So that's how we are going to do this.
Now for sorting the numbers based on their units digits we are going to use counting sort.
So let's again trace the algorithm.
So over here I have an array with indices from 0 to 9.
Because we know that because this is in decimal system, every digit in the units digit in the units
place can only be among 0 to 9.
So that's why I have this array with the indices from 0 to 9.
All right.
Now let's go ahead and fill in the frequencies.
So you can see that we have two fourths and we have two threes one.
And then we have two fives and one seven.
So this is the frequency.
And then everywhere else we are just going to fill in with zero.
All right.
Now we are going to create the cumulative sum array.
Again it's going to have indexes from 0 to 9.
And then we just fill the cumulative frequencies.
So you can see.
So over here you just have zero.
And then for this value you have to add these two.
So you get zero itself.
Now when we add these two you get value zero itself.
Over here you add these two you get two over here you add these two.
You get four over here for two plus two gives you six.
Six plus zero is six six plus one is seven and seven plus zero is seven and seven plus zero is again
seven.
So that's how we get the cumulative sum array over here.
All right.
Now let me just clean this up.
Now what we will do is we will have our output array over here.
And we are having the indexes over here zero one, two, three, four, five and six.
And then we go bottom up right.
So we start from 185.
So we go in this direction.
We have seen this is important to keep the stability.
Now the first digit over here is five.
Now we have to decide where should we insert 185 in the output array?
Which is this over here right now.
For this we will take a look at the index five.
In the cumulative sum array.
The value over here is six.
So we reduce this by one.
So we get five over here.
And hence we are going to insert 185 at index five.
All right.
So let's do that.
So we get 185 over here.
Now we proceed.
We take the next digit which is seven.
Now for this we have to decide where to insert this 247.
So we take a look at this seven over here.
So the value over here is seven which is reduced by one.
So we get six.
Now we are going to insert 247 at index six which is over here.
Now we proceed to the next digit is five right.
This is five.
So again we take a look at this five.
Over here we decrement this by one.
So we get four.
And this 65 is going to be inserted at index four.
Again we proceed.
So over here we have three.
And we take a look at index three.
So the value is two we subtract by one.
So we get one.
And we are going to insert 183 at index one which is over here.
Now we proceed.
The next value over here is four.
So we take a look at index four which is over here.
Now we decrease the value by one which is three.
So we're going to insert 374 at index three.
Again we proceed.
So over here we have three.
So we are taking a look at index three where the value is one.
So we decrease this.
So we get zero over here.
And hence we are going to insert 73 at index zero.
And then we have 384.
The value over here is four.
So we take a look at index four.
Over here the value is three.
We reduce this by one so we get two.
Hence we are going to insert 384 at index two.
Now you can see we have done one time the counting sort.
Right.
And that's done based on the units digits.
All right.
Now what we will do is we will again sort these numbers based on their ten's digits which is these digits.
Right.
Again we will implement the counting sort for this.
And when we do this the numbers will look like this.
And after this finally we will again implement counting sort on the digits in the hundredths place,
which is what we have over here.
And when we do that again we will get the numbers like this.
And that's the end, right?
So we just had to do it three times because the maximum digit over here is one hundredths place.
And then you can see the numbers are sorted.
We have 6573 183 185 247 374 and 384.
And this is sorted.
So this is how radix sort is implemented.
And you can see that we are using counting sort to implement the radix sort.
And we can implement the counting sort because we know that the value at at the, at a particular place,
whether the units place or the tenths place or the hundredths place, etc., will lie between 0 and
9.
So because we know that we can use the counting sort and we have, we have seen that in the case of
decimal values, this is getting a time complexity of o of n.
Now again, an interesting thing to notice over here is the counting sort works because it's stable.
For example, you can see over here we have 374 and 384.
Now both of them have the hundredths place three.
Right.
So because the counting sort is stable in the case of a tie it will maintain or preserve the previous
order.
So that's why you can see that over here you have 374 before 384.
Because that's the order over here also.
Right.
We have 374 before 384.
Hence the order that is preserved.
Right.
The previous order is preserved.
And over here you can see we have 374 and 384.
All right.
So the counting sort is stable is a stable sort.
And that's why we are using the counting sort for implementing the radix sort.
Now let's take a quick look at the time and space complexity of the radix sort.
Now previously we have seen that in the case of counting sort, the time complexity is O of n plus k
space and time.
Right.
And in the case of decimals that would be o of n plus ten and ten is a constant.
So we can just avoid it.
And we can say it's O of n space and time.
Now let's proceed.
What about radix sort?
What would be its time complexity?
We can see that we have to implement the counting sort d number of times, where d is the maximum number
of digits in any of the uh given numbers in the array.
All right.
So d is the largest number of digits.
So we can say that the time complexity is d times n plus k.
So that's the time complexity.
And again if the base is ten we know that d is just ten.
And that's a constant.
So we can avoid it.
And we can say that the time complexity is O of d into n.
And if we know D like for example, in this case, if we know that d is equal to three, we could even
avoid that.
And we can say that the time complexity is O of n.
But then generally we can just say the time complexity is O of d into n in the case of decimal values.
Now what about the space complexity?
The space complexity is going to be o of n plus k itself, right.
Why is that.
So you can see we consume extra space.
But that is only while doing the counting sort.
So we don't need to keep, uh, keep using that space which is used.
For example we are doing counting sort one time over here.
So we have an extra array.
We have the auxiliary array, the cumulative sum array etc. but then that is no longer required when
we are doing the second counting sort.
So we can free up this space.
So that's why the space complexity of the radix sort and the counting sort is the same, which is O
of n plus k.
And in the case of decimal values we know k is equal to ten.
So we can say that the space complexity over here is also o of n.
So the time complexity is of the order of d into n plus k and.
And the space complexity is of the order of n plus k.
Now, an interesting thing to notice over here is that let's say we increase k right?
Let's say we increase k then d would decrease.
Let's try to understand what this means.
Now for example let's say we have the binary.
Let's say we have the decimal system.
So let's say k is equal to ten because we have the digits from 0 to 9.
Right now if we take into consideration the binary system k is equal to two because we only have zeros
and ones.
Right now if we want to express a number 50.
For example, in the decimal system you can see we are using only two digits.
But if we want to express the same 50 in the binary system, you can see that we would have to use 110010.
So you can see that more digits are used when k is less.
Or you can say when k is increased from 2 to 10 the number of digits is reducing.
Right.
So over here you have 1234566 digits.
But that is reducing to two over here.
So that's why when you increase k d decreases.
Again this is just an interesting observation.
All right.
So over here d was equal to two.
And over here D is equal to six.
Right.
So when you increase k d is getting reduced.
All right.
So that's what we've seen over here.
We have increased it to ten and D is reduced to two.
So basically if you do that so what's the implication on the time and space complexity.
We can see that when we're increasing k the space complexity is increasing right.
Because this is over here this increases.
But then when we increase k d decreases this decreases.
And hence the overall time complexity will reduce.
So it's basically a trade off between time and space.
Whether we have to implement something in a in the binary system or where when, whether we have to
use numbers in the decimal system, etc..
So this is just an interesting observation.
All right.
So if we increase k the space increases.
But in general we have already seen that the time complexity is O of d into n plus k.
And the space complexity is O of n plus k.