Reverse a Stack using Recursion
Вставка
- Опубліковано 3 жов 2024
- Reverse a Stack in O(1) space using Recursion.
The Notes that I taught in the video and the Working Code (if any) will be available on my Patreon page under the "Notes, Code And Support" tier.
Link: / adityaverma
Video Pdf Notes: / reverse-stack-38641383 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
This IBH is amazing, we dont have to go through the entire recursion, just using base condition and n-1 iteration, and recursion takes care of the rest!!!! Damnnn, seriously recursion does work like magic! Thank you for such brilliant breakdown of recursion, no body teaches anything like these stuff! Kudos
Couldn't agree more! Recursion is magic !! 🤯
@@TheAdityaVerma bro, you're really intelligent, i love how you implemented the abstract idea of "mathemcatical induction" to recursion, just like in mathematical induction in which we just solve for n = 1, and for any n = k, prove n = k+1 is also true so that we dont have to solve for every value between from 1 to k, which is basically what we're doing in your IBH method, for any n = k we just solve for k - 1 and also for the base condition (which is basically the analogy for the n = 1 base condition in mathematical induction concept) so that we dont have to solve for every value between 1 to k (which is what i used to do before in recursion, but now you saved alot of my time through IBH method), you implementation of the mathematical induction idea to real-life application is truly ingenious, you are really smart and a good teacher, subbed.
@@123akash121 bruh everyone into cp knows that tbh, you can read the book "think recursively" which was published in the 80's and same concept is mentioned in it.
@@yuvrajr6491 Thinking Recursively [Roberts 1986-01-17].pdf yahi hai kya?
@@krushnapatil9196 haan bhai
I have gone through these questions and codes about 10 times but until now I have just mugged up the codes. This is the first time I know how recursion works and what's really happening. Thanks a lot for the amazing explanation.Looking forward to backtracking and graph playlist.I think people are eagerly waiting for these two playlists from you.
This is gold...nobody is teaching like this
Sir vo Dp vale playlist mei kuch ques reh gaye the like LIS , substring vgrh k , toh unko plz add kr digiye. And thanks a lot bhaiya
The way you build up the logic for complex problems by first hitting at the head of the easier ones is just MIND-BLOWING! YOU LOOK LIKE A MAGICIAN TO ME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
for the first time I could write my own recursion program :) Thanks a lot for the amazing work. Your teaching style remind me of friend who used to teach all in the early morning before exams.
I did reverse stack using recursion without watching this video. it was somewhat like sort stack and array. previous video helped me to think in this side. Thanks Aditya Appreciate your effort. I wish I could contribute to petreon.
yeah only diff is in sort stack inside insert function we check one extra condition s.top
I was going through each video one by one and implementing it alongside..
the moment I listened to the problem, I was able to create the solution out of it, and it worked in the first go itself.
Reason - he teaches you how to think around the problem...not only the solution.
Thanks, @Aditya Verma..kudos to you!
Exactly that's why I prefer his videos .
Finally, At the middle of this video i myself found the base case for the reverse and insert function even after you forgot to mention that which you gave later in the video of course.
Thank you bhaiya for this recursion series. 🙏
thank you, i watched your previous videos from playlist and i was able to attempt this one without any difficulty, thanks a lot.
You are making our lives easy
I have watched many videos of recursion but did not understood the concept till I watched yours. Thanks for your support
Man! The foundation you've built with the previous videos is so good that I didn't even have to watch this video before figuring out the solution!
//Method to insert the popped element at the beginning
const insert = (stack, element) =>{
// Base Condition
if(stack.length === 0){
stack.push(element);
return;
}
let top = stack.pop();
insert(stack, element);
stack.push(top);
}
// Method to reverse the stack
const reverse = (stack) => {
//Base Condition
if(stack.length === 1){
return;
}
let top = stack.pop();
reverse(stack);
insert(stack, top);
}
Was able to solve it by my own , thank you sir , you are providing Gold.
😭😭😭😭bhai aapki wajh se mai rcursion ke problem khud se solve kar paa rha hu aap god ho sach mai
brother hats off to you, your content, your methods can't deny recursion works like magic !!!
Recursion is like god, if we believe in it and do the right things, then we will get the desired output : )
Magical ✨
🤣🤣
Solved this question without seeing your video, that's the power of your teaching 🔥
ok bhai
so basically in induction we define the structure of code . RIght?
Did this on my own for the very first time . thanks brother .😁
Your explanation very simple 😊😊
Thanks a lot sir!!
You really made the recursion too simple... Before watching your videos I was not able to code recursive solutions..and now I can easily do it.. also I enjoy solving problems using Recursion.
Thanks a lot again!
solved the question without watching the video. You made the concept so clear in previous videos .Thanks a lot
First recursion code that i wrote myself. Thanks alotttt
Bhaiya u explained recursion so well.
I got the core idea of solving problems using recursion just by watching this lecture.
Man you are a terrific teacher.
Thank you for this amazing content.
aisa Khatarnaak confidence aaya hai na RECURRSION me ki pucho mat:) Thanks
Recursion will never be the same for me. Thanks Aditya Verma!
You have realized us that recursion is almost a magic
Great teaching style
Thank u a lot sir for sharing your knowledge and tricks. Best ever explanation video on recursion👍
If Recursion is Magic then you are the Magician !!!
exactly....
Man, you are amazing, thanks a lot!
great explanation. Thanks
Big thank for this recursion series ....finally i can think how to write recursive code....
@Aditya Verma
Please add time complexity at the end of each problem bro. It'll be useful for those struggling with time complexity
yeah
what is the time and space complexity of this algo?
@@ashutoshkumarjha9500 N2
There's an easy way to achieve this in python:
def rev(arr):
if len(arr)==0:
return
last=arr[-1]
arr.pop()
rev(arr)
arr.insert(0,last)
arr=[1,2,3,4]
rev(arr)
print(arr)
thanks
Yeah, but you can't simply insert like that in a stack. You need to pop all the elements to insert at the 0th index (Even I did the same before watching the video but realized after watching the induction step :D )
This has to be the right code
arr = [10,5,-2,89,7,54]
class recursion:
def insert(self,arr,val):
if len(arr)==0:
arr.append(val)
return
temp = arr.pop()
self.insert(arr,val)
arr.append(temp)
def reverse(self,arr):
if len(arr)==1:
return
val = arr.pop()
self.reverse(arr)
self.insert(arr,val)
return arr
obj = recursion()
print(obj.reverse(arr))
pls know what stack is and then code
@@suryavamsikodeti254 i think you can insert in same recursive function reverse with push only.....
Sir You are just great this method works like butter smooth i am just reading topic of video and able to solve for last 3 video and then i watch video at 2x to see if i could have just changed some part of code to make it better. Thanks Sir Again...
never understood recursion like this, hatsoff to u sir
You are great teacher, awesome recursion playlist
I am going to miss the pen tricks that you used to do
I still do those trick, they are just not visible now 😓
@@TheAdityaVerma please use pen and copy
@@itsvinayak jab bahi ye pen paper se smajhta tha tab bahut acche se samajh mai aatta tha ab to ghanta kuch samjh nhi aata
@@akhilkumarsingh5041 In some videos he speaks too fast. On the digital pad, you do not know where he will start writing next - it is a bit disconcerting, and it also loses the human/personal touch. Plus, the topic takes a while to understand -- it may be helpful to go over the series one more time and take notes by pausing the video while he is talking. Earlier, it was easy when he summed up the video by going over the whole code, but now you don't have the whole code in front of you!
@@0anant0 I can feel u bro. Now it feels like online classes
void reverse(Stack stk ){
if(stk.size()==1)
return;
int temp=stk.pop();
reverse(stk);
pushInStack(stk,temp);
}
void pushInStack(Stack stk, int temp){
if(stk.size()==0){
stk.push(temp);
return;
}else{
int value=stk.pop();
pushInStack(stk,temp);
stk.push(value);
return;
}
}
Nice code! It would be even more easier to understand if you had renamed 'pushInStack' to something like 'push at bottom of stack' (bcoz push is normally done at top in a stack), also 'value' as 'top', temp = top for reverse(), temp = cur elem/key, etc. for the other fn. Just my rant... :-)
Bro else is not needed in pushInStack function. Becoz u returned in the if condition. Just write whatever is inside the else but without else, it will work the same
Time complexity =O(n^2)??
code for reversing a stack and sort a stack are same?
@@prakharnegi1081 yes except for the base condition where we compare temp value to top of stack in while sorting a stack.
Thnx Bhaiya for such competitive coding..Helping me a lot in competitive coding
Bhiya maine aapki sirf 2 video dekhi and I am able to solve questions myself till now lots of love 💫
Bro You are God,Thank you very much for the Video;
Best video on the internet....Recursion seems like cake walk indeed(until this part atleast)
I don't really comment but like damn, i was compelled to. I was trying to figure out the recursive solution for like 10 mins and then thought to watch this video of yours to get a hint and oh boy, did I get one. Literally 4 minutes into the video, something clicked, i paused it and boom, solution accepted. A lot of ytbers cover these solutions but the ability to make these so intuitive is rarely observed. Thanks a ton man.
P.S: Just realised you are the DP series guy :)
Thankyou very much sir you made recursion cake walk!!
Bhiaya aap super master ho ..pata nahi ab aap es chanel pr active ho ya nahi ....thank you so much ..the way you explain the question and concept it becomes like "chutny" ....you are khan sir for us
static void reverse(Stack s){
if(s.size()==1)
return;
int val=s.pop();
reverse(s);
swap(s,val);
return;
}
static void swap(Stack s,int temp){
if(s.size()==0){
s.push(temp);
return;
}
int val=s.pop();
swap(s,temp);
s.push(val);
return;
}
Thankyou so much, great explanation 👏👏👏👏
Awesome style of teaching. Sir can u please upload series on graph theory. Please and thanks a lot for teaching us.
Confused that recursion is magic or their is magic in your teaching. I have unlocked another view of recursion . Thanks. ❤❤
Thanks brother now i am pretty comfortable in recursion✌🙂
Nice explanation sir
Sir I dis these question by myself tysm for Understanding the concept.
Bhai
Your videos are simply gold
Finallllyyyy
Mene code khud se likha
Aur maja aya recursion padh ke
This is fun!!! Thank you Aditya!
#include
using namespace std;
void insert(stack &s, int temp)
{
// base condition
if (s.size() == 0)
{
s.push(temp);
return;
}
// hypothesis
int x = s.top();
s.pop();
insert(s, temp);
// induction
s.push(x);
}
void reverse_Stack(stack &s)
{
// base condition
if (s.size() == 1)
{
return;
}
// hypothesis
int temp;
temp = s.top();
s.pop();
reverse_Stack(s);
// induction
insert(s, temp);
}
int main()
{
stack s;
int n;
cout > n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s.push(x);
}
reverse_Stack(s);
for (int i = 0; i < n; i++)
{
cout
Thankyou bhaiyaaa
Instead of using a seperate stack and increasing auxilary space we used temp variable at each call frame which is also part of call stack at the end. this is one hell of a trick.
The Game is Back........Thanks Bro .....Bhai Backtracking ki bhi video banaiye please....
aap bahut acha padhate ho sir agar aap graph aur tree v padhaye hote to itne sare edtech startup na huye hote bhaiya
Thank you bhaiya for such a great and simple explanation :)
@Aditya Verma Yes....but we can't say that this algorithm take O(1) space. It's indeed works in O(n) space.
Ignoring the internal call stack space bro*
Okay, so, I have read in some Leetcode solution that, there are two types of solutions when it comes to space complexity:
1. Constant Space solution: No recursive stack used. No extra data structure used. Nothing.
2. In-place Solution: Here, we cannot explicitly take extra space using some data structure, but we can make use of recursion.
And that's what he did here. The solution is in place as it doesn't allocate any extra space explicitly. But yes, it is not a constant space. And if it is about interviews, then, the interviewer is many times, pretty happy with such kind of intuitive solutions.
Nicely explained
sir u r best aapki apporach ache se smjh aati hai aap dry run krte ho ek ek ko phr aage code bhot sahi hai sir plzzzz sir dp graph bst tree sabki sari question batao
Python solution:
def insert_s(s,t):
if len(s)==0:
s.append(t)
return
temp=s.pop()
insert_s(s,t)
s.append(temp)
def reverse_stack(s):
if len(s)
Bhai Graphs par bhi bano do ek playlist , bohot help hoga !! 🙏🙏
i think base condition should be if(s.size()==0) then return; otherwise first element will not be reversed
Auxillary space complexity is O(n) as mentioned.
I have seen all your previous videos , pen and paper mode was better as you used to share a copy of the already written code to explain the discussed problem that was way better as the concepts and code was registered parallel. Your videos are amazing.
Thank you sir ji
Thank you bhya for uploading new videos 😊😊
def reverse(stk,n,op):
if n==0:
return
t=stk.pop()
op.append(t)
reverse(stk,n-1,op)
return op
stk=[1,2,3,4,5]
op=[]
n=len(stk)
print(reverse(stk,n,op))
Thank you bro... you are really awesome
it will be very helpful if you post the question link also.
Thanks for starting to make the videos again! Much awaited! Bas ek suggestion.
Intro aur Outro music ki link har ek video description mein Credits kehke daal do bhai. YT fucks with honest creators every now n then, if there is copyright violation. Don’t want all this hard work to be taken down unnecessarily!
Thanks for being so considerate brother !! But the music I used is "no copyright music" 😅 So cheers !!
@@TheAdityaVerma Great work!! Keep em coming!
AMAZING!! Can you please also explain reversing a linked list using recursion too!
Python Solution-
class Solving:
def insert(self,arr,ele):
if len(arr)==0:
arr.append(ele)
return
temp=arr.pop()
self.insert(arr,ele)
arr.append(temp)
def solve(self,arr):
if len(arr)==1:
return arr
temp=arr.pop()
self.solve(arr)
self.insert(arr,temp)
return arr
lst=[1,2,3,4,5,6]
obj=Solving()
print(obj.solve(lst))
Thanks @Aditya_Verma
Great explanation bro 👍👏😊
I liked your content that's why liked the video ... Subscribed the channel : )
class Solution:
def solve(self,arr,l,h):
if l
sir please make videos on backtacking and greedy approach...and nobody teaches like u...respect
using iteration time- O(n) space- O(n)
recursion time- O(n^2) space- O(1)
Thanks for such a detailed explanation ...Which Digital pen and software you are using for drawing?? Please suggest I am planning to buy one for me.
we can do this without insert function just by directly push(temp) in place of calling insert function as stack is lifo type , therefore when we push it goes to the bottom.
No you cannot, if you push the element which you removed, it will get pushed back to the top itself, when you write the insert function, you are essentially popping all elements of a the stack and store them, push the temp element and push all other values on top of it.
2 pointer and graph
Recursion also takes stack memory so basically it is taking o(n) space ??
Yes
Thats what I have mentioned in the video, we are not allocating memory explicitly. That's the call stack memory getting allocated internally. So we can consider it to O(1).
bhai trees pr vdos bna do plss!!
Jab pehli baar reverse function call karne pr reverse hogaya tha stack... toh recursion ki kya zarurat hai?
void insert(stack &s, int temp)
{
// base condition
if (s.size() == 0)
{
s.push(temp);
return;
}
// hypothesis
int x = s.top();
s.pop();
insert(s, temp);
// induction
s.push(x);
}
void reverse_Stack(stack &s)
{
// base condition
if (s.size() == 1)
{
return;
}
// hypothesis
int temp;
temp = s.top();
s.pop();
reverse_Stack(s);
// induction
insert(s, temp);
}
Kya padhaye ho sir ... Awesome breakdown of recursion
element aur nikalke rkhne wala element dono same h ky?
recursion is a magic
thank you sir
//Code For GFG-Reverse a Stack
void pushElem(stack &s, int elem){
if(s.size()==0){
s.push(elem);
return;
}
int val=s.top();
s.pop();
pushElem(s, elem);
s.push(val);
}
void Reverse(stack &St){
if(St.size()==1) return;
int temp=St.top();
St.pop();
Reverse(St);
pushElem(St, temp);
return;
}
u r an angel!!!
ye O(1) space nahi O(N) hi hai kyunki recursion mein har baar hum ek variable bana rahe hain temp jo total N baar banega
legend of dp
void reverse(stack s)
{
if(s.empty()) return;
int top_element = s.top();
s.pop();
reverse(s);
s.push(top_element);
}
Does this reverse in O(1) space ?
Super bro
private static void reverse(Stack stack) {
if (stack.size() == 0) {
return;
}
Integer temp = stack.pop();
reverse(stack);
insert(stack, temp);
}
private static void insert(Stack stack, Integer temp) {
if (stack.isEmpty()) {
stack.push(temp);
return;
}
Integer val = stack.pop();
insert(stack, temp);
stack.push(val);
}