Check if an Array is Stack Sortable

Last Updated on October 3, 2022 by Ria Pathak

Problem Statement

You will be given an array A of integers containing N elements. All the elements inside the array are unique and in the range of 1 to N, where both 1 and N are inclusive.
You have to tell whether this array A is stack sortable or not.

An array A is said to be stack sortable if all the elements of array A can be moved to an array B by using an auxiliary stack when only the given operations are allowed.

1. Operation 1: Removing an element from the front of array A and inserting it into the Stack.
2. Operation 2: Removing the element (top) from the stack and appending it to the end of array B.

So, after moving all the elements of array A to array B using the above operations, if array B is sorted in ascending order, array A can be said to be stack sortable else it cannot be called stack sortable.

Example

Consider the array A, B, and the stack as shown below.

Now, let us try to see if all the elements of array A can be moved to array B such that array B is sorted in ascending order.

1. Operation 1

2. Operation 1 (Now element 1 is at the front of the array as 4 has been removed.)

3. Operation 2 (Remove 1 from the stack and insert it into the array)

4. Operation 1 (Remove 2 from the front and add it to the top of the stack)

5. Operation 2 (Remove 2 from the stack and add it to the array B).

6. Operation 1 (Add 3 into the stack)

7. Operation 2 (Remove 3 from the stack and add it to the array B)

8. Operation 2 (Remove 4 from the stack and add it to the array B)

So, as you can see, we have successfully filled array B in ascending order by removing all the elements of array A and performing just the 2 allowed operations. Hence, array A is stack sortable.

Approach

The approach is purely observation based and we can derive the logic for our observation.

From the sequence of operations performed in the above example, we can observe that:

1. Pushing an element into the stack is only possible when either the stack is empty or the current element that we want to push into the stack is less than the value at the top of the stack.
2. Popping an element from the stack is only possible if the element present at the top of the stack is the next element in the sequence to the last element present in the array B i.e. top of the stack = B[end] + 1. This is because the array B has to maintain the sequence {1,2,3 …. N}.

So, we will continue to perform there operations till all the elements of the array are processed and till the stack is not empty. However, in between the procedure, if we are not able to push the starting element of the array A into the stack and we can’t pop an element from the stack as well, then the array A will be not stack sortable.

So, since we have already seen in the example aboe, a case where we found that array A was stack sortable, let us now see a case when we find that the array A is not stack sortable. For this, consider the example given below.

We have initially filled the array B with 0s. (No need to do this in Java as they are by default 0s. In C++, these may be garbage values hence we will fill them.)

So, let us try to find out whether the array A is stack sortable or not using the 2 points discussed above.
First, since the stack is empty, we will perform operation 1 i.e. push an element (front of the array A) into the stack. (Also, initially, the end pointer will be at index 0)

Now, we move at the next element 3. Since the current element is larger than the top of the stack, we cannot push it into the stack. Also, 2 which is at the top of the stack is not equal to B[end] + 1 as B[end] +1 = B[0] + 1 = 0 + 1 = 1.

Hence, we can’t push the element into the stack and can’t place it into the array either. So, the array A is not stack sortable.

Now that we have discussed the complete procedure, let us write the code for the same.

#include <bits/stdc++.h>
using namespace std;

bool check(int A[], int N)
{
	stack<int> stk;

	int B_end = 0;

	for (int i = 0; i < N; i++)
	{
		if (!stk.empty())
		{
			int top = stk.top();

            //we are checking whether the top of the stack
            //can be appended into the array B
			while (top == B_end + 1)
			{
				B_end = B_end + 1;

				stk.pop();
                
                //if the stack is empty
                // we cannot perform the pop operation again
                // So, we will break
				if (stk.empty())
				{
					break;
				}

				top = stk.top();
			}

            //as per our discussion
            //if stack is empty
            //perform operation 1
            
			if (stk.empty()) {
				stk.push(A[i]);
			}
			
			else
			{
				top = stk.top();

                //this is the case of performing operation 1
				if (A[i] < top)
				{
					stk.push(A[i]);
				}
				
				//else we cannot push the element into the stack
				//and we cannot insert the stack element into the array (already checked)
				//so, A is not stack sortable
				else
				{
					// Not Stack Sortable
					return false;
				}
			}
		}
		else
		{
			// If the stack is empty push the current
			// element in the stack.
			stk.push(A[i]);
		}
	}

	// Stack Sortable
	return true;
}

int main()
{
	int A[] = {4, 1, 2, 3 };
	int N = sizeof(A) / sizeof(int);
	check(A, N)? cout<<"Yes, the array A is stack sortable": cout<<"NO, the array A is not stack sortable";
	return 0;
}

import java.util.*;

class Main {

	static boolean check(int A[], int N) {
		Stack<Integer> stk = new Stack<Integer>();

		int B_end = 0;

		for (int i = 0; i < N; i++) {
			if (!stk.empty()) {
				int top = stk.peek();
                
                //perform operation 1
				while (top == B_end + 1) {
					B_end = B_end + 1;

					stk.pop();

					// If the stack is empty We cannot
					// further perfom pop operation.
					// hence break
					if (stk.empty()) {
						break;
					}

					top = stk.peek();
				}

				if (stk.empty()) {
					stk.push(A[i]);
				} else {
					top = stk.peek();

                    //this is the case of operation 1 
					if (A[i] < top) {
						stk.push(A[i]);
					} // Else we cannot insert the element into the stack
					//and we cannot pop an element from the stack (already checked)
					//so, A is not stack sortable
					else {
						// Not Stack Sortable
						return false;
					}
				}
			} else {
			    //if the stack is empty, perform operation 1
				stk.push(A[i]);
			}
		}

		// Stack Sortable
		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("YES, the array A is stack sortable");
		} else {
			System.out.println("NO, the array B is not stack sortable");
		}

	}
}

Time Complexity

The time complexity of this approach is O(N) as we are traversing all the elements of array A and filling them into array B.

Space Complexity

We are using a Stack and an array B. However, it was the demand of the question to use these. Hence, these are not any auxiliary spaces used by us to solve the problem. Hence, the space complexity will be O(1).

If we consider the stack and the array B space, then the space complexity will be O(N). However, again, it should not be considered as auxiliary space because it was the demand of the question to use them.

This article tried to discuss How to Check if an Array is Stack Sortable. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.