Stack: Check if an array is stack sortable

Problem Statement:

You are given an array with unique elements between 1 to n, you need to check if the array is stack sortable.

An array is considered as stack sortable, if it can be re arranged into sorted array using stack by using below operations:

1. Remove the first element from a[] and push it into stack.

2. Remove from top element from the stack and append to b[]

Example:

Input arr = [4, 1, 3, 2]

Yes.

Push 4 to stack [4]

Push 1 to stack [4, 1] and pop 1 to b[1]

Push 3 to stack [4, 3]

Push 2 to stack [4, 3, 2] Pop 2 to b [1, 2]

Push 3 to b [1, 2, 3]

Push 4 to b [1, 2, 3, 4]

Solution Explanation:

Initialize a stack set is_expected to 1

Iterate through the array and push each element to stack.

If the top of stack equals is_expected, pop from stack and increment is_expected and continue the process.

Repeat popping stack, and top matches is_expected.

Then if all elements are correctly arranged as is_expected = n+1 then return true else false.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

bool solution(vector<int> &arr) 
{
    
    stack<int> stk;
    
    int n = arr.size();
    
    // initialize the is_expected to 1
    int is_expected = 1;

    for (int num : arr) 
    {
        
        stk.push(num);
        
        while (!stk.empty() && stk.top() == is_expected) 
        {
                   
            stk.pop();
            is_expected++;
        }
    }

    return is_expected == n + 1;
}

int main() 
{
    
    vector<int> arr = {4, 1, 3, 2};

    if (solution(arr)) 
    {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Output

Yes