mediumStackPattern: Stack Design
Sequence of Stack Operations Solution
Problem Statement
You are given a sequence of operations representing either pushing an element onto a stack or popping an element from a stack. Each operation is represented by an integer. A positive integer `x` signifies pushing `x` onto the stack. A negative integer `-x` signifies popping the element `x` from the top of the stack. If a pop operation is requested for an element that is not at the top of the stack, or if the stack is empty and a pop operation is requested, the operation is considered invalid. You need to determine the final state of the stack after processing all valid operations. The operations are provided as a list of integers.
Examples
Example 1:
Input:[1, 2, -2, 3, -3, -1]
Output:[]
Explanation: Assuming a negative integer -x signifies popping the element x *if* x is at the top of the stack. If x is not at the top, or the stack is empty, the operation is invalid and the stack remains unchanged.
1. Push 1: Stack = [1]
2. Push 2: Stack = [1, 2]
3. Pop 2: Stack = [1]
4. Push 3: Stack = [1, 3]
5. Pop 3: Stack = [1]
6. Pop 1: Stack = []
Final Stack: []
Example 2:
Input:[5, 10, -10, 15, -5, 20]
Output:[5, 15, 20]
Explanation: 1. Push 5: Stack = [5]
2. Push 10: Stack = [5, 10]
3. Pop 10: Stack = [5]
4. Push 15: Stack = [5, 15]
5. Pop 5: Expected top is 5, but actual top is 15. Invalid operation. Stack remains [5, 15]
6. Push 20: Stack = [5, 15, 20]
Final Stack: [5, 15, 20]
Constraints
- The number of operations is between 0 and 10^5.
- The values of elements pushed onto the stack are between 1 and 10^9.
- The values of elements to be popped are between 1 and 10^9.
- Each operation value (positive or negative) will not exceed 10^9.
Time: O(N) Space: O(N)
The most efficient approach uses a single data structure, such as a dynamic array or list, to act as the stack. Iterate through the operations: push positive values, and for negative values, check the top for a match before popping. This directly simulates the required stack behavior.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def sequence_of_stack_operations(operations):
stack = []
for op in operations:
if op > 0:
stack.append(op)
else:
value_to_pop = -op
if stack and stack[-1] == value_to_pop:
stack.pop()
return stack