You are given two arrays A and B of unique elements of size N. Check if array B is a stack permutation of the array A or not.
Stack permutation means that array B can be created from array A using a stack and stack operations.
 
Example 1:
Input:
N = 3
A = {1,2,3}
B = {2,1,3}
Output:
1
Explanation:
1. push 1 from A to stack
2. push 2 from A to stack
3. pop 2 from stack to B
4. pop 1 from stack to B
5. push 3 from A to stack
6. pop 3 from stack to B
 
Example 2:
Input:
N = 3
A = {1,2,3}
B = {3,1,2}
Output:
0
Explanation:
Not Possible
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isStackPermutation() which takes two arrays A and B as inputs and returns 1 if it is a stack permutation otherwise returns 0.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
0 <= A[i], B[i] <= 2*10^{5}
Sum of N over all test cases doesn't exceeds 10^{6}

Difficulty: MEDIUM
Tags: Data structures

Implementation
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:


from typing import List

class Solution:

    def isStackPermutation(self, N : int, A : List[int], B : List[int]) -> int:

        # code here

        





Solutions:
from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		i = 0
		j = 0
		while j < N:
			if stack and stack[-1] == B[j]:
				stack.pop()
				j += 1
			elif i < N:
				stack.append(A[i])
				i += 1
			else:
				break
		if len(stack) == 0:
			return 1
		else:
			return 0


from typing import List

class Solution:

	def isStackPermutation(self, n: int, a: List[int], b: List[int]) -> int:
		stack = []
		i = 0
		for elm in a:
			stack.append(elm)
			while stack != [] and stack[-1] == b[i]:
				stack.pop()
				i += 1
		if stack == []:
			return 1
		return 0


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		from queue import Queue

		def check(ip, op, n):
			s = []
			j = 0
			for i in range(n):
				s.append(ip[i])
				while len(s) > 0 and s[-1] == op[j]:
					s.pop()
					j += 1
			if len(s) == 0:
				return True
			return False
		return int(check(A, B, N))


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		sol = []
		j = 0
		for i in range(N):
			stack.append(A[i])
			while len(stack) and j < N and (stack[-1] == B[j]):
				sol.append(stack.pop())
				j += 1
		if sol == B:
			return 1
		return 0


from typing import List

class Solution:

	def isStackPermutation(self, n: int, a: List[int], b: List[int]) -> int:
		st = [-1]
		j = 0
		for i in range(n):
			st.append(a[i])
			while st[-1] != -1 and j < n and (st[-1] == b[j]):
				st.pop()
				j += 1
		if st[-1] == -1:
			return 1
		else:
			return 0


from typing import List

class Solution:

	def isStackPermutation(self, n: int, A: List[int], B: List[int]) -> int:
		s = []
		i = 0
		j = 0
		while i < n:
			s.append(A[i])
			i += 1
			while s and s[-1] == B[j]:
				s.pop()
				j += 1
		return 1 if len(s) == 0 else 0


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		c = 0
		for i in A:
			stack.append(i)
			while len(stack) != 0 and stack[-1] == B[c]:
				stack.pop()
				c += 1
			if c == N:
				return 1
		else:
			return 0


from typing import List
from collections import deque

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		s = deque()
		ans = []
		j = 0
		for i in range(N):
			s.append(A[i])
			if A[i] == B[j]:
				while len(s) > 0 and j < N and (s[-1] == B[j]):
					ans.append(s.pop())
					j += 1
		if ans == B:
			return 1
		return 0


from typing import List

def check_if_stack_permutation(input_arr: [], output_arr: []):
	if len(input_arr) != len(output_arr):
		return False
	n = len(input_arr)
	i = 0
	j = 0
	data_stack = []
	while i < n:
		input_element = input_arr[i]
		if input_element == output_arr[j]:
			i = i + 1
			j = j + 1
			continue
		if len(data_stack) > 0 and output_arr[j] == data_stack[-1]:
			data_stack.pop(-1)
			j = j + 1
			continue
		data_stack.append(input_element)
		i = i + 1
	if j >= n - 1 and len(data_stack) == 0:
		return True
	while len(data_stack) > 0 and j < n:
		if output_arr[j] == data_stack[-1]:
			j = j + 1
			data_stack.pop()
		else:
			return False
	return True

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		return 1 if check_if_stack_permutation(A, B) else 0


from collections import deque
from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = deque()
		stack.append(-1)
		A.reverse()
		for i in range(N):
			while stack[-1] != B[i] and A:
				stack.append(A.pop())
			if stack[-1] == B[i]:
				stack.pop()
			else:
				return 0
		return 1


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		st = []
		i = 0
		j = 0
		for i in A:
			st.append(i)
			if st[-1] == B[j]:
				while st and st[-1] == B[j]:
					st.pop()
					j += 1
		if st:
			return 0
		else:
			return 1


from typing import List
from queue import deque

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		que = deque()
		for i in B:
			que.append(i)
		st = []
		for i in A:
			st.append(i)
			while st and st[-1] == que[0]:
				st.pop()
				que.popleft()
		if not st and (not que):
			return 1
		return 0


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		i = j = 0
		while j < N:
			while not stack or stack[-1] != B[j]:
				if i == N:
					return 0
				stack.append(A[i])
				i += 1
			stack.pop()
			j += 1
		return 1


from typing import List

class Solution:

	def isStackPermutation(self, N: int, a: List[int], b: List[int]) -> int:
		if len(a) != len(b):
			return 0
		st = []
		(i, j) = (0, 0)
		while i < len(a) and j < len(b):
			if st and b[j] == st[-1]:
				j += 1
				st.pop()
			elif b[j] == a[i]:
				i += 1
				j += 1
			elif a[i] != b[j]:
				st.append(a[i])
				i += 1
		if j >= len(b):
			return 1
		if i >= len(a):
			while st:
				if st[-1] == b[j]:
					st.pop()
					j += 1
					if j >= len(b):
						return 1
				else:
					return 0


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		idxB = 0
		idxA = 0
		while idxA <= N:
			if stack and stack[-1] == B[idxB]:
				stack.pop()
				idxB += 1
			elif idxA < N:
				stack.append(A[idxA])
				idxA += 1
			else:
				break
		return 1 if idxB == N else 0


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		n = N
		s = []
		pa = 0
		pb = 0
		while pb < n:
			while s:
				if s[-1] == B[pb]:
					s.pop()
					pb += 1
				else:
					break
			if pa < n:
				if A[pa] == B[pb]:
					pa += 1
					pb += 1
				else:
					s.append(A[pa])
					pa += 1
			if pa >= n and s and (s[-1] != B[pb]):
				return 0
		return 1


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		A = A[::-1]
		a = []
		i = 0
		while A:
			e = A.pop()
			if e != B[i]:
				a.append(e)
			else:
				i += 1
				while a:
					if a[-1] == B[i]:
						a.pop()
						i += 1
					else:
						break
		if i == N:
			return 1
		return 0


from typing import List

class Solution:

	def isStackPermutation(self, n: int, a: List[int], b: List[int]) -> int:
		stack = []
		j = 0
		for i in a:
			stack.append(i)
			if stack[-1] == b[j]:
				while len(stack) != 0 and stack[-1] == b[j]:
					stack.pop()
					j += 1
		if not stack:
			return 1
		else:
			return 0


from collections import deque
from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = deque()
		i = 0
		j = 0
		count = 0
		while j < len(B):
			if len(stack) == 0 or B[j] != stack[-1]:
				if i >= len(A):
					break
				else:
					stack.append(A[i])
				i += 1
			elif B[j] == stack[-1]:
				count += 1
				stack.pop()
				j += 1
		if len(stack) == 0:
			return 1
		else:
			return 0


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		B.reverse()
		for item in A:
			stack.append(item)
			while stack and stack[-1] == B[-1]:
				(stack.pop(), B.pop())
		return int(stack == [])


from typing import List

class Solution:

	def isStackPermutation(self, N: int, A: List[int], B: List[int]) -> int:
		stack = []
		A.reverse()
		B.reverse()
		while A:
			if stack and stack[-1] == B[-1]:
				stack.pop()
				B.pop()
			else:
				stack.append(A.pop())
		return int(stack == B)