Stack Problems
Here are more classic stack problems to solidify your understanding.
1. Stock Span Problem
Given stock prices, for each day find how many consecutive days the price was less than or equal to current day's price. Use stack to store indices of decreasing prices.
public static int[] stockSpan(int[] prices) {
int n = prices.length;
int[] span = new int[n];
Stack stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
stack.pop();
}
span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
return span;
}
2. Minimum Element in Stack (O(1) extra space)
Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time. Use an auxiliary stack or store min in each node (or use a single stack storing min along with value).
public class MinStack {
private Stack stack = new Stack<>();
private Stack minStack = new Stack<>();
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int val = stack.pop();
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Two Minute Drill
- Stock span: similar to next greater element, uses stack of indices.
- Min stack: maintain auxiliary stack or store min with each element.
- These problems are common in interviews.
- Stack is a versatile data structure for many "last seen" problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com