Design prefix-sum function and max stack
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 303. Range Sum Query – Immutable (design a reusable prefix-sum function) LeetCode 716. Max Stack (similar design question)
https://leetcode.com/problems/range-sum-query-immutable/description/ https://leetcode.com/problems/max-stack/description/
Quick Answer: This question evaluates understanding of prefix-sum precomputation for constant-time range queries and the design of a max-enabled stack, focusing on data structure design, algorithmic complexity, and space-time trade-offs.
Design a function that processes a sequence of operations on a Max Stack. The stack supports the following commands: (1) "push x": push integer x onto the stack; (2) "pop": remove and return the top element; (3) "top": return the top element without removing it; (4) "peekMax": return the current maximum element; (5) "popMax": remove and return the maximum element; if multiple maxima exist, remove the one closest to the top. The function must return a list of integers representing the results of all operations that produce output (pop, top, peekMax, popMax), in order. All inputs are valid; operations that require a non-empty stack will not be called on an empty stack.
Constraints
- 1 <= len(operations) <= 20000
- Operations are one of: "push x", "pop", "top", "peekMax", "popMax"
- -10^9 <= x <= 10^9
- Operations that require a non-empty stack (pop, top, peekMax, popMax) will not be called on an empty stack
Solution
def process_max_stack(operations: list[str]) -> list[int]:
stack = []
max_stack = []
out = []
def push_val(v: int) -> None:
stack.append(v)
if max_stack:
max_stack.append(v if v > max_stack[-1] else max_stack[-1])
else:
max_stack.append(v)
for op in operations:
if op.startswith("push"):
_, x_str = op.split()
x = int(x_str)
push_val(x)
elif op == "pop":
val = stack.pop()
max_stack.pop()
out.append(val)
elif op == "top":
out.append(stack[-1])
elif op == "peekMax":
out.append(max_stack[-1])
elif op == "popMax":
current_max = max_stack[-1]
buffer = []
while stack[-1] != current_max:
buffer.append(stack.pop())
max_stack.pop()
# Remove the maximum (closest to top among maxima)
removed = stack.pop()
max_stack.pop()
out.append(removed)
# Restore buffered elements
for v in reversed(buffer):
push_val(v)
else:
# Input guaranteed valid per problem statement; no-op for safety
pass
return out
Explanation
Use two stacks: one for values and one for tracking the running maximum at each position. push, pop, top, and peekMax are O(1) by updating/reading the top of both stacks. For popMax, store the current maximum, then pop elements into a temporary buffer until the top equals that maximum; remove it, then push back buffered elements to restore order and recompute running maxima.
Time complexity: push/top/peekMax/pop: O(1); popMax: O(n) in the worst case. Space complexity: O(n) for the stacks and temporary buffer.
Hints
- Maintain a parallel stack that tracks the maximum at each depth.
- For popMax, move elements to a temporary buffer until the maximum is at the top, remove it, then restore the buffered elements.
- When restoring elements from the buffer, use the same push logic so the max-tracking structure stays correct.