Sort a Stack

Easy
0/40
Average time to solve is 10m
profile
Contributed by
454 upvotes
Asked in companies
IBMGoldman SachsAmazon

Problem statement

You’re given a stack consisting of 'N' integers. Your task is to sort this stack in descending order using recursion.

We can only use the following functions on this stack S.

is_empty(S) : Tests whether stack is empty or not.
push(S) : Adds a new element to the stack.
pop(S) : Removes top element from the stack.
top(S) : Returns value of the top element. Note that this function does not remove elements from the stack.
Note :
1) Use of any loop constructs like while, for..etc is not allowed. 
2) The stack may contain duplicate integers.
3) The stack may contain any integer i.e it may either be negative, positive or zero.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow.

The first line of each test case contains an integer 'N', the number of elements in the stack.

The second line of each test contains 'N' space separated integers.
Output Format:
The only line of output of each test case should contain 'N' space separated integers denoting the stack in a sorted order.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function. 
Constraints:
1 <= 'T' <= 100
1 <=  'N' <= 100
1 <= |'V'| <= 10^9

Where |V| denotes the absolute value of any stack element.

Time limit: 1 sec
Sample Input 1:
1
5
5 -2 9 -7 3
Sample Output 1:
9 5 3 -2 -7
Explanation of Sample Input 1:
9 Is the largest element, hence it’s present at the top. Similarly 5>3, 3>-2 and -7 being the smallest element is present at the last. 
Sample Input 2:
1
5
-3 14 18 -5 30
Sample Output 2:
30 18 14 -3 -5
Explanation of Sample Input 2:
30 is the largest element, hence it’s present at the top. Similarly, 18>14, 14>-3 and -5 being the smallest element is present at the last. 
Hint

Try to think how you can sort the stack considering you can only access the top element of the stack.

Approaches (1)
Recursive approach

The idea of the solution is very simple. 

  • First, we will hold all values in a Call Stack until the stack becomes empty.
  • When the stack becomes empty, insert all held items one by one(from the call stack) in sorted order.
  • We will do this by using a function sortedInsert() which will sort these elements.
  • In the sortedInsert() function we will first check if the stack is empty and if the current element is greater than the top element of the stack, if these conditions are met then we push that current element to the stack.
  • Then we pop the top element of the stack and again recursively call the stack with the remaining elements.
  • Now we push the earlier top element which we popped in step 5 back into the stack.
  • Finally, we will print our sorted stack.
  • Let us understand this with the help of an example.
    • Consider we have the following stack.
      • 5 <- top of the stack
      • -2
      • 9
      • -7
      • 3
    • First, we will pop all the elements of the stack. After popping, the call stack frame looks like:
      • 5 <- stack frame #1
      • -2 <- stack frame #2
      • 9 <- stack frame #3
      • -7 <- stack frame #4
      • 3 <- stack frame #5
    • Now our stack is empty and sortedInsert() function is called. It inserts 3(from stack frame #5) the bottom of the stack.
      • 3 <- Top of the stack
    • Now next element i.e. -7 (from stack frame #4) is picked. Since -7 <3, -7 is inserted at the bottom of the stack. Now stack becomes:
      • 3 <- Top of the stack
      • -7
    • Now next element i.e. 9 (from stack frame #3) is picked. Since 9 is not smaller than any current value in the stack, it is inserted at the top of the stack. Now stack becomes:
      • 9 <- Top of the stack
      • 3
      • -7
    • Now next element i.e. -2 (from stack frame #2) is picked. Since -2 <3, -2 is inserted below 3. Now stack becomes:
      • 9 <- Top of the stack
      • 3
      • -2
      • -7
    • Now the final element i.e. 5  (from stack frame #1) is picked. Since 5 <9, 5 is inserted below 9. Now, stack finally becomes:
      • 9 <- Top of the stack
      • 5
      • 3
      • -2
      • -7
Time Complexity

O(N^2), where N is the number of elements in the stack. 

 

In the worst case for every sortStack(), sortedInsert() is called for ‘N’ times recursively for putting element to the right place

Space Complexity

O(N), where N is the number of elements in the stack.

 

This is the space used by the stack data structure to store the elements. 

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Sort a Stack
All tags
Sort by
Search icon

Interview problems

Easiest Solution in java..

import java.util.* ;

import java.io.*;

public class Solution {

 

public static void sortStack(Stack<Integer> stack) {

// Write your code here.

ArrayList<Integer> arr = new ArrayList<>();

while(!stack.isEmpty()){

arr.add(stack.pop());

}

Collections.sort(arr);

for(int i=0;i<arr.size();i++){

stack.push(arr.get(i));

}

}

 

}

1 view
0 replies
0 upvotes

Interview problems

easy solution in c++

#include <bits/stdc++.h> 

void sortedInsert(stack<int> &stack,int num){

    //base case

    if(stack.empty() || (!stack.empty() && stack.top()<num)){

        stack.push(num);

        return;

    }

    int n=stack.top();

    stack.pop();

    sortedInsert(stack,num);

    stack.push(n);

}

void sortStack(stack<int> &stack)

{

    //base case

    if(stack.empty()){

        return;

    }

    int num=stack.top();

    stack.pop();

    sortStack(stack);

    sortedInsert(stack,num);

}

36 views
0 replies
0 upvotes

Interview problems

C++ || with comments

#include <bits/stdc++.h> 
//Maintain vars in Recursive stackspace;
//sort while inserting each element (having its own stack space)
// O(n^2)
void ins(stack<int> &st, int el){
	
	if(st.empty() || st.top() < el){
		st.push(el); //fixed els position
		return;
	}

	int e = st.top();
	st.pop(); 

	ins(st,el);

	st.push(e);
}
void sortStack(stack<int> &stack)
{
	// Write your code here
	if(stack.empty()){
		return;
	}
	//maintaining el in stack space
	int el =  stack.top();
	stack.pop();

	sortStack(stack);
	//fixing each elements position in sorted order;
	ins(stack,el);
}
27 views
0 replies
0 upvotes

Interview problems

Sort a Stack #cpp

#include <bits/stdc++.h>

void sortInsert(stack<int> &st, int num) {
	if(st.empty() || st.top() < num){
		st.push(num);
		return;
	}

	int x = st.top();
	st.pop();

	// Recursive call
	sortInsert(st, num);

	st.push(x);
}

void sortStack(stack<int> &stack)
{
	// Write your code here
	if(stack.empty()){
		return;
	}

	int num = stack.top();
	stack.pop();

	// recursive call
	sortStack(stack);

	sortInsert(stack, num);
}

programming

datastructures

240 views
0 replies
1 upvote

Interview problems

One line Python solution

from os import *
from sys import *
from collections import *
from math import *

def sortStack(stack):
    stack.sort()

python

103 views
0 replies
1 upvote

Interview problems

Easy C++ solution:

#include <bits/stdc++.h> 

void insertatposition(stack<int> &s, int x){

    if(s.empty()){

        s.push(x);

        return;

    }

    if(s.top() < x){

        s.push(x);

        return;

    }

    int a = s.top();

    s.pop();

    insertatposition(s, x);

    s.push(a);

    

}

void insert(stack<int> &stack, int x){

    if(stack.empty() == true || stack.top() <= x){

        stack.push(x);

        return;

    }

    else{

        insertatposition(stack, x);

    }

}

void sortStack(stack<int> &stack)

{

    //base case

    if(stack.empty()){

        return;

    }

    int temp = stack.top();

    stack.pop();

    sortStack(stack);

    insert(stack, temp);

}

294 views
0 replies
0 upvotes

Interview problems

Java Solution

class Solution {    // Function to return a list containing the intersection of two arrays.    static ArrayList<Integer> printIntersection(int arr1[], int arr2[]) {        // add your code here        ArrayList<Integer>li=new ArrayList<>();        int i=0,j=0;        while(i<arr1.length && j<arr2.length){            if(arr1[i]<arr2[j]) i++;            else if(arr1[i]>arr2[j]) j++;            else{                if(i!=0 && arr1[i]==arr1[i-1]){                    i++;                    j++;                    continue;                }                li.add(arr1[i]);                i++;                j++;            }        }        if(li.size()==0) li.add(-1);        return li;    } }

137 views
0 replies
0 upvotes

Interview problems

"sort a stack" using recursion

#include <bits/stdc++.h> 

 

void insertSort(stack<int> &stack, int temp){

    if(stack.empty() || stack.top()< temp){

        stack.push(temp);

        return;

    }

 

    int var = stack.top();

    stack.pop();

    insertSort(stack, temp);

    stack.push(var);

}

void sortStack(stack<int> &stack)

{

    // Write your code here

    if(stack.empty()){

        return;

    }

 

    int temp = stack.top();

    stack.pop();

    sortStack(stack);

    insertSort(stack, temp);

}

311 views
0 replies
3 upvotes

Interview problems

easy to understand c++ solution

#include <bits/stdc++.h> 

#include<vector>

void insertstack(stack<int>&stack,int a){

vector<int>v;

while(!stack.empty() && a<stack.top()){

    v.push_back(stack.top());

    stack.pop();

}

stack.push(a);

for(int i=v.size()-1;i>=0;i--){

    stack.push(v[i]);

}

return;

}

void sortStack(stack<int> &stack)

{

    if(stack.empty()){

        return ;

    }

    int a=stack.top();

    stack.pop();

    sortStack(stack);

    insertstack(stack,a);

    return;

}

138 views
0 replies
0 upvotes

Interview problems

A Good Python Solution

from os import *

from sys import *

from collections import *

from math import *

 

def is_empty(stack):

    return len(stack)==0

def push(stack,item):

    stack.append(item)

def pop(stack):

    return stack.pop()

def top(stack):

    return stack[-1]   

#now we have to create function to place the elements in proper sorted order

 

def insert_sorted(stack,element):

    #case 1 if the stack is empty or the top of the stack is less then or equal to the element

    if is_empty(stack) or top(stack)<=element:

    #than we have to push that element in the stack

        push(stack,element)

    else:

        #the element is smaller than the top of stack

        temp=pop(stack)

        insert_sorted(stack,element)

        push(stack,temp)

 

def sortStack(stack):

    if not is_empty(stack):

        temp=pop(stack)

        sortStack(stack)

        insert_sorted(stack,temp)

    

72 views
0 replies
0 upvotes
Full screen
Console