Lesson 5 — Advanced

Top Greedy Problems

Greedy problems interview mein bahut puchhe jaate hain. Inhe pattern se samjho — har problem ka ek greedy insight hota hai jo tumhe dhoondni hai. Aaj 10 most asked problems cover karenge.

Greedy Problem Patterns

Sare greedy problems kuch patterns follow karte hain:

• Sorting-based: Kuch property ke basis pe sort karo, phir greedy choice karo. (Activity Selection, Interval problems)
• Local vs Global: Har step pe locally best choice lo. (Jump Game, Gas Station)
• Counting/Frequency: Coins ya items ki frequency track karo. (Lemonade Change, Hand of Straights)
• Two-pointer: Do ends se iterate karo. (Container With Most Water)
• Mathematical Insight: Problem ka math formula dhoondo. (Candy, Task Scheduler)

1. Jump Game (LC 55)

Problem: Tum ek array mein ho jisme har index pe ek maximum jump length hai. Tum last index tak pahunch sakte ho ya nahi?

Greedy Insight: Har step pe maximum reach update karo. Agar current index > max_reach hai toh stuck ho.

def can_jump(nums):
 max_reach = 0
 for i, jump in enumerate(nums):
 if i > max_reach:
 return False
 max_reach = max(max_reach, i + jump)
 return True

# Example
print(can_jump([2,3,1,1,4])) # True
print(can_jump([3,2,1,0,4])) # False

2. Gas Station (LC 134)

Problem: Circular route pe gas stations hain. Har station pe gas milti hai aur next station tak fuel lagta hai. Ek starting point dhoondo jahan se circuit complete ho sake.

Greedy Insight: Agar total gas >= total cost hai toh solution hai. Start point wo hai jahan se tank kabhi empty nahi hota.

def can_complete_circuit(gas, cost):
 total_tank = 0
 current_tank = 0
 start = 0

 for i in range(len(gas)):
 total_tank += gas[i] - cost[i]
 current_tank += gas[i] - cost[i]

 if current_tank < 0:
 start = i + 1
 current_tank = 0

 return start if total_tank >= 0 else -1

3. Hand of Straights (LC 846)

Problem: Given array of card values, check karo ki kya tum groups of groupSize consecutive cards bana sakte ho.

Greedy Insight: Frequency count karo, sorted order mein iterate karo, har card ke liye consecutive group banao.

from collections import Counter

def is_n_straight_hand(hand, groupSize):
 if len(hand) % groupSize != 0:
 return False

 count = Counter(hand)
 for card in sorted(count):
 if count[card] > 0:
 need = count[card]
 for i in range(card, card + groupSize):
 if count[i] < need:
 return False
 count[i] -= need
 return True

4. Lemonade Change (LC 860)

Problem: Customers $5, $10, ya $20 bill se lemonade kharidte hain. Tumhe $5 se start karna hai. Change de sakte ho ya nahi?

Greedy Insight: Hamesha $10 ka change $5 se do, $20 ka change pehle $10+$5 try karo phir $5—3 try karo.

def lemonade_change(bills):
 five = ten = 0

 for bill in bills:
 if bill == 5:
 five += 1
 elif bill == 10:
 if five == 0:
 return False
 five -= 1
 ten += 1
 else: # bill == 20
 if ten > 0 and five > 0:
 ten -= 1
 five -= 1
 elif five >= 3:
 five -= 3
 else:
 return False
 return True

5. Partition Labels (LC 763)

Problem: String ko maximum partitions mein todo taaki har letter sirf ek partition mein ho. Return sizes of all partitions.

Greedy Insight: Pehle har letter ki last occurrence dhoondo. Har partition ka end current letter ki last occurrence tak hai.

def partition_labels(s):
 last = {c: i for i, c in enumerate(s)}
 result = []
 start = end = 0

 for i, c in enumerate(s):
 end = max(end, last[c])
 if i == end:
 result.append(end - start + 1)
 start = end + 1

 return result

6. Queue Reconstruction by Height (LC 406)

Problem: Logon ki list hai (height, taller count). Reconstruct karo queue jo valid ho.

Greedy Insight: Height ke descending order mein sort karo, phir apni position pe insert karo. Taller log pehle aa jaate hain toh position sahi rahega.

7. Task Scheduler (LC 621)

Problem: Tasks hain with cooldown period n. Minimum time lagega kitna?

Greedy Insight: Sabse frequent task pehle schedule karo, uske beech mein cooling slots mein baaki tasks daalo. Formula: max(len(tasks), (max_freq-1)*(n+1) + count_of_max_freq)

8. Candy (LC 135)

Problem: Children ko candies deni hain — har child ko at least 1 candy, aur agar rating zyada hai toh zyada candy. Minimum total candies?

Greedy Insight: Left-to-right pass: agar left child se bada hai toh left + 1. Right-to-left pass: agar right child se bada hai toh max(current, right + 1).

9. Minimum Number of Arrows (LC 452)

Problem: Balloons hain x-coordinates pe. Kitne arrows chahiye sabko burst karne ke liye?

Greedy Insight: End point pe sort karo. Agar next balloon start current end se pehle hai toh same arrow se burst hoga. Naya arrow tab jab start > current end.

10. Valid Parenthesis String (LC 678)

Problem: String mein '(', ')', '*' hain. '*' ko '(', ')', ya empty treat kar sakte ho. Valid parentheses string bana sakta hai ya nahi?

Greedy Insight: Do range track karo — min open aur max open brackets. ')' se min ghatto, '(' ya '*' se max badhao. Agar dono 0 se neeche jaayein toh invalid.

Try it: code khud likho

Common Mistakes

• Greedy ka proof na sochna — Interview mein jab greedy approach suggest karo, toh batao kyun ye kaam karta hai. Proof chahiye.
• Sorting ignore karna — Bahut saare greedy problems sorting se easy ho jaate hain. Pehle sort karne ka sochho.
• Edge cases na check karna — Empty array, single element, sab same elements — handle karo. Function shuru mein check karo if not arr: return.
• Greedy vs DP confuse karna — Agar greedy se wrong aa raha hai toh DP try karo. Coin change mein greedy kaam nahi karta.
• Frequency counting bhoolna — Hand of Straights, Lemonade Change jaise problems mein frequency count karna zaroori hai.
• Two-pass approach na samajhna — Candy problem mein ek pass se nahi hoga. Left-to-right phir right-to-left karo.