Given an array of N distinct elements where elements are between 1 and N both inclusive, check if it is stack-sortable or not. An array A[] is said to be stack sortable if it can be stored in another array B[], using a temporary stack S. The operations that are allowed on array are:
- Remove the starting element of array A[] and push it into the stack.
- Remove the top element of the stack S and append it to the end of array B.
If all the element of A[] can be moved to B[] by performing these operations such that array B is sorted in ascending order, then array A[] is stack sortable.
Examples:
Input : A[] = { 3, 2, 1 }
Output : YES
Explanation :
Step 1: Remove the starting element of array A[]
and push it in the stack S. ( Operation 1)
That makes A[] = { 2, 1 } ; Stack S = { 3 }
Step 2: Operation 1
That makes A[] = { 1 } Stack S = { 3, 2 }
Step 3: Operation 1
That makes A[] = {} Stack S = { 3, 2, 1 }
Step 4: Operation 2
That makes Stack S = { 3, 2 } B[] = { 1 }
Step 5: Operation 2
That makes Stack S = { 3 } B[] = { 1, 2 }
Step 6: Operation 2
That makes Stack S = {} B[] = { 1, 2, 3 }
Input : A[] = { 2, 3, 1}
Output : NO
Given, array A[] is a permutation of [1, …, N], so let us suppose the initially B[] = {0}. Now we can observe that:
- We can only push an element in the stack S if the stack is empty or the current element is less than the top of the stack.
- We can only pop from the stack only if the top of the stack is as the array B[] will contain {1, 2, 3, 4, …, n}.
If we are not able to push the starting element of the array A[], then the given array is Not Stack Sortable. Below is the implementation of above idea:
C++
#include <bits/stdc++.h>
using namespace std;
bool check( int A[], int N)
{
stack< int > S;
int B_end = 0;
for ( int i = 0; i < N; i++)
{
if (!S.empty())
{
int top = S.top();
while (top == B_end + 1)
{
B_end = B_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<< "YES" : cout<< "NO" ;
return 0;
}
|
Java
import java.util.Stack;
class GFG {
static boolean check( int A[], int N) {
Stack<Integer> S = new Stack<Integer>();
int B_end = 0 ;
for ( int i = 0 ; i < N; i++) {
if (!S.empty()) {
int top = S.peek();
while (top == B_end + 1 ) {
B_end = B_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( "YES" );
} else {
System.out.println( "NO" );
}
}
}
|
Python3
def check(A, N):
S = []
B_end = 0
for i in range (N):
if len (S) ! = 0 :
top = S[ - 1 ]
while top = = B_end + 1 :
B_end = B_end + 1
S.pop()
if len (S) = = 0 :
break
top = S[ - 1 ]
if len (S) = = 0 :
S.append(A[i])
else :
top = S[ - 1 ]
if A[i] < top:
S.append(A[i])
else :
return False
else :
S.append(A[i])
return True
if __name__ = = "__main__" :
A = [ 4 , 1 , 2 , 3 ]
N = len (A)
if check(A, N):
print ( "YES" )
else :
print ( "NO" )
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static bool check( int [] A, int N)
{
Stack< int > S = new Stack< int >();
var B_end = 0;
for ( int i = 0; i < N; i++)
{
if (S.Count != 0)
{
int top = S.Peek();
while (top == B_end + 1)
{
B_end = B_end + 1;
S.Pop();
if (S.Count == 0) {
break ;
}
top = S.Peek();
}
if (S.Count == 0) {
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)) {
Console.WriteLine( "YES" );
}
else {
Console.WriteLine( "NO" );
}
}
}
|
Javascript
function check(A, N) {
let S = [];
let B_end = 0;
for (let i = 0; i < N; i++) {
if (S.length != 0) {
let top = S[0];
while (top == B_end + 1) {
B_end = B_end + 1;
S.shift();
if (S.length == 0) {
break ;
}
top = S[0];
}
if (S.length != 0) {
S.push(A[i]);
}
else {
top = S[0];
if (A[i] < top) {
S.push(A[i]);
}
else {
return false ;
}
}
}
else {
S.push(A[i]);
}
}
return true ;
}
let A = [4, 1, 2, 3];
let N = A.length;
check(A, N) ? console.log( "YES" ) : console.log( "NO" );
|
Output:
YES
Time Complexity: O(N)
Auxiliary Space: O(N) because using stack
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!