Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
 

Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1


Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.



 
Constraints:

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Starter code: class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        

Solutions:
class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		j = 0
		l = []
		for i in pushed:
			l.append(i)
			while l and l[-1] == popped[j]:
				l.pop()
				j += 1
		if l:
			return False
		return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		if len(pushed) != len(popped):
			return False
		idx = 0
		stack = []
		for i in range(len(popped)):
			if len(stack) > 0 and stack[-1] == popped[i]:
				stack.pop()
			else:
				while idx < len(pushed) and pushed[idx] != popped[i]:
					stack.append(pushed[idx])
					idx += 1
				idx += 1
		return len(stack) == 0


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		i = 0
		j = 0
		demo = []
		for j in range(len(popped)):
			while popped[j] not in demo and i < len(pushed):
				demo.append(pushed[i])
				i += 1
			if demo[-1] == popped[j]:
				demo.pop()
			else:
				return False
		return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		j = 0
		stack = []
		for x in pushed:
			stack.append(x)
			while stack and j < len(popped) and (stack[-1] == popped[j]):
				print(j, stack)
				stack.pop()
				j += 1
		return j == len(popped)


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		l = len(pushed)
		i = 0
		j = 0
		while i < l and j < l:
			if pushed[i] == popped[j]:
				pushed[i] = -1
				popped[j] = -1
				while i > 0:
					if pushed[i] != -1:
						break
					i -= 1
				j += 1
			else:
				i += 1
		i = 0
		j = 0
		r_pop = popped[::-1]
		while i < l and j < l:
			if pushed[i] == -1:
				i += 1
				continue
			if r_pop[j] == -1:
				j += 1
				continue
			if pushed[i] != popped[j]:
				return False
			else:
				i += 1
				j += 1
		return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		stack = []
		n = len(pushed)
		i = j = 0
		while True:
			if not stack or stack[-1] != popped[j]:
				if i >= n:
					return not stack
				stack.append(pushed[i])
				i += 1
			else:
				stack.pop()
				j += 1


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		l = []
		j = i = 0
		for i in pushed:
			l.append(i)
			while l and popped and (l[-1] == popped[0]):
				l.pop()
				popped.pop(0)
		return len(popped) == 0


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		(i, j, k, n) = (-1, 0, 0, len(pushed))
		while i < n and k < n:
			if i >= 0 and pushed[i] == popped[k]:
				i -= 1
				k += 1
			else:
				if j >= n:
					break
				i += 1
				pushed[i] = pushed[j]
				j += 1
		return i == -1 and k == n


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		stack = []
		while len(pushed) or len(popped) or len(stack):
			if len(stack) and len(popped) and (stack[-1] == popped[0]):
				stack.pop()
				popped = popped[1:]
			elif len(pushed):
				stack.append(pushed[0])
				pushed = pushed[1:]
			else:
				return False
		return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		push = []
		i = 0
		while popped:
			if i < len(pushed):
				push += [pushed[i]]
			while push and push[-1] == popped[0]:
				popped.pop(0)
				push.pop()
			if i < len(pushed):
				i += 1
			else:
				return False
		return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		if len(pushed) != len(popped):
			return False
		(stack, i) = ([], 0)
		for (j, n) in enumerate(pushed):
			stack.append(n)
			while len(stack) > 0 and popped[i] == stack[-1]:
				stack.pop()
				i += 1
		return len(stack) == 0


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		pushed.reverse()
		popped.reverse()
		stack = []
		while pushed:
			value = pushed.pop()
			stack.append(value)
			while stack and popped and (stack[-1] == popped[-1]):
				popped.pop()
				stack.pop()
		if not stack:
			return True
		return False


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		stack = []
		j = 0
		for x in pushed:
			stack.append(x)
			while stack and j < len(popped) and (stack[-1] == popped[j]):
				stack.pop()
				j += 1
		return True if j == len(popped) else False


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		stack = []
		push_index = 0
		pop_index = 0
		n = len(pushed)
		while push_index < n:
			while stack and stack[-1] == popped[pop_index]:
				stack.pop()
				pop_index += 1
			stack.append(pushed[push_index])
			push_index += 1
			while stack and stack[-1] == popped[pop_index]:
				stack.pop()
				pop_index += 1
		return True if not stack else False


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		seen = set()
		stack = []
		start = 0
		for (index, element) in enumerate(popped):
			while element not in seen:
				stack.append(pushed[start])
				seen.add(pushed[start])
				start += 1
			catch = False
			while catch == False:
				if catch == False and len(stack) == 0:
					return False
				e = stack.pop()
				if e == element:
					catch = True
		return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		stack = []
		pop_index = 0
		length = len(pushed)
		for i in range(length):
			stack.append(pushed[i])
			while stack[-1] == popped[pop_index]:
				print(stack)
				stack.pop()
				pop_index += 1
				if pop_index >= length or len(stack) == 0:
					break
				continue
		if len(stack) != 0:
			return False
		else:
			return True


class Solution:

	def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
		if not pushed:
			return True
		temp = []
		i = popiter = 0
		while i < len(pushed):
			if temp and temp[-1] == popped[popiter]:
				print(temp, popped[popiter])
				temp.pop()
				popiter += 1
			else:
				temp.append(pushed[i])
				i += 1
		print(temp, popiter)
		while temp:
			if temp[-1] == popped[popiter]:
				temp.pop()
				popiter += 1
			else:
				return False
		return True