Stacks and Monotonic Structures
32 / 170Stacks and Monotonic StructuresLesson 2 of 8About 36 min
If a query must be constant time, the answer has to already be sitting there when it is asked.
Suppose a stack must support total() in constant time. Summing on demand is O(n). Keeping one running total alongside the stack works for push, and breaks on pop unless you can undo the addition, which here you can.
The more general fix, and the one that survives operations you cannot undo, is to store the answer as of that moment with each entry.
class SummingStack: def __init__(self): self.entries = [] # each entry is (value, total including it) def push(self, value): running = self.total() + value self.entries.append((value, running)) def pop(self): return self.entries.pop()[0] def total(self): return self.entries[-1][1] if self.entries else 0 s = SummingStack()for value in [3, 1, 4]: s.push(value)print(s.total())s.pop()print(s.total())The problem below asks for exactly this design with a different aggregate. Decide what each entry needs to carry so that the required query reads a single stored value, and check that your rule still holds after a pop.
You are storing an extra field with each stack entry so a query can read it directly. Which of these queries cannot be supported this way?
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.