Concept Notes — Greedy Math Tricks (লোভের পেছনের যুক্তি)¶
Greedy-র code প্রায়ই 5 লাইনের — কিন্তু সেই 5 লাইন লেখার সাহস আসে প্রমাণ থেকে। এই note-এর লক্ষ্য: প্রতিটা greedy pattern-এর পেছনের "কেন"-টা ছবি আর ছোট উদাহরণ দিয়ে মাথায় গেঁথে দেওয়া। মুখস্থ নয় — convince হও।
1. Greedy মানে কী, আর কখন বিশ্বাস করব?¶
Greedy = প্রতি step-এ locally সেরা choice নাও, পেছনে ফিরে তাকিও না। যেমন পাহাড়ে উঠছ আর প্রতি মোড়ে সবচেয়ে খাড়া রাস্তাটা নিচ্ছ — কখনো এতে চূড়ায় পৌঁছাবে, কখনো একটা ছোট টিলায় আটকে যাবে।
তাহলে কখন কাজ করে? দুটো জিনিস লাগে:
- Greedy choice property — locally সেরা choice টা কোনো না কোনো optimal solution-এর অংশ
- Optimal substructure — choice নেওয়ার পর বাকি problem টা একই রকম ছোট problem
এগুলো শুনতে ভারী লাগে, তাই practical নিয়ম: greedy idea পেলে আগে counterexample খোঁজো। 5 মিনিট খুঁজে না পেলে exchange argument দিয়ে প্রমাণের চেষ্টা করো। দুটোর একটাও না পারলে greedy টা ঝুঁকিপূর্ণ — DP বা অন্য পথ ভাবো।
2. Exchange argument — greedy প্রমাণের প্রধান হাতিয়ার¶
ধারণাটা এক লাইনে: যেকোনো optimal solution নাও, তার সাথে আমার greedy solution-এর প্রথম যেখানে অমিল, সেখানে optimal-এর choice টা greedy-র choice দিয়ে বদলে (exchange করে) দেখাও যে solution খারাপ হয় না। বারবার বদলাতে থাকলে optimal টা greedy-তে রূপান্তরিত হয়, কিন্তু মান একই থাকে — তাই greedy-ও optimal।
Interval scheduling (earliest finish first) দিয়ে দেখি। ধরো optimal solution O-র প্রথম interval j, আর greedy নিয়েছে g (সবচেয়ে আগে শেষ হওয়াটা)। তাহলে finish(g) ≤ finish(j)। O-তে j-এর জায়গায় g বসাও:
greedy: [--g--]
optimal: [----j----] [--পরের গুলো--]
g আগে শেষ হয় ⇒ j-এর পরের সব interval g-এর পরেও শুরু হতে পারে
⇒ j-কে g দিয়ে বদলালে কোনো clash হয় না, interval সংখ্যাও কমে না
এই বদলে solution খারাপ হলো না — মানে greedy-র প্রথম choice নিরাপদ। বাকিটা একই যুক্তি ছোট problem-এ। এটাই exchange argument-এর পুরো কঙ্কাল।
3. Coin change — greedy-র সবচেয়ে বিখ্যাত ফাঁদ¶
Canonical system (যেমন টাকা: 1, 2, 5, 10, 20, 50, 100...) এ greedy ঠিকঠাক: সবচেয়ে বড় coin যতবার পারো নাও।
def min_coins_greedy(amount, coins): # coins বড় থেকে ছোট sorted
count = 0
for c in coins:
count += amount // c
amount %= c
return count if amount == 0 else -1
print(min_coins_greedy(67, [50, 20, 10, 5, 2, 1])) # 50+10+5+2 = 4 coins ✓
কিন্তু coin set {1, 3, 4} দিয়ে 6 বানাও:
greedy: 6 → 4 নিলাম (বাকি 2) → 1 নিলাম (বাকি 1) → 1 নিলাম → মোট 3 coin
optimal: 3 + 3 → মোট 2 coin ✗ greedy হেরে গেল!
কেন fail? 4 নেওয়াটা locally লোভনীয়, কিন্তু বাকি 2-টা গড়তে দুটো 1 লাগে — বড় coin টা ভবিষ্যৎ নষ্ট করল। শিক্ষা: greedy-র correctness coin set-এর গঠনের উপর নির্ভর করে; arbitrary set-এ DP লাগে (level 12-র coin change অপেক্ষা করছে)। এই counterexample টা মুখস্থ রাখো — interview-তে "greedy কেন সবসময় কাজ করে না" প্রশ্নের one-shot উত্তর।
4. Furthest reach — Jump Game-এর এক-সংখ্যার জাদু¶
Array-র প্রতিটা ঘরে লেখা সেখান থেকে সর্বোচ্চ কত ঘর লাফানো যায়। শেষ ঘরে পৌঁছানো সম্ভব কি? সব path ঘাঁটতে হবে না — শুধু track করো এখন পর্যন্ত সর্বোচ্চ কোথায় পৌঁছানো সম্ভব:
def can_jump(nums):
furthest = 0
for i, x in enumerate(nums):
if i > furthest: # এই ঘরেই তো আসা যায় না!
return False
furthest = max(furthest, i + x)
return True
Mini dry run (nums = [2, 3, 1, 1, 4]):
i=0, x=2: furthest = max(0, 0+2) = 2
i=1, x=3: 1 ≤ 2 ✓, furthest = max(2, 1+3) = 4
i=2, x=1: 2 ≤ 4 ✓, furthest = max(4, 3) = 4
i=3, i=4: সবই ≤ 4 → True
আর nums = [3, 2, 1, 0, 4] হলে: furthest আটকে যায় 3-এ, i = 4 > 3 → False। কেন greedy ঠিক? কারণ "কোন ঘর থেকে লাফালাম" তথ্যটা দরকারই নেই — পৌঁছানো যায় কি না সেটা শুধু furthest-এর উপর নির্ভর করে। অপ্রয়োজনীয় তথ্য ফেলে দেওয়াই এখানে greedy-র জোর।
5. Reset point — Gas Station-এর দুই observation¶
বৃত্তাকার রাস্তায় n টা station; gain[i] = gas[i] - cost[i]। কোন station থেকে শুরু করলে পুরো চক্কর সম্ভব?
- Observation 1: মোট
sum(gain) < 0হলে কোনো start-ই কাজ করবে না (মোট জ্বালানিই কম)। আর≥ 0হলে অন্তত একটা start আছেই। - Observation 2: station
sথেকে শুরু করে stationi-তে এসে tank negative হলে —sথেকেi-এর মাঝের কোনো station-ই valid start না। কারণ মাঝের যেকোনো station থেকে শুরু করলেi-তে পৌঁছানোর সময় tank আরো কম থাকত (পথে জমা fuel হারাচ্ছ)। তাই সোজাi + 1থেকে নতুন করে শুরু করো — এটাই reset।
def gas_station(gas, cost):
total, tank, start = 0, 0, 0
for i in range(len(gas)):
gain = gas[i] - cost[i]
total += gain
tank += gain
if tank < 0:
start = i + 1 # reset: মাঝের কাউকে আর try করতে হবে না
tank = 0
return start if total >= 0 else -1
O(n²) simulate না করে এক pass — দুটো observation মিলেই জাদু।
6. Two pass — Candy-তে দুই প্রতিবেশীকে আলাদাভাবে খুশি করা¶
প্রতিটা শিশুর rating আছে; বেশি rating-এর শিশু দুই পাশের প্রতিবেশীর চেয়ে বেশি candy পাবে, প্রত্যেকে অন্তত 1টা। সমস্যা: এক pass-এ বাঁ-প্রতিবেশীর শর্ত মেটালেও ডান-প্রতিবেশী তো এখনো দেখাই হয়নি! তাই:
- Pass 1 (বাঁ → ডান):
rating[i] > rating[i-1]হলেcandy[i] = candy[i-1] + 1— শুধু বাঁ দিকের শর্ত guarantee - Pass 2 (ডান → বাঁ):
rating[i] > rating[i+1]হলেcandy[i] = max(candy[i], candy[i+1] + 1)— ডান দিকের শর্ত, আরmaxনেওয়ায় বাঁ দিকের guarantee ভাঙে না
def candy(ratings):
n = len(ratings)
c = [1] * n
for i in range(1, n): # pass 1
if ratings[i] > ratings[i - 1]:
c[i] = c[i - 1] + 1
for i in range(n - 2, -1, -1): # pass 2
if ratings[i] > ratings[i + 1]:
c[i] = max(c[i], c[i + 1] + 1)
return sum(c)
Mini dry run (ratings = [1, 3, 2, 1]):
pass 1: c = [1, 2, 1, 1] (3 > 1 বলে index 1 বাড়ল; বাকি বাড়েনি)
pass 2: i=2: 2 > 1 → c[2] = max(1, 1+1) = 2
i=1: 3 > 2 → c[1] = max(2, 2+1) = 3
c = [1, 3, 2, 1] → মোট 7
প্রতিটা ঘরে এখন দুই দিকের শর্তই সত্য — কারণ max কখনো কমায় না, শুধু বাড়ায়।
7. Event sweep — Minimum Platforms (level 5-এর পুরোনো বন্ধু)¶
ট্রেনের arrival/departure সময় দেওয়া; এক মুহূর্তে সর্বোচ্চ কয়টা ট্রেন station-এ — সেটাই minimum platform। প্রতিটা arrival = +1 event, departure = −1 event; সময় ধরে sort করে চলন্ত যোগফলের maximum নাও — হুবহু level 5-এর sweep line / prefix trick:
def min_platforms(arrivals, departures):
events = [(t, +1) for t in arrivals] + [(t, -1) for t in departures]
events.sort() # সমান সময়ে departure (−1) আগে — tuple sort এটা ফ্রি-তে দেয়
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
Dry run (arrivals [900, 940, 950], departures [910, 1200, 1120]):
sorted events: (900,+1) (910,−1) (940,+1) (950,+1) (1120,−1) (1200,−1)
running: 1 0 1 2 1 0
best = 2 → 2টা platform যথেষ্ট
লক্ষ করো sort-এ (950, −1) থাকলে সেটা (950, +1)-এর আগে আসত — মানে একই মুহূর্তে ছাড়া ট্রেনের platform-টা আসা ট্রেন পেয়ে যায়। Problem-এর নিয়ম উল্টো হলে event-এ +1-কে আগে আনার মতো করে sort key পাল্টাতে হবে — এটা একটা classic edge case।
8. Most frequent first — Reorganize String (heap-এর teaser)¶
কোনো দুটো একই character পাশাপাশি থাকবে না — সম্ভব হলে rearrange করো। Greedy intuition: সবচেয়ে বেশি frequency-র character-টাই সবচেয়ে বড় হুমকি — তাকে আগে আগে বসাও, ফাঁকে ফাঁকে। Feasibility check: কোনো character-এর count (n + 1) // 2-এর বেশি হলে অসম্ভব (ফাঁকই নেই অত)।
সহজ Python কৌশল — সবচেয়ে frequent character টা index 0, 2, 4...-এ আগে বসাও, বাকিরা পরের ফাঁকা even ঘর শেষে odd ঘরে:
from collections import Counter
def reorganize(s):
n = len(s)
cnt = Counter(s)
ch, freq = cnt.most_common(1)[0]
if freq > (n + 1) // 2:
return "" # অসম্ভব
res = [None] * n
i = 0
for c, f in cnt.most_common(): # frequency descending
for _ in range(f):
res[i] = c
i += 2
if i >= n:
i = 1 # even ঘর শেষ → odd ঘরে যাও
return "".join(res)
print(reorganize("aab")) # "aba"
প্রতিবার "এখন সবচেয়ে frequent কে?" — dynamic ভাবে জানতে চাইলে max-heap লাগে; সেই পুরো গল্প ../../08-heap-priority-queue/-তে। এখানে শুধু greedy idea-টা চেনো: বড় বোঝা আগে নামাও।
9. Break into 3s — Integer Break-এর math greedy¶
n-কে অন্তত দুই টুকরো (positive integer) করে গুণফল maximize করো। দাবি: যত পারো 3 ভাঙো; 4 থাকলে 2+2 রাখো; 1 কখনো রেখো না। কেন?
6 = 3+3 → 9 কিন্তু 2+2+2 → 8 (3 জেতে)
4 = 2+2 → 4 কিন্তু 3+1 → 3 (1 মানেই অপচয় — গুণে কিছু যোগ করে না)
5-এর বেশি যেকোনো টুকরো ভাঙলে গুণফল বাড়ে: x ≥ 5 হলে 3(x−3) = 3x−9 > x
def integer_break(n):
if n <= 3:
return n - 1 # অন্তত দুই টুকরো বাধ্যতামূলক
prod = 1
while n > 4:
prod *= 3
n -= 3
return prod * n # শেষে n হবে 2, 3 বা 4
print(integer_break(10)) # 3*3*4 = 36
এটা greedy কারণ এক-একটা local নিয়ম ("3 নাও") সরাসরি ছোট অসমতা দিয়ে প্রমাণিত — exchange argument-এর ক্ষুদ্রতম রূপ।
10. Median target — সমান করতে median, mean নয়!¶
সব element সমান করতে হবে; এক move-এ একটা element ±1। মোট move = sum(|a[i] − target|) — এটা minimize করে median, mean নয়। ছোট উদাহরণে দেখো:
a = [1, 2, 100]
mean = 34.33 → 34-এ আনলে: 33 + 32 + 66 = 131 move
median = 2 → 2-এ আনলে: 1 + 0 + 98 = 99 move ✓
Intuition: target-টা একটু ডানে সরাও — median-এর বাঁয়ে যত element, প্রত্যেকের cost +1; ডানে যত, প্রত্যেকের −1। দুই পাশে সমান সংখ্যা থাকলে (median-এ) সরে লাভ নেই — এটাই minimum। Mean জেতে squared difference-এ; absolute difference-এ median-ই রাজা।
11. Minimize Maximum Difference — greedy নাকি binary search on answer?¶
k টা element বেছে নিয়ে (বা ভাগ করে) maximum gap minimize করার ঘরানার problem-এ দুটো রাস্তা: (1) sort করে adjacent difference নিয়ে greedy ভাবা — কারণ sorted array-তে যেকোনো বাছাইয়ের সেরা প্রার্থীরা পাশাপাশি বসে; (2) "answer ≤ x সম্ভব কি?" — এই check monotonic, তাই level 7-এর binary search on answer (BSoA) চলে (../07-binary-search-on-answer/)। Problem 112-এ দুই পথ পাশাপাশি দাঁড় করিয়ে তুলনা করবে — কোনটা কখন সহজ, এই বিচারবোধটাই এই level-এর শেষ উপহার।
এক নজরে pattern গুলো¶
pattern মূল প্রশ্ন প্রমাণের ধরন
─────────────────────────────────────────────────────────────────────
canonical greedy বড় coin আগে নিলে ঠিক হবে? counterexample খোঁজো!
furthest reach সর্বোচ্চ কোথায় পৌঁছাই? তথ্য কমানো যুক্তি
reset point fail করলে কোথা থেকে আবার? observation 1 + 2
two pass দুই দিকের শর্ত একসাথে কীভাবে? max-এ guarantee রক্ষা
earliest finish কোন interval আগে? exchange argument
event sweep এক মুহূর্তে কয়জন? +1/−1 চলন্ত যোগফল
most frequent first কে সবচেয়ে বড় হুমকি? feasibility bound
break into 3s কত টুকরোয় ভাঙব? ছোট অসমতা
median target কোথায় টেনে আনব? বাঁ-ডান ভারসাম্য
পরের ধাপ: প্রতিটা problem-এ ঢোকার আগে visualization-ideas.md-র ছবিগুলো একবার দেখে নাও — greedy-র যুক্তি চোখে দেখলে অর্ধেক প্রমাণ এমনিই হয়ে যায়।