Valid stack sequence

Given two integer arrays pushed and popped, each with distinct values, write a function that returns True if this could have been the result of a sequence of push and pop operations on an initially empty stack, or False otherwise.

For example, given the following inputs:

pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]

Your function should return True. We can push 1, 2, 3, 4, then pop 4, push 5, then pop 5, 3, 2, 1.

However, for pushed = [1, 2, 3, 4, 5] and popped = [4, 3, 5, 1, 2], the answer is False. After pushing 1, 2, 3, 4 and popping 4, 3, then pushing 5 and popping 5, we are left with 1 on top of 2 -- so we cannot pop 1 before 2.

1def valid_stack_sequence(pushed: list[int], popped: list[int]) -> bool:
2    # implement valid_stack_sequence
3    return False
4