Lesson 3 — Intermediate

Monotonic Stack Pattern

Monotonic stack ek stack hai jo hamesha increasing ya decreasing order mein rehta hai. Ye pattern interview mein bahut powerful hai — Next Greater Element, Daily Temperatures, Stock Span — ye sab monotonic stack se O(n) mein solve hote hain jo brute force O(n—) hota hai.

? 25 min✓ Intermediate✓ Stack basics

Monotonic Stack kya hai?

WHAT

Monotonic stack ek stack hai jo hamesha ya toh strictly increasing order mein hota hai ya strictly decreasing. Jab naya element aata hai jo order todta hai, toh existing elements pop hote hain jab tak order restore na ho jaye. Isliye har element sirf ek baar push aur ek baar pop hota hai — total O(n).

WHEN

Jab tumhe "next greater/smaller element" ya "previous greater/smaller element" find karna ho. Jab array mein har element ke liye kisi condition ko satisfy karne wala nearest element dhundhna ho — monotonic stack try karo.

WHERE

Next Greater Element, Daily Temperatures, Stock Span, Trapping Rain Water, Largest Rectangle in Histogram — ye sab classic monotonic stack problems hain.

Key Insight: Monotonic stack tab useful hota hai jab tumhe har element ke liye kisi "nearest larger" ya "nearest smaller" element ki zaroorat hoti hai. Brute force mein har element ke liye aage peeche dekhte ho — O(n—). Monotonic stack mein ek baar array traverse karte ho — O(n).

Increasing vs Decreasing Stack

Do types ke monotonic stacks hain — dono samajh lo:

# DECREASING STACK (maintains decreasing order from bottom to top)
# Use karo jab "Next Greater Element" chahiye
# Stack mein chhote elements hote hain, bade aate hain toh chhote pop hote hain

stack = [] # decreasing: bottom se top tak decreasing
for i in range(n):
 while stack and arr[stack[-1]] < arr[i]:
 # arr[i] is the next greater element for arr[stack[-1]]
 idx = stack.pop()
 result[idx] = arr[i]
 stack.append(i)

# INCREASING STACK (maintains increasing order from bottom to top)
# Use karo jab "Next Smaller Element" chahiye
# Stack mein bade elements hote hain, chhote aate hain toh bade pop hote hain

stack = [] # increasing: bottom se top tak increasing
for i in range(n):
 while stack and arr[stack[-1]] > arr[i]:
 # arr[i] is the next smaller element for arr[stack[-1]]
 idx = stack.pop()
 result[idx] = arr[i]
 stack.append(i)

Decreasing Stack

Stack mein elements decreasing order mein hote hain. Jab bada element aata hai toh chhote pop hote hain. Use karo jab "next greater element" chahiye — pop hue elements ko bata do ki unka next greater mil gaya.

Increasing Stack

Stack mein elements increasing order mein hote hain. Jab chhota element aata hai toh bade pop hote hain. Use karo jab "next smaller element" chahiye — pop hue elements ko bata do ki unka next smaller mil gaya.

Pattern yaad rakho

Decreasing stack = "bada aaya toh chhote hato" = Next Greater Element ke liye. Increasing stack = "chhota aaya toh bade hato" = Next Smaller Element ke liye.

Step-by-Step: Decreasing Stack Example

Maan lo array [2, 1, 2, 4, 3] hai aur tumhe har element ka Next Greater Element find karna hai:

# arr = [2, 1, 2, 4, 3]
# Decreasing stack se NGE nikalo

arr = [2, 1, 2, 4, 3]
n = len(arr)
result = [-1] * n
stack = [] # indices store karenge

for i in range(n):
 # Jab tak current element stack ke top se bada hai
 while stack and arr[stack[-1]] < arr[i]:
 idx = stack.pop()
 result[idx] = arr[i] # arr[i] is NGE for arr[idx]
 stack.append(i)

print(result) # [2, 2, 4, -1, -1]

# Step by step walkthrough:
# i=0: stack=[], push 0 ✓ stack=[0]
# i=1: arr[0]=2 > arr[1]=1, push 1 ✓ stack=[0,1]
# i=2: arr[1]=1 < arr[2]=2, pop 1 ✓ result[1]=2; arr[0]=2 not < 2, push 2 ✓ stack=[0,2]
# i=3: arr[2]=2 < arr[3]=4, pop 2 ✓ result[2]=4; arr[0]=2 < 4, pop 0 ✓ result[0]=4; push 3 ✓ stack=[3]
# i=4: arr[3]=4 > arr[4]=3, push 4 ✓ stack=[3,4]
# Stack mein bache elements ka NGE = -1 (koi bada nahi mila)

Why O(n)? Har element sirf ek baar push hota hai aur ek baar pop hota hai. Total operations = 2n. Isliye time complexity O(n) hai — bahut efficient hai brute force O(n—) ke comparison mein.

Visual Walkthrough

Decreasing stack ka visual dekho — elements kaise push aur pop hote hain:

# arr = [2, 1, 2, 4, 3]
# Decreasing Stack Visual

# Step 1: i=0, arr[0]=2
# Stack: [2] (push 2)
# Result: [-1, -1, -1, -1, -1]

# Step 2: i=1, arr[1]=1
# 1 < 2, so 2 stays. Push 1.
# Stack: [2, 1] (decreasing order maintained)
# Result: [-1, -1, -1, -1, -1]

# Step 3: i=2, arr[2]=2
# 2 > 1, so 1 pops! ✓ result[1] = 2
# 2 == 2, so 2 stays. Push 2.
# Stack: [2, 2]
# Result: [-1, 2, -1, -1, -1]

# Step 4: i=3, arr[3]=4
# 4 > 2, so 2 pops! ✓ result[2] = 4
# 4 > 2, so 2 pops! ✓ result[0] = 4
# Push 4.
# Stack: [4]
# Result: [4, 2, 4, -1, -1]

# Step 5: i=4, arr[4]=3
# 3 < 4, so 4 stays. Push 3.
# Stack: [4, 3]
# Result: [4, 2, 4, -1, -1]

# Final: Stack mein bache [4, 3] ka koi bada nahi mila ? -1

Try it: code khud likho

Exercise

Question: Temperatures [73, 74, 75, 71, 69, 72, 76, 73] ke liye Daily Temperatures solve karo. Answer mein result array likho (comma-separated, jaise "1,1,4,2,1,1,0,0").

Question: Array [4, 5, 2, 25] ke liye Next Greater Element find karo using monotonic stack. Answer mein NGE array likho (comma-separated, jaise "5,25,25,-1").

Common mistakes

Stack mein value vs index: Hamesha stack mein index store karo, value nahi. Index se tum distance calculate kar sakte ho — i - stack[-1]. Value store karne se ye nahi hota.
Pop condition galat: Decreasing stack mein while stack and arr[stack[-1]] < arr[i] likho. Equal ya less than mein pop mat karo — strict comparison use karo unless problem specifically bole.
Stack empty check bhool jaana: while stack and ... mein pehle stack check karo. Agar stack empty hai toh stack[-1] error dega. Short-circuit evaluation se ye hota nahi but yaad rakhlo.
Brute force se shuru karna: Interview mein seedha O(n—) brute force mat do. Pehle monotonic stack approach socho — interviewer impressed hoga aur solution efficient hoga.

Lesson complete?

Monotonic Stack pattern samajh aa gaya✓ Ab Next Greater Element problems dekhte hain — ye monotonic stack ka sabse popular application hai.