You know push and pop. The advanced stack problems are about three ideas: sharing one array between several stacks, the monotonic stack that answers previous/next greater or smaller questions in O(n), and augmenting a stack so getMin() is O(1).
The three families of stack problems
The monotonic stack pattern
Most nearest element questions — what is the closest element to the left that is greater than me? — have an obvious O(n²) answer: for every i scan backwards. The stack version scans once and keeps only the candidates that can still be the answer for some future element.
arr = [15, 10, 18, 12, 4, 6, 2, 8] stack holds values, decreasing bottom → top
i arr[i] pop while top <= arr[i] top after pops previous greater push → stack
0 15 – (empty) -1 [15]
1 10 – 15 15 [15, 10]
2 18 10, 15 (empty) -1 [18]
3 12 – 18 18 [18, 12]
4 4 – 12 12 [18, 12, 4]
5 6 4 12 12 [18, 12, 6]
6 2 – 6 6 [18, 12, 6, 2]
7 8 2, 6 12 12 [18, 12, 8]| Question | Scan direction | Pop while | Stack order (bottom → top) |
|---|---|---|---|
| Previous greater | left → right | top <= arr[i] | strictly decreasing |
| Next greater | right → left | top <= arr[i] | strictly decreasing |
| Previous smaller | left → right | top >= arr[i] | strictly increasing |
| Next smaller | right → left | top >= arr[i] | strictly increasing |
Store indices on the stack rather than values when you also need distances (stock span, histogram widths). Store values when only the element itself is wanted. The rest of this topic uses this pattern five times; each section says which variant it is.
Implement two stacks in one array
Naive split. Give the first half of the array to stack 1 and the second half to stack 2. Wasteful: with capacity 6, stack 1 is full after 3 pushes even if stack 2 is empty.
index: 0 1 2 3 4 5
┌────┬────┬────┬────┬────┬────┐
│ 5 │ 10 │ 15 │ 20 │ 30 │ 25 │
└────┴────┴────┴────┴────┴────┘
stack 1 ──────────▶ ◀── stack 2
top1 = 3 top2 = 4 full: top1 + 1 == top2class TwoStacks:
def __init__(self, n):
self.cap = n
self.arr = [None] * n
self.top1 = -1 # stack 1 grows from the left end
self.top2 = n # stack 2 grows from the right end
def push1(self, x):
if self.top1 + 1 == self.top2: # the tops have met: no free slot
return False
self.top1 += 1
self.arr[self.top1] = x
return True
def push2(self, x):
if self.top1 + 1 == self.top2:
return False
self.top2 -= 1
self.arr[self.top2] = x
return True
def pop1(self):
if self.top1 < 0:
return None
x = self.arr[self.top1]
self.top1 -= 1
return x
def pop2(self):
if self.top2 >= self.cap:
return None
x = self.arr[self.top2]
self.top2 += 1
return x
def size1(self):
return self.top1 + 1
def size2(self):
return self.cap - self.top2
s = TwoStacks(6)
for x in (5, 10, 15):
s.push1(x)
print("push1(20):", "true" if s.push1(20) else "false") # a 3+3 split would refuse this
for x in (25, 30):
s.push2(x)
print("push2(35):", "true" if s.push2(35) else "false") # now the array really is full
print("pop1:", s.pop1())
print("pop1:", s.pop1())
print("pop2:", s.pop2())
print("pop2:", s.pop2())
print("size1:", s.size1())
print("size2:", s.size2())#include <iostream>
#include <vector>
using namespace std;
class TwoStacks {
vector<int> arr;
int cap, top1, top2;
public:
TwoStacks(int n) : arr(n), cap(n), top1(-1), top2(n) {}
bool push1(int x) {
if (top1 + 1 == top2) return false; // the tops have met: no free slot
arr[++top1] = x;
return true;
}
bool push2(int x) {
if (top1 + 1 == top2) return false;
arr[--top2] = x;
return true;
}
int pop1() { return top1 < 0 ? -1 : arr[top1--]; }
int pop2() { return top2 >= cap ? -1 : arr[top2++]; }
int size1() const { return top1 + 1; }
int size2() const { return cap - top2; }
};
int main() {
TwoStacks s(6);
for (int x : {5, 10, 15}) s.push1(x);
cout << "push1(20): " << (s.push1(20) ? "true" : "false") << "\n"; // a 3+3 split would refuse this
for (int x : {25, 30}) s.push2(x);
cout << "push2(35): " << (s.push2(35) ? "true" : "false") << "\n"; // now the array really is full
cout << "pop1: " << s.pop1() << "\n";
cout << "pop1: " << s.pop1() << "\n";
cout << "pop2: " << s.pop2() << "\n";
cout << "pop2: " << s.pop2() << "\n";
cout << "size1: " << s.size1() << "\n";
cout << "size2: " << s.size2() << "\n";
}public class Main {
static class TwoStacks {
int[] arr;
int cap, top1, top2;
TwoStacks(int n) { arr = new int[n]; cap = n; top1 = -1; top2 = n; }
boolean push1(int x) {
if (top1 + 1 == top2) return false; // the tops have met: no free slot
arr[++top1] = x;
return true;
}
boolean push2(int x) {
if (top1 + 1 == top2) return false;
arr[--top2] = x;
return true;
}
int pop1() { return top1 < 0 ? -1 : arr[top1--]; }
int pop2() { return top2 >= cap ? -1 : arr[top2++]; }
int size1() { return top1 + 1; }
int size2() { return cap - top2; }
}
public static void main(String[] args) {
TwoStacks s = new TwoStacks(6);
for (int x : new int[]{5, 10, 15}) s.push1(x);
System.out.println("push1(20): " + s.push1(20)); // a 3+3 split would refuse this
for (int x : new int[]{25, 30}) s.push2(x);
System.out.println("push2(35): " + s.push2(35)); // now the array really is full
System.out.println("pop1: " + s.pop1());
System.out.println("pop1: " + s.pop1());
System.out.println("pop2: " + s.pop2());
System.out.println("pop2: " + s.pop2());
System.out.println("size1: " + s.size1());
System.out.println("size2: " + s.size2());
}
}class TwoStacks {
constructor(n) {
this.cap = n;
this.arr = new Array(n);
this.top1 = -1; // stack 1 grows from the left end
this.top2 = n; // stack 2 grows from the right end
}
push1(x) {
if (this.top1 + 1 === this.top2) return false; // the tops have met: no free slot
this.arr[++this.top1] = x;
return true;
}
push2(x) {
if (this.top1 + 1 === this.top2) return false;
this.arr[--this.top2] = x;
return true;
}
pop1() { return this.top1 < 0 ? null : this.arr[this.top1--]; }
pop2() { return this.top2 >= this.cap ? null : this.arr[this.top2++]; }
size1() { return this.top1 + 1; }
size2() { return this.cap - this.top2; }
}
const s = new TwoStacks(6);
for (const x of [5, 10, 15]) s.push1(x);
console.log("push1(20):", s.push1(20)); // a 3+3 split would refuse this
for (const x of [25, 30]) s.push2(x);
console.log("push2(35):", s.push2(35)); // now the array really is full
console.log("pop1:", s.pop1());
console.log("pop1:", s.pop1());
console.log("pop2:", s.pop2());
console.log("pop2:", s.pop2());
console.log("size1:", s.size1());
console.log("size2:", s.size2());push1(20): true
push2(35): false
pop1: 20
pop1: 15
pop2: 30
pop2: 25
size1: 2
size2: 0Time O(1) per operation · Space O(n) for the shared array
Implement k stacks in one array
The two-ends trick does not extend to three or more stacks. The general solution threads linked lists through the array: every stack is a linked list of slots, and the unused slots form one more linked list, the free list. Three small arrays do all the bookkeeping.
| Array / variable | Size | Meaning |
|---|---|---|
arr[n] | n | the stored values |
top[k] | k | top[sn] = index of the top slot of stack sn; -1 when that stack is empty |
next[n] | n | for a used slot: index of the slot below it in its stack; for a free slot: index of the next free slot (-1 = none) |
free | 1 | index of the first free slot — the top of the free list |
after push(15,0) push(45,1) push(17,0) push(39,1) push(11,2) with n = 10, k = 3
index : 0 1 2 3 4 5 6 7 8 9
arr : 15 45 17 39 11 _ _ _ _ _
next : -1 -1 0 1 -1 6 7 8 9 -1
↑ ↑ ↑ ↑ └── free list: 5 → 6 → 7 → 8 → 9 → -1
└─────────┘ │ └─ stack 2: 11 free = 5
stack 0: 17 → 15 stack 1: 39 → 45 top = [2, 3, 4]class KStacks:
def __init__(self, n, k):
self.arr = [None] * n
self.top = [-1] * k # top[sn] = index of the top of stack sn
self.next = [i + 1 for i in range(n)] # free list: slot i → slot i+1
self.next[n - 1] = -1
self.free = 0 # first free slot
def is_full(self):
return self.free == -1
def is_empty(self, sn):
return self.top[sn] == -1
def push(self, x, sn):
if self.is_full():
return False
i = self.free
self.free = self.next[i] # take the slot off the free list
self.arr[i] = x
self.next[i] = self.top[sn] # link it above the old top of stack sn
self.top[sn] = i
return True
def pop(self, sn):
if self.is_empty(sn):
return None
i = self.top[sn]
self.top[sn] = self.next[i] # unlink the top slot
self.next[i] = self.free # give it back to the free list
self.free = i
return self.arr[i]
s = KStacks(10, 3)
for x, sn in ((15, 0), (45, 1), (17, 0), (39, 1), (11, 2)):
s.push(x, sn)
print("pop(0):", s.pop(0))
print("pop(1):", s.pop(1))
print("pop(2):", s.pop(2))
print("pop(0):", s.pop(0))
print("empty(2):", "true" if s.is_empty(2) else "false")
print("empty(0):", "true" if s.is_empty(0) else "false")#include <iostream>
#include <vector>
using namespace std;
class KStacks {
vector<int> arr, top, nxt;
int freeTop;
public:
KStacks(int n, int k) : arr(n), top(k, -1), nxt(n), freeTop(0) {
for (int i = 0; i < n; i++) nxt[i] = i + 1; // free list: slot i → slot i+1
nxt[n - 1] = -1;
}
bool isFull() const { return freeTop == -1; }
bool isEmpty(int sn) const { return top[sn] == -1; }
bool push(int x, int sn) {
if (isFull()) return false;
int i = freeTop;
freeTop = nxt[i]; // take the slot off the free list
arr[i] = x;
nxt[i] = top[sn]; // link it above the old top of stack sn
top[sn] = i;
return true;
}
int pop(int sn) {
if (isEmpty(sn)) return -1;
int i = top[sn];
top[sn] = nxt[i]; // unlink the top slot
nxt[i] = freeTop; // give it back to the free list
freeTop = i;
return arr[i];
}
};
int main() {
KStacks s(10, 3);
int xs[] = {15, 45, 17, 39, 11}, sns[] = {0, 1, 0, 1, 2};
for (int i = 0; i < 5; i++) s.push(xs[i], sns[i]);
cout << "pop(0): " << s.pop(0) << "\n";
cout << "pop(1): " << s.pop(1) << "\n";
cout << "pop(2): " << s.pop(2) << "\n";
cout << "pop(0): " << s.pop(0) << "\n";
cout << "empty(2): " << (s.isEmpty(2) ? "true" : "false") << "\n";
cout << "empty(0): " << (s.isEmpty(0) ? "true" : "false") << "\n";
}import java.util.Arrays;
public class Main {
static class KStacks {
int[] arr, top, next;
int free;
KStacks(int n, int k) {
arr = new int[n];
top = new int[k];
Arrays.fill(top, -1);
next = new int[n];
for (int i = 0; i < n; i++) next[i] = i + 1; // free list: slot i → slot i+1
next[n - 1] = -1;
free = 0;
}
boolean isFull() { return free == -1; }
boolean isEmpty(int sn) { return top[sn] == -1; }
boolean push(int x, int sn) {
if (isFull()) return false;
int i = free;
free = next[i]; // take the slot off the free list
arr[i] = x;
next[i] = top[sn]; // link it above the old top of stack sn
top[sn] = i;
return true;
}
int pop(int sn) {
if (isEmpty(sn)) return -1;
int i = top[sn];
top[sn] = next[i]; // unlink the top slot
next[i] = free; // give it back to the free list
free = i;
return arr[i];
}
}
public static void main(String[] args) {
KStacks s = new KStacks(10, 3);
int[] xs = {15, 45, 17, 39, 11}, sns = {0, 1, 0, 1, 2};
for (int i = 0; i < 5; i++) s.push(xs[i], sns[i]);
System.out.println("pop(0): " + s.pop(0));
System.out.println("pop(1): " + s.pop(1));
System.out.println("pop(2): " + s.pop(2));
System.out.println("pop(0): " + s.pop(0));
System.out.println("empty(2): " + s.isEmpty(2));
System.out.println("empty(0): " + s.isEmpty(0));
}
}class KStacks {
constructor(n, k) {
this.arr = new Array(n);
this.top = new Array(k).fill(-1); // top[sn] = index of the top of stack sn
this.next = Array.from({ length: n }, (_, i) => i + 1); // free list: slot i → slot i+1
this.next[n - 1] = -1;
this.free = 0; // first free slot
}
isFull() { return this.free === -1; }
isEmpty(sn) { return this.top[sn] === -1; }
push(x, sn) {
if (this.isFull()) return false;
const i = this.free;
this.free = this.next[i]; // take the slot off the free list
this.arr[i] = x;
this.next[i] = this.top[sn]; // link it above the old top of stack sn
this.top[sn] = i;
return true;
}
pop(sn) {
if (this.isEmpty(sn)) return null;
const i = this.top[sn];
this.top[sn] = this.next[i]; // unlink the top slot
this.next[i] = this.free; // give it back to the free list
this.free = i;
return this.arr[i];
}
}
const s = new KStacks(10, 3);
for (const [x, sn] of [[15, 0], [45, 1], [17, 0], [39, 1], [11, 2]]) s.push(x, sn);
console.log("pop(0):", s.pop(0));
console.log("pop(1):", s.pop(1));
console.log("pop(2):", s.pop(2));
console.log("pop(0):", s.pop(0));
console.log("empty(2):", s.isEmpty(2));
console.log("empty(0):", s.isEmpty(0));pop(0): 17
pop(1): 39
pop(2): 11
pop(0): 15
empty(2): true
empty(0): trueTime O(1) per operation · Space O(n + k) — arr and next of size n, top of size k
Stock span problem
The span of a stock's price on day i is the number of consecutive days ending at i (including i) on which the price was less than or equal to price[i]. Day 4 (price 16) has span 5 because all of 13, 15, 12, 14 are below 16; day 8 (price 10) has span 4 because 8, 6, 4 are below it but 16 stops the run.
def stock_span_naive(price):
span = []
for i in range(len(price)):
j = i - 1
while j >= 0 and price[j] <= price[i]: # walk back while prices are not higher
j -= 1
span.append(i - j)
return span
print(*stock_span_naive([13, 15, 12, 14, 16, 8, 6, 4, 10, 30]))1 2 1 2 5 1 1 1 4 10def stock_span(price):
st = [] # indices; prices strictly decreasing bottom → top
span = [0] * len(price)
for i in range(len(price)):
while st and price[st[-1]] <= price[i]: # those days can never be a previous greater again
st.pop()
span[i] = i + 1 if not st else i - st[-1]
st.append(i)
return span
print(*stock_span([13, 15, 12, 14, 16, 8, 6, 4, 10, 30]))#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> stockSpan(const vector<int>& price) {
int n = price.size();
vector<int> span(n);
stack<int> st; // indices; prices strictly decreasing bottom → top
for (int i = 0; i < n; i++) {
while (!st.empty() && price[st.top()] <= price[i]) st.pop(); // dead candidates
span[i] = st.empty() ? i + 1 : i - st.top();
st.push(i);
}
return span;
}
int main() {
vector<int> price = {13, 15, 12, 14, 16, 8, 6, 4, 10, 30};
for (int s : stockSpan(price)) cout << s << " ";
cout << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static int[] stockSpan(int[] price) {
int n = price.length;
int[] span = new int[n];
Deque<Integer> st = new ArrayDeque<>(); // indices; prices strictly decreasing bottom → top
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && price[st.peek()] <= price[i]) st.pop(); // dead candidates
span[i] = st.isEmpty() ? i + 1 : i - st.peek();
st.push(i);
}
return span;
}
public static void main(String[] args) {
int[] price = {13, 15, 12, 14, 16, 8, 6, 4, 10, 30};
StringBuilder sb = new StringBuilder();
for (int s : stockSpan(price)) sb.append(s).append(' ');
System.out.println(sb.toString().trim());
}
}function stockSpan(price) {
const st = []; // indices; prices strictly decreasing bottom → top
const span = new Array(price.length);
for (let i = 0; i < price.length; i++) {
while (st.length && price[st[st.length - 1]] <= price[i]) st.pop(); // dead candidates
span[i] = st.length === 0 ? i + 1 : i - st[st.length - 1];
st.push(i);
}
return span;
}
console.log(stockSpan([13, 15, 12, 14, 16, 8, 6, 4, 10, 30]).join(" "));1 2 1 2 5 1 1 1 4 10Time O(n) · Space O(n)
Previous greater element
For every element, the nearest element to its left that is strictly greater; -1 if there is none. This is the pattern from the overview section in its purest form — the trace table above is exactly this input.
def previous_greater_naive(arr):
res = []
for i in range(len(arr)):
pg = -1
for j in range(i - 1, -1, -1): # scan left until something bigger
if arr[j] > arr[i]:
pg = arr[j]
break
res.append(pg)
return res
print(*previous_greater_naive([15, 10, 18, 12, 4, 6, 2, 8]))-1 15 -1 18 12 12 6 12def previous_greater(arr):
st = [] # values; strictly decreasing bottom → top
res = []
for x in arr:
while st and st[-1] <= x: # smaller-or-equal elements can never be an answer again
st.pop()
res.append(-1 if not st else st[-1])
st.append(x)
return res
print(*previous_greater([15, 10, 18, 12, 4, 6, 2, 8]))#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> previousGreater(const vector<int>& arr) {
stack<int> st; // values; strictly decreasing bottom → top
vector<int> res;
for (int x : arr) {
while (!st.empty() && st.top() <= x) st.pop(); // can never be an answer again
res.push_back(st.empty() ? -1 : st.top());
st.push(x);
}
return res;
}
int main() {
for (int v : previousGreater({15, 10, 18, 12, 4, 6, 2, 8})) cout << v << " ";
cout << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static int[] previousGreater(int[] arr) {
Deque<Integer> st = new ArrayDeque<>(); // values; strictly decreasing bottom → top
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
while (!st.isEmpty() && st.peek() <= arr[i]) st.pop(); // can never be an answer again
res[i] = st.isEmpty() ? -1 : st.peek();
st.push(arr[i]);
}
return res;
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
for (int v : previousGreater(new int[]{15, 10, 18, 12, 4, 6, 2, 8})) sb.append(v).append(' ');
System.out.println(sb.toString().trim());
}
}function previousGreater(arr) {
const st = []; // values; strictly decreasing bottom → top
const res = [];
for (const x of arr) {
while (st.length && st[st.length - 1] <= x) st.pop(); // can never be an answer again
res.push(st.length === 0 ? -1 : st[st.length - 1]);
st.push(x);
}
return res;
}
console.log(previousGreater([15, 10, 18, 12, 4, 6, 2, 8]).join(" "));-1 15 -1 18 12 12 6 12Time O(n) · Space O(n)
Next greater element
Mirror image: for every element, the nearest strictly greater element to its right, -1 if none. (The original notes listed seven answers for six inputs — the correct output has one answer per element.)
def next_greater_naive(arr):
res = []
for i in range(len(arr)):
ng = -1
for j in range(i + 1, len(arr)):
if arr[j] > arr[i]:
ng = arr[j]
break
res.append(ng)
return res
print(*next_greater_naive([5, 15, 10, 8, 12, 7]))15 -1 12 12 -1 -1def next_greater(arr):
n = len(arr)
st = [] # values to the right of i; strictly decreasing bottom → top
res = [-1] * n
for i in range(n - 1, -1, -1): # right to left
while st and st[-1] <= arr[i]:
st.pop()
res[i] = -1 if not st else st[-1]
st.append(arr[i])
return res
print(*next_greater([5, 15, 10, 8, 12, 7]))#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> nextGreater(const vector<int>& arr) {
int n = arr.size();
stack<int> st; // values to the right of i; strictly decreasing bottom → top
vector<int> res(n, -1);
for (int i = n - 1; i >= 0; i--) { // right to left
while (!st.empty() && st.top() <= arr[i]) st.pop();
res[i] = st.empty() ? -1 : st.top();
st.push(arr[i]);
}
return res;
}
int main() {
for (int v : nextGreater({5, 15, 10, 8, 12, 7})) cout << v << " ";
cout << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static int[] nextGreater(int[] arr) {
int n = arr.length;
Deque<Integer> st = new ArrayDeque<>(); // values to the right of i; strictly decreasing
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) { // right to left
while (!st.isEmpty() && st.peek() <= arr[i]) st.pop();
res[i] = st.isEmpty() ? -1 : st.peek();
st.push(arr[i]);
}
return res;
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
for (int v : nextGreater(new int[]{5, 15, 10, 8, 12, 7})) sb.append(v).append(' ');
System.out.println(sb.toString().trim());
}
}function nextGreater(arr) {
const n = arr.length;
const st = []; // values to the right of i; strictly decreasing bottom → top
const res = new Array(n).fill(-1);
for (let i = n - 1; i >= 0; i--) { // right to left
while (st.length && st[st.length - 1] <= arr[i]) st.pop();
res[i] = st.length === 0 ? -1 : st[st.length - 1];
st.push(arr[i]);
}
return res;
}
console.log(nextGreater([5, 15, 10, 8, 12, 7]).join(" "));15 -1 12 12 -1 -1Time O(n) · Space O(n)
Largest rectangular area in a histogram
■ ■
■ ■ ■ ■
■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ largest rectangle: height 5 over bars 5,6 → 10
6 2 5 4 1 5 6Every bar is the shortest bar of exactly one maximal rectangle: the one that extends from the previous smaller bar to the next smaller bar. So the answer is max over i of heights[i] × (nextSmaller[i] − prevSmaller[i] − 1). The problem is finding both boundaries fast — which is the monotonic stack again, this time the smaller variants.
def max_area_naive(h):
best = 0
for i in range(len(h)):
width = 1
j = i - 1
while j >= 0 and h[j] >= h[i]: # extend left while bars are at least as tall
width += 1
j -= 1
j = i + 1
while j < len(h) and h[j] >= h[i]: # extend right
width += 1
j += 1
best = max(best, h[i] * width)
return best
print(max_area_naive([6, 2, 5, 4, 1, 5, 6]))10def prev_smaller(h):
st, res = [], [-1] * len(h)
for i in range(len(h)):
while st and h[st[-1]] >= h[i]:
st.pop()
res[i] = st[-1] if st else -1 # -1 = no smaller bar on the left
st.append(i)
return res
def next_smaller(h):
n = len(h)
st, res = [], [n] * n
for i in range(n - 1, -1, -1):
while st and h[st[-1]] >= h[i]:
st.pop()
res[i] = st[-1] if st else n # n = no smaller bar on the right
st.append(i)
return res
def max_area_two_pass(h):
ps, ns = prev_smaller(h), next_smaller(h)
return max(h[i] * (ns[i] - ps[i] - 1) for i in range(len(h)))
h = [6, 2, 5, 4, 1, 5, 6]
print(*prev_smaller(h))
print(*next_smaller(h))
print(max_area_two_pass(h))-1 -1 1 1 -1 4 5
1 4 3 4 7 7 7
10def max_histogram_area(h):
n = len(h)
st = [] # indices; heights increasing bottom → top
best = 0
for i in range(n + 1):
cur = h[i] if i < n else 0 # a 0-high bar at the end flushes the stack
while st and h[st[-1]] >= cur:
top = st.pop() # i is the next smaller of bar `top`
left = st[-1] if st else -1 # the bar below is its previous smaller
best = max(best, h[top] * (i - left - 1))
st.append(i)
return best
print(max_histogram_area([6, 2, 5, 4, 1, 5, 6]))#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int maxHistogramArea(const vector<int>& h) {
int n = h.size();
stack<int> st; // indices; heights increasing bottom → top
int best = 0;
for (int i = 0; i <= n; i++) {
int cur = i < n ? h[i] : 0; // a 0-high bar at the end flushes the stack
while (!st.empty() && h[st.top()] >= cur) {
int top = st.top(); st.pop(); // i is the next smaller of bar `top`
int left = st.empty() ? -1 : st.top(); // the bar below is its previous smaller
best = max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}
int main() {
cout << maxHistogramArea({6, 2, 5, 4, 1, 5, 6}) << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static int maxHistogramArea(int[] h) {
int n = h.length;
Deque<Integer> st = new ArrayDeque<>(); // indices; heights increasing bottom → top
int best = 0;
for (int i = 0; i <= n; i++) {
int cur = i < n ? h[i] : 0; // a 0-high bar at the end flushes the stack
while (!st.isEmpty() && h[st.peek()] >= cur) {
int top = st.pop(); // i is the next smaller of bar `top`
int left = st.isEmpty() ? -1 : st.peek(); // the bar below is its previous smaller
best = Math.max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}
public static void main(String[] args) {
System.out.println(maxHistogramArea(new int[]{6, 2, 5, 4, 1, 5, 6}));
}
}function maxHistogramArea(h) {
const n = h.length;
const st = []; // indices; heights increasing bottom → top
let best = 0;
for (let i = 0; i <= n; i++) {
const cur = i < n ? h[i] : 0; // a 0-high bar at the end flushes the stack
while (st.length && h[st[st.length - 1]] >= cur) {
const top = st.pop(); // i is the next smaller of bar `top`
const left = st.length ? st[st.length - 1] : -1; // the bar below is its previous smaller
best = Math.max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}
console.log(maxHistogramArea([6, 2, 5, 4, 1, 5, 6]));10Time O(n) · Space O(n)
Largest rectangle with all 1s in a binary matrix
Naive: take every cell as a top-left corner, try every width and height, check that the rectangle contains only 1s — O(R³C³) or O(R²C²) with prefix sums. The efficient solution reuses the histogram algorithm row by row.
matrix height[] after each row best histogram area
0 1 1 0 0 1 1 0 2
1 1 1 1 1 2 2 1 4
1 1 1 1 2 3 3 2 8 ← 4 columns × height 2
1 1 0 0 3 4 0 0 6def max_histogram_area(h):
st, best = [], 0
for i in range(len(h) + 1):
cur = h[i] if i < len(h) else 0
while st and h[st[-1]] >= cur:
top = st.pop()
left = st[-1] if st else -1
best = max(best, h[top] * (i - left - 1))
st.append(i)
return best
def max_rectangle_of_ones(mat):
if not mat:
return 0
cols = len(mat[0])
height = [0] * cols
best = 0
for row in mat:
for j in range(cols):
height[j] = height[j] + 1 if row[j] == 1 else 0 # grow the bar or reset it
best = max(best, max_histogram_area(height)) # best rectangle ending on this row
return best
mat = [[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 0, 0]]
print(max_rectangle_of_ones(mat))#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int maxHistogramArea(const vector<int>& h) {
int n = h.size(), best = 0;
stack<int> st;
for (int i = 0; i <= n; i++) {
int cur = i < n ? h[i] : 0;
while (!st.empty() && h[st.top()] >= cur) {
int top = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
best = max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}
int maxRectangleOfOnes(const vector<vector<int>>& mat) {
if (mat.empty()) return 0;
int cols = mat[0].size(), best = 0;
vector<int> height(cols, 0);
for (const auto& row : mat) {
for (int j = 0; j < cols; j++)
height[j] = row[j] == 1 ? height[j] + 1 : 0; // grow the bar or reset it
best = max(best, maxHistogramArea(height)); // best rectangle ending on this row
}
return best;
}
int main() {
vector<vector<int>> mat = {{0, 1, 1, 0},
{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 1, 0, 0}};
cout << maxRectangleOfOnes(mat) << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static int maxHistogramArea(int[] h) {
int n = h.length, best = 0;
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
int cur = i < n ? h[i] : 0;
while (!st.isEmpty() && h[st.peek()] >= cur) {
int top = st.pop();
int left = st.isEmpty() ? -1 : st.peek();
best = Math.max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}
static int maxRectangleOfOnes(int[][] mat) {
if (mat.length == 0) return 0;
int cols = mat[0].length, best = 0;
int[] height = new int[cols];
for (int[] row : mat) {
for (int j = 0; j < cols; j++)
height[j] = row[j] == 1 ? height[j] + 1 : 0; // grow the bar or reset it
best = Math.max(best, maxHistogramArea(height)); // best rectangle ending on this row
}
return best;
}
public static void main(String[] args) {
int[][] mat = {{0, 1, 1, 0},
{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 1, 0, 0}};
System.out.println(maxRectangleOfOnes(mat));
}
}function maxHistogramArea(h) {
const st = [];
let best = 0;
for (let i = 0; i <= h.length; i++) {
const cur = i < h.length ? h[i] : 0;
while (st.length && h[st[st.length - 1]] >= cur) {
const top = st.pop();
const left = st.length ? st[st.length - 1] : -1;
best = Math.max(best, h[top] * (i - left - 1));
}
st.push(i);
}
return best;
}
function maxRectangleOfOnes(mat) {
if (mat.length === 0) return 0;
const cols = mat[0].length;
const height = new Array(cols).fill(0);
let best = 0;
for (const row of mat) {
for (let j = 0; j < cols; j++)
height[j] = row[j] === 1 ? height[j] + 1 : 0; // grow the bar or reset it
best = Math.max(best, maxHistogramArea(height)); // best rectangle ending on this row
}
return best;
}
const mat = [[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 0, 0]];
console.log(maxRectangleOfOnes(mat));8Time O(R × C) · Space O(C) for the height array (plus the stack)
Design a stack with getMin() in O(1) — auxiliary stack
Naive: keep an ordinary stack and compute min(stack) on demand — getMin() becomes O(n). The requirement is O(1) for every operation including getMin().
operation main stack mins stack getMin()
push(20) [20] [20] 20
push(10) [20, 10] [20, 10] 10
push(5) [20, 10, 5] [20, 10, 5] 5
push(12) [20, 10, 5, 12] [20, 10, 5, 5] 5 ← 12 does not lower the min, so 5 is repeated
pop() [20, 10, 5] [20, 10, 5] 5
pop() [20, 10] [20, 10] 10class MinStack:
def __init__(self):
self.main = []
self.mins = [] # mins[i] = min of main[0..i]
def push(self, x):
self.main.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop() # the two stacks always move together
return self.main.pop()
def top(self):
return self.main[-1]
def get_min(self):
return self.mins[-1]
s = MinStack()
s.push(20)
s.push(10)
print("getMin:", s.get_min())
s.push(5)
print("getMin:", s.get_min())
print("pop:", s.pop())
print("getMin:", s.get_min())
print("pop:", s.pop())
print("getMin:", s.get_min())#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
class MinStack {
stack<int> main_, mins; // mins.top() = min of everything in main_
public:
void push(int x) {
main_.push(x);
mins.push(mins.empty() ? x : min(x, mins.top()));
}
int pop() {
int x = main_.top();
main_.pop();
mins.pop(); // the two stacks always move together
return x;
}
int top() const { return main_.top(); }
int getMin() const { return mins.top(); }
};
int main() {
MinStack s;
s.push(20);
s.push(10);
cout << "getMin: " << s.getMin() << "\n";
s.push(5);
cout << "getMin: " << s.getMin() << "\n";
cout << "pop: " << s.pop() << "\n";
cout << "getMin: " << s.getMin() << "\n";
cout << "pop: " << s.pop() << "\n";
cout << "getMin: " << s.getMin() << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class MinStack {
Deque<Integer> main = new ArrayDeque<>();
Deque<Integer> mins = new ArrayDeque<>(); // mins.peek() = min of everything in main
void push(int x) {
main.push(x);
mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
}
int pop() {
mins.pop(); // the two stacks always move together
return main.pop();
}
int top() { return main.peek(); }
int getMin() { return mins.peek(); }
}
public static void main(String[] args) {
MinStack s = new MinStack();
s.push(20);
s.push(10);
System.out.println("getMin: " + s.getMin());
s.push(5);
System.out.println("getMin: " + s.getMin());
System.out.println("pop: " + s.pop());
System.out.println("getMin: " + s.getMin());
System.out.println("pop: " + s.pop());
System.out.println("getMin: " + s.getMin());
}
}class MinStack {
constructor() {
this.main = [];
this.mins = []; // mins[i] = min of main[0..i]
}
push(x) {
this.main.push(x);
this.mins.push(this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x);
}
pop() {
this.mins.pop(); // the two stacks always move together
return this.main.pop();
}
top() { return this.main[this.main.length - 1]; }
getMin() { return this.mins[this.mins.length - 1]; }
}
const s = new MinStack();
s.push(20);
s.push(10);
console.log("getMin:", s.getMin());
s.push(5);
console.log("getMin:", s.getMin());
console.log("pop:", s.pop());
console.log("getMin:", s.getMin());
console.log("pop:", s.pop());
console.log("getMin:", s.getMin());getMin: 10
getMin: 5
pop: 5
getMin: 10
pop: 10
getMin: 20Time O(1) per operation · Space O(n) extra for the mins stack
Design a stack with getMin() in O(1) extra space
The auxiliary stack stores one number per element. Can we do it with a single extra variable minEle? Yes — by storing an encoded value instead of x whenever x becomes the new minimum. The encoded value remembers the previous minimum, so pop() can restore it.
| Operation | Condition | Do |
|---|---|---|
push(x) | stack empty | push x; minEle = x |
push(x) | x >= minEle | push x as is |
push(x) | x < minEle | push 2x − minEle (encoded); minEle = x |
pop() | top >= minEle | return top |
pop() | top < minEle | the real value is minEle; restore minEle = 2·minEle − top; return the old minEle |
top() | top < minEle | return minEle, else the stored value |
getMin() | — | return minEle |
operation stored stack minEle note
push(20) [20] 20
push(10) [20, 0] 10 10 < 20 → store 2·10 − 20 = 0
push(5) [20, 0, 0] 5 5 < 10 → store 2·5 − 10 = 0
pop() [20, 0] 10 top 0 < minEle 5 → real value 5; minEle = 2·5 − 0 = 10
pop() [20] 20 top 0 < minEle 10 → real value 10; minEle = 2·10 − 0 = 20class MinStack:
def __init__(self):
self.st = []
self.min_ele = None
def push(self, x):
if not self.st:
self.st.append(x)
self.min_ele = x
elif x < self.min_ele:
self.st.append(2 * x - self.min_ele) # encoded: always < x < new min
self.min_ele = x
else:
self.st.append(x)
def pop(self):
top = self.st.pop()
if top < self.min_ele: # encoded entry: it *was* the minimum
real = self.min_ele
self.min_ele = 2 * self.min_ele - top # restore the previous minimum
return real
return top
def top(self):
t = self.st[-1]
return self.min_ele if t < self.min_ele else t
def get_min(self):
return self.min_ele
s = MinStack()
s.push(20)
s.push(10)
print("getMin:", s.get_min())
s.push(5)
print("getMin:", s.get_min())
print("pop:", s.pop())
print("getMin:", s.get_min())
print("pop:", s.pop())
print("getMin:", s.get_min())
print("--- negatives ---")
s = MinStack()
for x in (-2, 0, -3):
s.push(x)
print("getMin:", s.get_min())
print("pop:", s.pop())
print("getMin:", s.get_min())
print("top:", s.top())#include <iostream>
#include <stack>
using namespace std;
class MinStack {
stack<long long> st; // long long: 2x - minEle can exceed the int range
long long minEle = 0;
public:
void push(long long x) {
if (st.empty()) {
st.push(x);
minEle = x;
} else if (x < minEle) {
st.push(2 * x - minEle); // encoded: always < x < new min
minEle = x;
} else {
st.push(x);
}
}
long long pop() {
long long top = st.top();
st.pop();
if (top < minEle) { // encoded entry: it *was* the minimum
long long real = minEle;
minEle = 2 * minEle - top; // restore the previous minimum
return real;
}
return top;
}
long long top() const {
long long t = st.top();
return t < minEle ? minEle : t;
}
long long getMin() const { return minEle; }
};
int main() {
MinStack s;
s.push(20);
s.push(10);
cout << "getMin: " << s.getMin() << "\n";
s.push(5);
cout << "getMin: " << s.getMin() << "\n";
cout << "pop: " << s.pop() << "\n";
cout << "getMin: " << s.getMin() << "\n";
cout << "pop: " << s.pop() << "\n";
cout << "getMin: " << s.getMin() << "\n";
cout << "--- negatives ---\n";
MinStack t;
for (long long x : {-2, 0, -3}) t.push(x);
cout << "getMin: " << t.getMin() << "\n";
cout << "pop: " << t.pop() << "\n";
cout << "getMin: " << t.getMin() << "\n";
cout << "top: " << t.top() << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class MinStack {
Deque<Long> st = new ArrayDeque<>(); // long: 2x - minEle can exceed the int range
long minEle;
void push(long x) {
if (st.isEmpty()) {
st.push(x);
minEle = x;
} else if (x < minEle) {
st.push(2 * x - minEle); // encoded: always < x < new min
minEle = x;
} else {
st.push(x);
}
}
long pop() {
long top = st.pop();
if (top < minEle) { // encoded entry: it *was* the minimum
long real = minEle;
minEle = 2 * minEle - top; // restore the previous minimum
return real;
}
return top;
}
long top() {
long t = st.peek();
return t < minEle ? minEle : t;
}
long getMin() { return minEle; }
}
public static void main(String[] args) {
MinStack s = new MinStack();
s.push(20);
s.push(10);
System.out.println("getMin: " + s.getMin());
s.push(5);
System.out.println("getMin: " + s.getMin());
System.out.println("pop: " + s.pop());
System.out.println("getMin: " + s.getMin());
System.out.println("pop: " + s.pop());
System.out.println("getMin: " + s.getMin());
System.out.println("--- negatives ---");
MinStack t = new MinStack();
for (long x : new long[]{-2, 0, -3}) t.push(x);
System.out.println("getMin: " + t.getMin());
System.out.println("pop: " + t.pop());
System.out.println("getMin: " + t.getMin());
System.out.println("top: " + t.top());
}
}class MinStack {
constructor() {
this.st = [];
this.minEle = null;
}
push(x) {
if (this.st.length === 0) {
this.st.push(x);
this.minEle = x;
} else if (x < this.minEle) {
this.st.push(2 * x - this.minEle); // encoded: always < x < new min
this.minEle = x;
} else {
this.st.push(x);
}
}
pop() {
const top = this.st.pop();
if (top < this.minEle) { // encoded entry: it *was* the minimum
const real = this.minEle;
this.minEle = 2 * this.minEle - top; // restore the previous minimum
return real;
}
return top;
}
top() {
const t = this.st[this.st.length - 1];
return t < this.minEle ? this.minEle : t;
}
getMin() { return this.minEle; }
}
let s = new MinStack();
s.push(20);
s.push(10);
console.log("getMin:", s.getMin());
s.push(5);
console.log("getMin:", s.getMin());
console.log("pop:", s.pop());
console.log("getMin:", s.getMin());
console.log("pop:", s.pop());
console.log("getMin:", s.getMin());
console.log("--- negatives ---");
s = new MinStack();
for (const x of [-2, 0, -3]) s.push(x);
console.log("getMin:", s.getMin());
console.log("pop:", s.pop());
console.log("getMin:", s.getMin());
console.log("top:", s.top());getMin: 10
getMin: 5
pop: 5
getMin: 10
pop: 10
getMin: 20
--- negatives ---
getMin: -3
pop: -3
getMin: -2
top: 0Time O(1) per operation · Space O(1) extra — one variable besides the stack
Why 2x − minEle works. Let m be the old minimum and x < m the new one. The stored value is e = 2x − m = x − (m − x) < x. Since the new minEle is x, the stored e is below minEle, which is how pop() recognises it. Reversing: 2·minEle − e = 2x − (2x − m) = m, the old minimum. Negative numbers need no special handling — the algebra never relied on signs, only on x < m. The original notes repeated the same class under Handling negatives; the -2, 0, -3 driver above shows it works unchanged.
Interview Q&A
When should I reach for a monotonic stack?
Previous greater vs next greater: what actually changes in the code?
Why is the histogram problem O(n) when each bar may pop many others?
How does the k-stacks structure differ from just using k dynamic arrays?
Is the O(1)-space getMin() trick safe in production code?
How would you find the next greater element for a circular array?