Problem link ও উৎস
- **Original source:** LeetCode — Candy
- **Platform:** LeetCode —
- **Topic:** Greedy math tricks → two-pass (left-to-right + right-to-left)
- **Difficulty:** Hard
- **Pattern:** two pass (এক দিক থেকে এক pass, আরেক দিক থেকে আরেক, তারপর max)
- **Basic idea inherited from:** — (greedy level-এর প্রথম two-pass problem)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একসারিতে `n` টা শিশু দাঁড়িয়ে, প্রত্যেকের একটা `rating` (নম্বর) আছে। তুমি ক্যান্ডি বিলি করবে এই দুই নিয়ম মেনে:
- প্রত্যেক শিশু **অন্তত 1টা** ক্যান্ডি পাবে
- যার rating তার **পাশের প্রতিবেশীর** (বাঁ বা ডান) চেয়ে বেশি, সে ওই প্রতিবেশীর চেয়ে **বেশি** ক্যান্ডি পাবে
প্রশ্ন: এই দুই শর্ত মেনে **সবচেয়ে কম মোট কয়টা ক্যান্ডি** লাগবে?
উদাহরণ: `ratings = [1, 0, 2]` → ক্যান্ডি `[2, 1, 2]` → মোট 5।
### Input ও output {#6-example-input-and-output}
```text
ratings -> output (এক সম্ভাব্য বণ্টন)
-----------------------------------------------------
[1, 0, 2] -> 5 ([2, 1, 2])
[1, 2, 2] -> 4 ([1, 2, 1] — সমান rating-এ শর্ত নেই)
[1, 3, 2, 1] -> 7 ([1, 3, 2, 1])
[5] -> 1 (একটাই শিশু)
[1, 2, 3, 4, 5] -> 15 ([1, 2, 3, 4, 5], 1+2+3+4+5)
```
খেয়াল করো `[1, 2, 2]`-এ মাঝ আর শেষ শিশুর rating সমান — সমান হলে কোনো শর্ত নেই, তাই দুজনকে আলাদা সংখ্যা দেওয়ার দরকার নেই।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো শিক্ষক ক্যান্ডি বিলি করছেন এই নিয়মে — "যে বেশি ভালো করেছে (বেশি rating), সে তার পাশের জনের চেয়ে বেশি পাবে।"
প্রথমে শিক্ষক **বাঁ দিক থেকে ডানে** হাঁটেন: কোনো শিশু তার বাঁ পাশের জনের চেয়ে ভালো হলে, তাকে এক বেশি দেন। কিন্তু থামুন — ডান পাশের শর্ত তো এখনো দেখাই হয়নি! তাই শিক্ষক আবার **ডান দিক থেকে বাঁয়ে** হাঁটেন, এবার ডান পাশের শর্ত মেটান। আর প্রতিটা শিশুর হাতে শেষমেশ থাকে **দুবারের মধ্যে যেটা বেশি** — তাহলেই দুই পাশের শর্তই একসাথে মেনে চলা হয়, আর একটাও বাড়তি ক্যান্ডি নষ্ট হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা greedy level-এর প্রথম two-pass problem, তাই আগের কোনো greedy-র উপর সরাসরি দাঁড়ায় না (`inherited from: —`)।
তবে এর শিকড় array-র উপর directional pass-এর সেই পুরোনো অভ্যাসে — বাঁ থেকে ডানে চলন্ত একটা মান ধরে রাখা (running comparison)। নতুনত্ব হলো **দুই দিক থেকে দুবার** চালিয়ে `max` দিয়ে মেলানো। এই "এক pass-এ ধরা যায় না বলে উল্টোদিক থেকে আরেক pass" idea-টা পরের অনেক DP/greedy-তে ফিরবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল কথা — **প্রতিটা শিশুর শর্ত দুই দিক থেকে আসে** (বাঁ প্রতিবেশী আর ডান প্রতিবেশী), আর এই দুই দিক একসাথে এক pass-এ সামলানো যায় না। তাই idea:
- প্রতিটা দিকের শর্ত **আলাদা pass-এ** মেটাও
- তারপর প্রতিটা শিশুর জন্য দুই pass-এর **সর্বোচ্চটা (max)** নাও — কারণ max নিলে কোনো দিকের শর্তই ভাঙে না, দুটোই একসাথে সত্য থাকে
এটা greedy: প্রতিটা ঘরে যতটুকু **দরকার ঠিক ততটুকু** ক্যান্ডি দিই, এক ফোঁটা বেশি নয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি, কিন্তু ধীর চিন্তা — **সবাইকে 1 দিয়ে শুরু করো, তারপর যতক্ষণ কোনো শর্ত ভাঙছে ততক্ষণ ভাঙা ঘরের ক্যান্ডি 1 করে বাড়াতে থাকো** (repeated relaxation):
```python
def candy_brute(ratings):
n = len(ratings)
candy = [1] * n
changed = True
while changed:
changed = False
for i in range(n):
if i > 0 and ratings[i] > ratings[i - 1] and candy[i] <= candy[i - 1]:
candy[i] = candy[i - 1] + 1
changed = True
if i < n - 1 and ratings[i] > ratings[i + 1] and candy[i] <= candy[i + 1]:
candy[i] = candy[i + 1] + 1
changed = True
return sum(candy)
```
প্রতিটা ভাঙা শর্ত ঠিক না হওয়া পর্যন্ত loop চলে, তাই শেষে সব শর্ত মেটে আর প্রতিটা মান যতটুকু দরকার ঠিক ততটুকু — অর্থাৎ minimum। ধীর, কিন্তু নির্ভুল; এটাই আমাদের যাচাইয়ের মাপকাঠি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই relaxation একবারে শুধু পাশের ঘরে তথ্য ছড়ায়, তাই একটা লম্বা বাড়তি-ক্রম (যেমন `[1,2,3,...,k]`) ঠিক করতে অনেকবার পুরো array ঘুরতে হয়। worst case-এ এটা প্রায় **O(n²)** (বা তারও বেশি pass) হয়ে যায়।
```text
[1,2,3,...,n] হলে শেষ ঘরের তথ্য বাঁ দিক পর্যন্ত পৌঁছাতে
বহুবার pass লাগে — একই array বারবার ঘোরা।
brute force : ~O(n²) (ধীর, বহু pass)
greedy : O(n) (মাত্র দুই pass — বাঁ→ডান, ডান→বাঁ)
```
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল observation: **প্রতিটা দিকের শর্ত একটামাত্র directional pass-এ পুরোপুরি মেটানো যায়।** তাই দুই pass যথেষ্ট:
```python
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)
```
**Greedy choice:** প্রতিটা ঘরে দুই pass মিলিয়ে যতটুকু **ন্যূনতম দরকার** ঠিক ততটুকুই দাও (`max` নিয়ে, কখনো বেশি নয়)।
**কেন কাজ করে (এক লাইন):** pass 1-এর পর "বাঁ প্রতিবেশী" শর্ত সব ঘরে সত্য; pass 2-এ `max` নেওয়ায় "ডান প্রতিবেশী" শর্তও সত্য হয় **আর pass 1-এর guarantee ভাঙে না** (max কখনো মান কমায় না) — তাই দুই শর্ত একসাথে মেটে, এবং প্রতিটা মান ন্যূনতম রাখায় মোটও minimum।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা!":
> "বাঁ আর ডান প্রতিবেশীর শর্ত একসাথে এক pass-এ ধরা যায় না — তাই দুই দিক থেকে দুবার চালাও, আর `max` দিয়ে মেলাও যাতে কোনো দিকের জয় নষ্ট না হয়।"
এক pass-এ চেষ্টা করলে ডান প্রতিবেশীর তথ্য বাঁ থেকে যেতে যেতে জানাই যায় না — এই উপলব্ধিটাই tweak। আর `max`-এর জাদু: একদিকের অর্জন রক্ষা করেই অন্যদিকের শর্ত জোড়ে।
### ছবিতে বোঝা {#5-visual-explanation}
`ratings = [1, 3, 2, 1]` — দুই pass কীভাবে কাজ করে:
```text
ratings : 1 3 2 1
শুরু : 1 1 1 1 (সবাই অন্তত 1)
pass 1 (বাঁ→ডান): rating[i] > rating[i-1] হলে candy[i]=candy[i-1]+1
i=1: 3>1 → 2
i=2: 2>3? না i=3: 1>2? না
candy : 1 2 1 1
pass 2 (ডান→বাঁ): rating[i] > rating[i+1] হলে candy[i]=max(candy[i], candy[i+1]+1)
i=2: 2>1 → max(1, 1+1)=2
i=1: 3>2 → max(2, 2+1)=3
i=0: 1>3? না
candy : 1 3 2 1 মোট = 7
```
কেন `max`? — সেই ছবি:
```text
শিশু 1 (rating 3): বাঁ pass চাইল ≥ 2 (কারণ 3>1)
ডান pass চাইল ≥ 3 (কারণ 3>2)
max(2, 3) = 3 → দুই দাবিই একসাথে মেটে ✓
max না নিয়ে 2 দিলে ডান শর্ত ভাঙত!
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`ratings = [1, 3, 2, 1]` ধীরে চালাই।
শুরু: `c = [1, 1, 1, 1]`
**Pass 1 (বাঁ→ডান):**
| i | ratings[i] > ratings[i-1]? | c[i] |
| --- | --- | --- |
| 1 | 3 > 1 হ্যাঁ | c[0]+1 = 2 |
| 2 | 2 > 3 না | 1 |
| 3 | 1 > 2 না | 1 |
pass 1 শেষে: `c = [1, 2, 1, 1]`
**Pass 2 (ডান→বাঁ):**
| i | ratings[i] > ratings[i+1]? | c[i] = max(c[i], c[i+1]+1) |
| --- | --- | --- |
| 2 | 2 > 1 হ্যাঁ | max(1, 1+1) = 2 |
| 1 | 3 > 2 হ্যাঁ | max(2, 2+1) = 3 |
| 0 | 1 > 3 না | 1 |
pass 2 শেষে: `c = [1, 3, 2, 1]` → মোট = **7**। প্রতিটা ঘরে এখন দুই দিকের শর্তই সত্য।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def candy(ratings):
"""two-pass greedy — minimum মোট ক্যান্ডি।"""
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)
def candy_brute(ratings):
"""relaxation দিয়ে minimum — ধীর কিন্তু নির্ভুল (যাচাইয়ের জন্য)।"""
n = len(ratings)
c = [1] * n
changed = True
while changed:
changed = False
for i in range(n):
if i > 0 and ratings[i] > ratings[i - 1] and c[i] <= c[i - 1]:
c[i] = c[i - 1] + 1
changed = True
if i < n - 1 and ratings[i] > ratings[i + 1] and c[i] <= c[i + 1]:
c[i] = c[i + 1] + 1
changed = True
return sum(c)
# --- ছোট test (সব pass করা উচিত) ---
assert candy([1, 0, 2]) == 5
assert candy([1, 2, 2]) == 4
assert candy([1, 3, 2, 1]) == 7
assert candy([5]) == 1
assert candy([1, 2, 3, 4, 5]) == 15
assert candy([5, 4, 3, 2, 1]) == 15
# two-pass আর brute force ছোট সব rating-এ একমত (brute = সত্য)
import itertools
for n in range(1, 7):
for r in itertools.product(range(0, 3), repeat=n):
assert candy(list(r)) == candy_brute(list(r))
print(candy([1, 0, 2])) # 5
print(candy([1, 3, 2, 1])) # 7
print(candy([1, 2, 3, 4, 5])) # 15
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
c = [1] * n
```
প্রথম শর্ত — সবাই অন্তত 1টা ক্যান্ডি পায়।
```text
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
c[i] = c[i - 1] + 1
```
pass 1, বাঁ→ডান। কোনো শিশু তার বাঁ প্রতিবেশীর চেয়ে ভালো হলে, তাকে বাঁ-জনের চেয়ে 1 বেশি দিই। এই pass শেষে **সব ঘরে বাঁ প্রতিবেশীর শর্ত সত্য**।
```text
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
c[i] = max(c[i], c[i + 1] + 1)
```
pass 2, ডান→বাঁ। ডান প্রতিবেশীর শর্ত মেটাই, কিন্তু `max` দিয়ে — যাতে pass 1-এ পাওয়া বাঁ-দিকের guarantee ভেঙে না যায়। `max` কখনো মান কমায় না, শুধু দরকারে বাড়ায়।
```text
return sum(c)
```
প্রতিটা শিশুর ন্যূনতম দরকার মেটানো ক্যান্ডির যোগফলই minimum মোট।
`candy_brute` repeated relaxation দিয়ে একই minimum বের করে (ধীর); `itertools.product` দিয়ে ছোট সব rating-array বানিয়ে two-pass আর brute মিলিয়ে দেখা হয়েছে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
5
7
15
সব test pass!
```
প্রথম তিন line `print` থেকে: `[1,0,2]` → 5, `[1,3,2,1]` → 7, `[1,2,3,4,5]` → 15। তার আগে সব `assert` (সরাসরি case + itertools দিয়ে ছোট সব rating-array) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — ঠিক দুটো pass, প্রতিটা array-র উপর একবার; প্রতিটা ঘরে constant কাজ। brute force-এর ~O(n²) থেকে বড় উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — একটা `c` array লাগে n শিশুর ক্যান্ডি ধরে রাখতে। (চাইলে দুই আলাদা array দিয়েও করা যায়, কিন্তু এক array + max-ই যথেষ্ট।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **এক pass-এ সমাধানের চেষ্টা** — সবচেয়ে বড় ভুল; ডান প্রতিবেশীর তথ্য বাঁ→ডান pass-এ জানা যায় না, দুই pass লাগবেই।
- **Pass 2-এ `max` না নেওয়া** — সরাসরি `c[i] = c[i+1] + 1` লিখলে pass 1-এর বাঁ-দিকের guarantee ভেঙে যেতে পারে; সবসময় `max(c[i], c[i+1]+1)`।
- **সমান rating-এ শর্ত বসানো** — শর্ত শুধু **কড়া বড়** (`>`)-র জন্য; সমান rating-এ কোনো দাবি নেই, তাই অহেতুক বাড়িও না।
- **সবাইকে 1 দিয়ে শুরু না করা** — base হিসেবে সবার 1 দরকার (ন্যূনতম শর্ত); 0 দিলে ভুল।
- **শুধু একদিকের pass করা** — শুধু বাঁ→ডান বা শুধু ডান→বাঁ করলে অন্য পাশের শর্ত ভাঙবে; দুটোই চাই।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Trapping Rain Water** (