Check if an array is stack sortable

Algorithm

Let’s have a look at the step-by-step solution to the problem.

• Create an array a[] of size n.
• Create a stack to hold the array's elements and a variable end = 0 to indicate the end.
• If the stack is empty, traverse from 0 to n-1 and push the value of the array at the current index in the stack. Otherwise, put the stack's top in a variable top. Increase the end and pop the top while the top is equal to end+1. If the stack is empty, the loop is broken. Replace the variable top with the stack's current top.
• If the stack is completely empty Push the array's value to the stack at the current index.
• Otherwise, put the stack's top in a variable top. If the array value at the current position is less than the top, push the array element onto the stack. Otherwise, return false.
• Return true.

Implementation

Let us see the code to check if array is stack sortable or not.

#include <bits/stdc++.h> 
using namespace std; 
  
bool check(int arr[], int x){ 
    stack<int> Stk; 
    int end = 0; 
    for(int i = 0; i < x; i++){ 
        if(!Stk.empty()){      
            int top = Stk.top();   
            while(top == end + 1){ 
                end = end + 1;   
                Stk.pop();   
                if(Stk.empty()){ 
                    break; 
                }   
                top = Stk.top(); 
            }   
            if(Stk.empty()) { 
                Stk.push(arr[i]); 
            } 
            
            else{ 
                top = Stk.top();   
                if(arr[i] < top){ 
                    Stk.push(arr[i]); 
                } 
                else{ 
                    return false; 
                } 
            } 
        } 
        else{ 
            Stk.push(arr[i]); 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    int a[] = {4,1,2,3}; 
    int n = sizeof(a) / sizeof(a[0]);
    
    check(a, n)? cout<<"array is stack sortable": cout<<"array is not stack sortable";    
    
    return 0; 
}

You can also try this code with Online C++ Compiler

Run Code

Input: 4,1,2,3

Output:

array is stack sortable

Algorithm Complexity

Let's see the complexity of the code.

Time Complexity

 O(n) because we traverse all the nodes. Here n is the number of nodes in a given binary tree.

Space Complexity

The space complexity of a skewed tree is O(n), while the call stack of a balanced tree consumes O(log n) space (i.e., the height of the balanced tree).

Frequently Asked Questions

What sorting algorithm does sort function in C++ use? 

C++ uses a merge sort algorithm in its Inbuilt sort function.

What's the difference between a queue and a stack?

The main difference between Stack and Queue Data Structures is that Stack uses a LIFO data structure type, whereas Queue uses a FIFO data structure type. Last In First Out (LIFO) is a term that relates to the order in which things are done. When we add data to a Stack, the last entry is processed first. FIFO, on the other hand, is a term that stands for "First In, First Out."

Stack is a recursive data structure, Why?  

A stack is a recursive data structure; it's either empty or made up of a top and the remainder, a stack in and of itself. 

What is an example of a stack in real life?

We use the concept of LIFO/stack in our daily activities such as in a cafeteria, a stack of trays; In a cabinet, a stack of plates; In a classroom; a stack of books.

Conclusion

In this article, we have extensively discussed if an array is stack sortable. We started with the introduction of the problem, the problem statement of if an array is stack sortable, the example of the problem, the algorithm, and finally concluded with the implementation of the same.

After reading about if an array is a stack sortable or not, are you not feeling excited to read/explore more articles on the topic of binary trees? Don't worry; Coding Ninjas has you covered. To learn, see the Introduction to stack, Reverse an array using Stack and Recursion and stack. 

Recommended Problems:

• Sort A Stack
• Stack Permutation
• Max Stack
   

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your capacity in coding, you may check out the mock test series and participate in the contests hosted on the Coding Ninjas Studio website. But if you have just started learning and are looking for questions asked by tech giants like Amazon, Microsoft, Google, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

 You may also consider our paid courses to give your career an edge over others!

 Do upvote our blogs if you find them helpful and engaging!

Happy Learning!