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.
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.
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.
The only line of output of each test case should contain 'N' space separated integers denoting the stack in a sorted order.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= 'T' <= 100
1 <= 'N' <= 100
1 <= |'V'| <= 10^9
Where |V| denotes the absolute value of any stack element.
Time limit: 1 sec
1
5
5 -2 9 -7 3
9 5 3 -2 -7
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.
1
5
-3 14 18 -5 30
30 18 14 -3 -5
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.
Try to think how you can sort the stack considering you can only access the top element of the stack.
The idea of the solution is very simple.
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
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.
All tags
Sort by
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));
}
}
}
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);
}
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);
}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);
}Interview problems
One line Python solution
from os import *
from sys import *
from collections import *
from math import *
def sortStack(stack):
stack.sort()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);
}
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; } }
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);
}
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;
}
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)
