Stack Patterns: Decode, Remove and Validate | DSA Interview Patterns - Study Chapter | QuizMaker

Use stacks for latest-unresolved tokens, nested structures, and local undo decisions.

Read: 16m
Type: Chapter
Access: Free

Course

DSA Interview Patterns Roadmap

Topic

Stack and Monotonic Stack

Learning Outcome

Use stacks for latest-unresolved tokens, nested structures, and local undo decisions.

Pattern Recognition

Item	Detail
Core signal	The problem involves parentheses, nested encodings, removing previous characters, or validating order.
Use when	The most recent unresolved item should be matched or removed before older items.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

A stack stores the open work. When a close token or better candidate arrives, resolve the top first.

Exact Practice Question Names

Valid Parentheses
Decode String
Remove K Digits
Longest Valid Parentheses
Basic Calculator

Interview Approach

Push unresolved tokens or indices.
On a closing/resolving event, pop until the current state is valid.
Use indices when length matters.
Process remaining stack content after the scan if required.

Pseudocode

stack = []
for token in input:
  if token opens work: stack.push(token)
  else if token resolves work: pop and combine
  else if token is better than stack top: pop while allowed
handle leftovers
return answer

Sample Dry Run

For remove K digits on 1432219 with k=3, seeing 3 pops 4, seeing 2 pops 3, seeing next 2 keeps equal order, seeing 1 pops 2, giving 1219.

Edge Cases

Empty stack before top()
Nested brackets
Leading zeroes after removals
Unmatched closing bracket

Common Mistakes

Calling top before checking empty
Not handling leftover k removals
Storing characters when indices are needed

Complexity

Item	Detail
Expected time	O(n) because each item is pushed and popped a bounded number of times.
Expected space	O(n) for the stack.

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.