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.

Difficulty: interview

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:
            # print(pushed, popped)
            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:
        j=0
        stack=[]
        for x in pushed:
            stack.append(x)
            while stack and j<len(popped) and stack[-1]==popped[j]:
                stack.pop()
                j+=1
        return j==len(popped)

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:
        '''
        start: 1:27
        
        edge cases:
            not poping entire stack (nm, pushed is a permutation of popped)
            
        complexity:
            O(n) time, O(1) space seems right
            
        approach:
            Let's just build a stack and attempt to pop at each opportunity... Seems simple
            Greedy approach, always pop if possible, should work fine due to distinct numbers
        '''
        
        stack = []
        
        while len(pushed) or len(popped) or len(stack):
            if len(stack) and len(popped) and stack[-1] == popped[0]: # can pop
                stack.pop()
                popped = popped[1:]
            elif len(pushed): # can push
                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()
            # print(push)
            # print(popped)
            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 pushed and not popped:
        #    return True
        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:
        pushed.reverse()
        popped.reverse()
        
        stack = []
        while pushed:
            #value = pushed.pop()
            #stack.append(value)
            stack.append(pushed.pop())
            while stack and popped and stack[-1] == popped[-1]:
                popped.pop()
                stack.pop()
                
        #if not pushed and not popped:
        #    return True
        if not stack:
            return True
        return False
                


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 pushed and not popped:
            return True
        return 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
        
        
        # 1 2   
        
        
        # #given one element
        #     not seen: keep push until we see
        #     seen: keep pop until we seen
                


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