Stacks and Monotonic Structures
31 / 170Stacks and Monotonic StructuresLesson 1 of 8About 52 min
The stack is the answer whenever the thing you opened last is the thing that must close first.
Here is the pattern on a problem with no brackets in it. Repeatedly remove adjacent identical characters until none remain, so abbaca collapses to ca.
A stack does this in one pass. Each incoming character either cancels the top or joins it.
def collapse_adjacent(text): stack = [] for ch in text: if stack and stack[-1] == ch: stack.pop() # the pair cancels else: stack.append(ch) return "".join(stack) print(collapse_adjacent("abbaca"))print(collapse_adjacent("azxxzy"))Stacks are not only for matching pairs. Resolving a path with .. segments is the same shape: .. undoes the most recent directory, which is exactly a pop.
def resolve_path(path): stack = [] for part in path.split("/"): if part == "" or part == ".": continue # nothing to do elif part == "..": if stack: stack.pop() # step back up else: stack.append(part) return "/" + "/".join(stack) print(resolve_path("/home//user/../docs/./notes"))print(resolve_path("/../.."))This checks the top before checking emptiness. Type what it prints, including the exception name if it raises one.
def broken(text): stack = [] for ch in text: if stack[-1] == ch and stack: stack.pop() else: stack.append(ch) return "".join(stack) try: print(broken("ab"))except IndexError: print("IndexError")Three one-pass stack problems. collapse_k removes runs of exactly k identical adjacent characters, repeatedly. undo_history applies a list of actions where undo cancels the most recent surviving action. is_balanced_single checks a string containing only ( and ).
Tests
print(collapse_k("deeedbbcccbdaa", 3))print(undo_history(["open", "type", "undo", "save", "undo", "undo", "undo"]))print(is_balanced_single("(())"), is_balanced_single("())("), is_balanced_single("(("))Output
Run tests to see output.
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.