mediumStackPattern: Stack Design

Max Stack Weight Solution

Problem Statement

Implement a data structure that supports pushing elements with associated weights onto a stack and popping them. The data structure must maintain a maximum capacity, and any push operation that would exceed this capacity should be rejected. You are given a list of operations, each specifying whether to push an element with a given weight or to pop an element. Return the final state of the stack (list of remaining weights) after all operations are performed.

Examples

Example 1:

Input:{"capacity": 10, "operations": [["push", 5], ["push", 3], ["pop"], ["push", 7], ["push", 2]]}

Output:[5,2]

Explanation: Capacity is 10. 1. Push 5: Stack [5], current weight 5. (5 <= 10) 2. Push 3: Stack [5, 3], current weight 8. (8 <= 10) 3. Pop: Removes 3. Stack [5], current weight 5. 4. Push 7: Attempt to push 7. New weight = 5 (current) + 7 (new) = 12. 12 > 10, push rejected. Stack remains [5]. Current weight 5. 5. Push 2: Attempt to push 2. New weight = 5 (current) + 2 (new) = 7. 7 <= 10, push accepted. Stack [5, 2]. Current weight 7. Final stack: [5, 2].

Example 2:

Input:{"capacity": 5, "operations": [["push", 2], ["push", 4], ["pop"], ["push", 1]]}

Output:[1]

Explanation: Initial stack is empty, capacity is 5. 1. Push 2: Stack [2], current weight 2. (2 <= 5) 2. Push 4: Attempt to push 4. New weight = 2 (current) + 4 (new) = 6. 6 > 5, push rejected. Stack remains [2]. Current weight 2. 3. Pop: Removes 2. Stack []. Current weight 0. 4. Push 1: Stack [1], current weight 1. (1 <= 5) Final stack: [1].

Example 3:

Input:{"capacity": 10, "operations": [["push", 6], ["push", 4], ["pop"], ["push", 3], ["push", 1]]}

Output:[6,3,1]

Explanation: Capacity is 10. 1. Push 6: Stack [6], current weight 6. (6 <= 10) 2. Push 4: Stack [6, 4], current weight 10. (10 <= 10) 3. Pop: Removes 4. Stack [6], current weight 6. 4. Push 3: Stack [6, 3], current weight 9. (9 <= 10) 5. Push 1: Stack [6, 3, 1], current weight 10. (10 <= 10) Final stack: [6, 3, 1].

Example 4:

Input:{"capacity": 7, "operations": [["push", 7], ["push", 1], ["pop"], ["push", 5], ["push", 2]]}

Output:[5,2]

Explanation: Capacity is 7. 1. Push 7: Stack [7], current weight 7. (7 <= 7) 2. Push 1: Attempt to push 1. New weight = 7 + 1 = 8. 8 > 7, push rejected. Stack [7]. Current weight 7. 3. Pop: Removes 7. Stack []. Current weight 0. 4. Push 5: Stack [5], current weight 5. (5 <= 7) 5. Push 2: Attempt to push 2. New weight = 5 + 2 = 7. 7 <= 7, push accepted. Stack [5, 2]. Current weight 7. Final stack: [5, 2].

Example 5:

Input:{"capacity": 15, "operations": [["push", 5], ["push", 8], ["push", 3], ["pop"], ["push", 4]]}

Output:[5,4]

Explanation: Capacity is 15. 1. Push 5: Stack [5], weight 5. (5 <= 15) 2. Push 8: Stack [5, 8], weight 13. (13 <= 15) 3. Push 3: Attempt to push 3. New weight = 13 + 3 = 16. 16 > 15, rejected. Stack [5, 8]. Weight 13. 4. Pop: Removes 8. Stack [5]. Weight 5. 5. Push 4: Stack [5, 4], weight 9. (9 <= 15) Final stack: [5, 4].

Constraints

The capacity will be a positive integer.
The number of operations will be between 0 and 10^5.
Element weights will be positive integers.
The stack will never be popped when empty.
An element's weight will not exceed the capacity.

Time: O(N) Space: O(N)

Use an array or `LinkedList` for the stack and a single integer variable for the current total weight. This allows for O(1) push and pop operations, with a constant time check for capacity. The overall time complexity will be linear with respect to the number of operations.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

def max_stack_weight(params):
    capacity = params['capacity']
    operations = params['operations']
    stack = []
    current_weight = 0

    for op in operations:
        op_type = op[0]
        if op_type == 'push':
            weight = op[1]
            if current_weight + weight <= capacity:
                stack.append(weight)
                current_weight += weight
        elif op_type == 'pop':
            if stack:
                popped_weight = stack.pop()
                current_weight -= popped_weight

    return stack