Sort Stack

Easy
0/40
Average time to solve is 20m
profile
Contributed by
36 upvotes
Asked in companies
MicrosoftIBMGoldman Sachs

Problem statement

You are given a stack ‘S’. Your task is to sort the sack recursively.


Note: 
Looping through the stack is not allowed.
You need to return a stack that is sorted in descending order.


For example: 
Given stack S = 1 3 2 
The output will be 3 2 1 since it is the sorted order.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.
The second line of each test case contains a single integer ‘N’, denoting the stack size.
The next line contains ‘N’ space-separated integers denoting the elements of the stack, the last element of the input being the top of the stack.

If the input is 1 3 2 then the input stack will look like this :

Output format : 
For each test case, print the stack in descending sorted order.

The output of each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
2
4
1 0 0 2 
3 
2 4 2
Sample Output 1 :
2 1 0 0
4 4 2
Explanation of the Sample Input 1:
For the first test case:
For the given stack, the resultant sorted stack would be 0 0 1 2.  

For the second test case:
For the given stack, the resulting sorted stack would be 2 2 4.
Sample Input 2 :
2
4
1 2 3 4     
3    
5 1 2
Sample Output 2 :
4 3 2 1 
5 2 1
Constraints:
1 <= T <= 5
1 <=  N <= 2000
0 <= S[i] <= 1000

Where ‘T’ is the total number of test cases, and 'N’ is the size of the stack, and 'S[i]' is the element of the stack.
Hint

Use recursion? 

Approaches (1)
Recursion

The main idea is to remove the elements recursively from the stack until the stack becomes empty and then insert those values (from the call-stack  [A call-stack is the stack that is made in the memory when recursive-calls are made. ]), back into the stack in a sorted position.

  • In each call, remove the top element from the stack.

 

  • Make a recursive call to the function sortStack.

 

  • After the call, insert the element in the stack in a sorted fashion.

 

  • This can be done by removing the top element from the stack until the topmost element is greater than the current element that we want to insert.

 

Time Complexity

O( N ^ 2 ), where N is the size of the stack.

 

We are going through the stack once and for each element we may have to empty the stack that takes O(N) time. Hence, the overall time complexity will be O(N ^ 2). 

Space Complexity

O( N ), where N is the size of the stack.

 

Since we are using recursion, hence N call-stacks would be made. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Sort Stack
Full screen
Console