Problem of the day
Reverse a given stack of 'N' integers using recursion. You are required to make changes in the input parameter itself.
Note: You are not allowed to use any extra space other than the internal stack space used due to recursion.
Input: [1,2,3,4,5]
Output: [5,4,3,2,1]
The first line of input contains an integer value 'N', denoting the size of the input Stack.
The second line contains 'N' single space-separated integers, denoting the stack elements, where the leftmost integer denotes the TOP element of Stack.
Output Format :
'N' single space-separated integers in a single line, where the leftmost integer denotes the TOP element of the reversed stack.
3
2 1 3
3 1 2
Reverse of a give stack is 3 1 2 where first element becomes last and last becomes first.
2
3 2
2 3
0 <= N <= 10^3
Where 'N' is the number of elements in the given stack.
Time Limit: 1 sec
Use the recursion call stack to store the elements of the stack and reverse it.
We will be using two recursive methods:
Algorithm:
O(N^2), where ‘N’ is the total number of elements in the given stack.
In the worst case, reverseStack method will be called for each element in the stack( requires O(N)) time, and for each call of the reverse stack, we call InsertAtBottom which also takes O(N) time.
O(N), where ‘N’ is the total number of elements in the given stack.
In the worst case, the depth of recursion can extend up to O(N). So, extra space will be required for the recursion stack.