In check if an array is stack sortable problem we have given an array a[ ] of size n containing elements from 1 to n in random order. Sort the array in ascending order using a temporary stack following only these two operations –
- Remove the element at the starting index in the array and store it in the stack.
- Pop the top From stack and append it at the end of another array.
Check if it is possible to sort the given array using stack or not.
Example
Input
a[ ] = {4, 1, 2, 3}
Output
Given array can be sorted using stack.
Input
a[ ] = {2, 3, 1}
Output
Given array can not be sorted using stack.
Algorithm
- Initialize an array a[ ] of size n.
- Create a stack to store the elements to sort the array and a variable end = 0 to point the end.
- Traverse from 0 to n-1 and check if the stack is empty, push the value of the array at the current index in the stack. Else store the top of the stack in a variable top. While the top is equal to end+1, increment the end and pop the top. Check if the stack is empty break the loop. Update the variable top as the current top in the stack.
- If the stack is empty Push the value of the array at the current index in the stack.
- Else store the top of the stack in a variable top. Check if the value of the array at the current index is less than the top, push the array element in the stack. Else return false.
- Return true.
C++ Program for Check if an Array is Stack Sortable
#include <bits/stdc++.h> using namespace std; bool check(int a[], int n){ stack<int> S; int end = 0; for(int i = 0; i < n; i++){ if(!S.empty()){ int top = S.top(); while(top == end + 1){ end = end + 1; S.pop(); if(S.empty()){ break; } top = S.top(); } if(S.empty()) { S.push(a[i]); } else{ top = S.top(); if(a[i] < top){ S.push(a[i]); } else{ return false; } } } else{ S.push(a[i]); } } return true; } int main(){ int a[] = {4, 1, 2, 3}; int n = sizeof(a) / sizeof(a[0]); check(a, n)? cout<<"Given array can be sorted using stack.": cout<<"Given array can not be sorted using stack."; return 0; }
Given array can be sorted using stack.
Java Program for Check if an Array is Stack Sortable
import java.util.Stack; class soryArray{ static boolean check(int a[], int n){ Stack<Integer> S = new Stack<Integer>(); int end = 0; for(int i = 0; i < n; i++) { if(!S.empty()){ int top = S.peek(); while(top == end + 1){ end = end + 1; S.pop(); if(S.empty()){ break; } top = S.peek(); } if (S.empty()) { S.push(a[i]); } else{ top = S.peek(); if(a[i] < top) { S.push(a[i]); } else{ return false; } } } else{ S.push(a[i]); } } return true; } public static void main(String[] args) { int a[] = {4, 1, 2, 3}; int n = a.length; if(check(a, n)){ System.out.println("Given array can be sorted using stack."); } else{ System.out.println("Given array can not be sorted using stack."); } } }
Given array can be sorted using stack.
Complexity Analysis for Check if an Array is Stack Sortable
Time Complexity: O(n) where n is the number of elements in the array.
Space Complexity: O(n) because we used space to store the n elements.