Learn�DSA�Stacks & Queues

Lesson 4 � Intermediate

Next Greater Element Problems

Next Greater Element (NGE) monotonic stack ka sabse popular application hai. Har element ke liye usse right mein pehla bada element find karna � ye problem interview mein baar baar aati hai. Is lesson mein NGE, circular variant, stock span, aur trapping rain water ka connection dekhenge.

? 25 min✓ Intermediate✓ Monotonic stack

NGE Problem kya hai?

WHAT

Next Greater Element mein har element ke liye usse right mein pehla bada element find karna hai. Agar koi bada nahi hai toh -1 return karna hai. Brute force O(n�) hai � har element ke liye aage dekho. Monotonic stack se O(n) ho jaata hai.

WHEN

Jab array mein har element ke liye "next bigger" find karna ho. Stock prices mein "kab price badha", temperature mein "kab garmi badhi", histogram mein "next bada pillar" � ye sab NGE variants hain.

WHERE

LeetCode 496 (NGE I), 503 (NGE II Circular), 739 (Daily Temperatures), 496 (Stock Span), 84 (Largest Rectangle), 42 (Trapping Rain Water) � ye sab NGE based hain.

Core Idea: Stack mein un elements ko rakho jinka NGE abhi nahi mila. Jab bada element aaye toh stack ke un sab elements ko bata do ki unka NGE mil gaya. Jo elements stack mein reh gaye � unka koi bada nahi hai.

NGE I � Basic Problem

Pehla basic NGE problem dekhte hain � given array, har element ka next greater element find karo:

# Next Greater Element I
# nums1 = subset of nums2, har nums1 element ka NGE nums2 mein find karo

def next_greater_element(nums1, nums2):
 nge_map = {}
 stack = []
 
 # Pehle nums2 ke liye NGE map banao
 for num in nums2:
 while stack and stack[-1] < num:
 nge_map[stack.pop()] = num
 stack.append(num)
 
 # Ab nums1 ke liye map se answer nikalo
 return [nge_map.get(num, -1) for num in nums1]

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(next_greater_element(nums1, nums2)) # [-1, 3, -1]

# nums2 mein: 1?3, 3?4, 4?-1, 2?-1
# nums1 mein: 4?-1, 1?3, 2?-1
# NGE II � Basic approach (no map, direct array)
def next_greater_elements(arr):
 n = len(arr)
 result = [-1] * n
 stack = [] # indices
 
 for i in range(n):
 while stack and arr[stack[-1]] < arr[i]:
 idx = stack.pop()
 result[idx] = arr[i]
 stack.append(i)
 
 return result

arr = [4, 5, 2, 25]
print(next_greater_elements(arr)) # [5, 25, 25, -1]

NGE II � Circular Array Variant

Circular array mein last element ka NGE pehla element ho sakta hai. Isko handle karne ke liye array ko 2 baar traverse karo (ya modulo use karo):

# Next Greater Element II � Circular Array
# Array circular hai � last ke baad first aata hai

def next_greater_circular(nums):
 n = len(nums)
 result = [-1] * n
 stack = [] # indices
 
 # 2n iterations � circular array simulate karo
 for i in range(2 * n):
 while stack and nums[stack[-1]] < nums[i % n]:
 idx = stack.pop()
 result[idx] = nums[i % n]
 if i < n: # sirf pehle n elements push karo
 stack.append(i)
 
 return result

arr = [1, 2, 1]
print(next_greater_circular(arr)) # [2, -1, 2]

# arr circular hai: [1, 2, 1, 1, 2, 1, ...]
# arr[0]=1, arr[1]=2 (bada mila)
# arr[1]=2, koi bada nahi
# arr[2]=1, arr[3%3]=arr[0]=1, arr[4%3]=arr[1]=2 (bada mila!)
Circular Trick: for i in range(2 * n) se array effectively 2 baar repeat hota hai. nums[i % n] se circular index milta hai. Sirf pehle n elements ko stack mein push karo � baaki sirf check karo.

Stock Span Problem

Stock span mein tumhe har din ke liye wo number of consecutive days find karna hai jisme price us din se kam ya barabar ho. Ye NGE ka variation hai:

# Stock Span Problem
# Har din ke liye kitne consecutive days hain jinme price <= current price

def stock_span(prices):
 n = len(prices)
 span = [1] * n # minimum span = 1 (khud)
 stack = [] # indices of prices we're tracking
 
 for i in range(n):
 while stack and prices[stack[-1]] <= prices[i]:
 stack.pop()
 span[i] = i - stack[-1] if stack else i + 1
 stack.append(i)
 
 return span

prices = [100, 80, 60, 70, 60, 75, 85]
print(stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]

# Day 0: span=1 (khud)
# Day 1: 80 < 100, span=1
# Day 2: 60 < 80, span=1
# Day 3: 70 > 60, span=2 (day 2 + khud)
# Day 4: 60 < 70, span=1
# Day 5: 75 > 60,70,60, span=4 (days 2,3,4 + khud)
# Day 6: 85 > 75,70,60,80, span=6 (days 1-5 + khud)
Stock Span = NGE with distance: Stock span mein hum "previous greater element" find karte hain (left mein pehla bada). Span = current index - previous greater index. Agar previous greater nahi hai toh span = current index + 1.

Trapping Rain Water Connection

Trapping Rain Water bhi monotonic stack se solve hota hai � ye NGE ka advanced application hai:

# Trapping Rain Water � Monotonic Stack Approach
# Har pillar ke liye left max aur right max find karo

def trap(height):
 if not height:
 return 0
 
 stack = []
 water = 0
 
 for i in range(len(height)):
 while stack and height[stack[-1]] < height[i]:
 bottom = stack.pop()
 if not stack:
 break
 width = i - stack[-1] - 1
 bounded_height = min(height[i], height[stack[-1]]) - height[bottom]
 water += width * bounded_height
 stack.append(i)
 
 return water

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(height)) # 6

# Visual: water trapped between pillars
# Index: 0 1 2 3 4 5 6 7 8 9 10 11
# Height: 0 1 0 2 1 0 1 3 2 1 2 1
# Water: 0 0 1 0 1 2 1 0 0 1 0 0
# Total trapped water = 6 units

Try it: code khud likho




Exercise




Question: Circular array [1, 2, 3, 4, 3] ke liye Next Greater Element find karo. Answer mein NGE array likho (comma-separated, jaise "2,3,4,-1,4").











Question: Stock prices [100, 80, 60, 70, 60, 75, 85] ke liye stock span find karo. Answer mein span array likho (comma-separated, jaise "1,1,1,2,1,4,6").









Common mistakes




Lesson complete?
NGE problems samajh aa gayi✓ Ab Valid Parentheses dekhte hain � stack ka sabse classic interview problem!