DSA: Stack-Based Problems
Solution to Last Week's Challenge
Last week's problem was: DSA: Two Pointers Pattern
The optimal solution uses dsa: two pointers pattern pattern with careful state management.
Complexity Analysis:
- Time Complexity: O(n)
- Space Complexity: O(1)
In the hierarchy of data structures, the stack is often introduced as one of the simplest. However, its simplicity is deceptive. As a senior engineer, I have seen stack-based logic power everything from the undo-redo functionality in complex IDEs to the expression evaluation engines in financial software. In the context of technical interviews, stacks are the gateway to optimizing nested loop problems from O(n²) to O(n), particularly through the use of the Monotonic Stack pattern.
Understanding stacks is not just about knowing the Last-In-First-Out (LIFO) principle; it is about recognizing when a problem requires processing elements in a way that "remembers" previous states while focusing on the immediate neighbor. Whether you are parsing HTML tags, calculating the area of a histogram, or simulating a recursive algorithm to avoid stack overflow errors, the stack is your primary tool for managing linear data with non-linear dependencies.
Theory
The core of a stack is its restricted access. Unlike an array where you can access any index, a stack only allows you to interact with the "top" element. This constraint is what makes it efficient.
From a complexity perspective, every standard stack operation is O(1). The real power comes from the Monotonic Stack, where we maintain the stack elements in a specific order (either strictly increasing or decreasing). This allows us to solve "Nearest Neighbor" problems in linear time because each element is pushed and popped exactly once.
Pattern Visualization
When faced with a linear data structure (like an array or string) and asked to find a relationship between elements based on their relative positions, follow this logic:
Implementation
Let's look at a classic interview problem: Next Greater Element. Given an array, find the first element to the right that is greater than the current element for every index.
Brute Force Approach
The naive way is to use nested loops. For each element, we scan the rest of the array.
def next_greater_brute(nums):
res = [-1] * len(nums)
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
res[i] = nums[j]
break
return res
# Time Complexity: O(n^2)
# Space Complexity: O(1) - excluding output arrayOptimized Approach (Monotonic Stack)
We use a stack to keep track of indices for which we haven't found a "greater element" yet.
def next_greater_optimized(nums):
n = len(nums)
res = [-1] * n
stack = [] # Stores indices
for i in range(n):
# While stack is not empty and current element is
# greater than the element at the index on top of stack
while stack and nums[i] > nums[stack[-1]]:
index = stack.pop()
res[index] = nums[i]
stack.append(i)
return res
# Time Complexity: O(n) - Each element pushed/popped once
# Space Complexity: O(n) - To store the stackComplexity Analysis Table
| Approach | Time Complexity | Space Complexity | Best For |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Small datasets, simple logic |
| Monotonic Stack | O(n) | O(n) | Large datasets, "Next Greater/Smaller" problems |
| Recursive (DFS) | O(n) | O(n) | Tree traversals, nested structures |
Common Patterns
1. Balanced Parentheses
This is the most common entry-level stack problem. We push opening brackets and pop when we see a closing bracket, checking for a match.
def isValid(s):
mapping = {")": "(", "}": "{", "]": "["}
stack = []
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack2. String Manipulation (Simplify Path)
Stacks are excellent for processing paths where .. means moving up a directory (popping from the stack).
def simplifyPath(path):
stack = []
for portion in path.split("/"):
if portion == "..":
if stack: stack.pop()
elif portion not in ("", "."):
stack.append(portion)
return "/" + "/".join(stack)Practice Problems
The following chart maps common stack problems by their frequency in FAANG interviews and their technical difficulty.
This Week's Interview Challenge
Problem: Remove K Digits
Given a non-negative integer represented as a string num, and an integer k, remove k digits from the number so that the new number is the smallest possible.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Constraints:
1 <= k <= num.length <= 10^5numconsists of only digits.numdoes not have any leading zeros except for the zero itself.
Hints:
- Think greedily: to make a number smaller, should you remove a larger digit from the left or the right?
- Use a monotonic stack to maintain the digits in increasing order.
- If after iterating through the string you still need to remove digits (k > 0), where should you remove them from?
- Don't forget to handle leading zeros in your final result string.
Template:
def removeKdigits(num: str, k: int) -> str:
# Your code here
pass
# Submit your solution and check back next week for the detailed answer!Conclusion
The stack is more than just a LIFO buffer; it is a strategic tool for linearizing complex problems. When you see words like "nested," "matching," "previous greater," or "undo," your mind should immediately pivot to a stack-based approach. In interviews, remember that the Monotonic Stack is often the difference between a passing O(n) solution and a failing O(n²) one. Practice visualizing the "push and pop" lifecycle to master the flow of data.