Check if an Array is Stack Sortable

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

1. Initialize an array a[ ] of size n.
2. Create a stack to store the elements to sort the array and a variable end = 0 to point the end.
3. 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.
4. If the stack is empty Push the value of the array at the current index in the stack.
5. 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.
6. 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.

References