106 — Candy Distribution¶

এই level-এর একমাত্র Hard, কিন্তু ভয় পেও না — কঠিন লাগে শুধু "এক pass-এ হবে না কেন" বুঝতে। একবার দেখলে যে দুই দিকের প্রতিবেশীকে আলাদা দুই pass-এ খুশি করতে হয়, তখন সব জলের মতো পরিষ্কার। ধীরে পড়ো; two pass-এর এই trick অনেক জায়গায় ফিরবে।

Source¶

Original source: LeetCode — Candy
Platform: LeetCode — https://leetcode.com/problems/candy/
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)

1. Problem in simple words¶

একসারিতে n টা শিশু দাঁড়িয়ে, প্রত্যেকের একটা rating (নম্বর) আছে। তুমি ক্যান্ডি বিলি করবে এই দুই নিয়ম মেনে:

প্রত্যেক শিশু অন্তত 1টা ক্যান্ডি পাবে
যার rating তার পাশের প্রতিবেশীর (বাঁ বা ডান) চেয়ে বেশি, সে ওই প্রতিবেশীর চেয়ে বেশি ক্যান্ডি পাবে

প্রশ্ন: এই দুই শর্ত মেনে সবচেয়ে কম মোট কয়টা ক্যান্ডি লাগবে?

উদাহরণ: ratings = [1, 0, 2] → ক্যান্ডি [2, 1, 2] → মোট 5।

2. What is the math idea?¶

মূল কথা — প্রতিটা শিশুর শর্ত দুই দিক থেকে আসে (বাঁ প্রতিবেশী আর ডান প্রতিবেশী), আর এই দুই দিক একসাথে এক pass-এ সামলানো যায় না। তাই idea:

প্রতিটা দিকের শর্ত আলাদা pass-এ মেটাও
তারপর প্রতিটা শিশুর জন্য দুই pass-এর সর্বোচ্চটা (max) নাও — কারণ max নিলে কোনো দিকের শর্তই ভাঙে না, দুটোই একসাথে সত্য থাকে

এটা greedy: প্রতিটা ঘরে যতটুকু দরকার ঠিক ততটুকু ক্যান্ডি দিই, এক ফোঁটা বেশি নয়।

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-তে ফিরবে।

4. Real-life analogy¶

ভাবো শিক্ষক ক্যান্ডি বিলি করছেন এই নিয়মে — "যে বেশি ভালো করেছে (বেশি rating), সে তার পাশের জনের চেয়ে বেশি পাবে।"

প্রথমে শিক্ষক বাঁ দিক থেকে ডানে হাঁটেন: কোনো শিশু তার বাঁ পাশের জনের চেয়ে ভালো হলে, তাকে এক বেশি দেন। কিন্তু থামুন — ডান পাশের শর্ত তো এখনো দেখাই হয়নি! তাই শিক্ষক আবার ডান দিক থেকে বাঁয়ে হাঁটেন, এবার ডান পাশের শর্ত মেটান। আর প্রতিটা শিশুর হাতে শেষমেশ থাকে দুবারের মধ্যে যেটা বেশি — তাহলেই দুই পাশের শর্তই একসাথে মেনে চলা হয়, আর একটাও বাড়তি ক্যান্ডি নষ্ট হয় না।

5. Visual explanation¶

ratings = [1, 3, 2, 1] — দুই pass কীভাবে কাজ করে:

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? — সেই ছবি:

শিশু 1 (rating 3): বাঁ pass চাইল ≥ 2 (কারণ 3>1)
                   ডান pass চাইল ≥ 3 (কারণ 3>2)
        max(2, 3) = 3  → দুই দাবিই একসাথে মেটে ✓
        max না নিয়ে 2 দিলে ডান শর্ত ভাঙত!

6. Example input and output¶

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 সমান — সমান হলে কোনো শর্ত নেই, তাই দুজনকে আলাদা সংখ্যা দেওয়ার দরকার নেই।

7. Brute force thinking¶

সরাসরি, কিন্তু ধীর চিন্তা — সবাইকে 1 দিয়ে শুরু করো, তারপর যতক্ষণ কোনো শর্ত ভাঙছে ততক্ষণ ভাঙা ঘরের ক্যান্ডি 1 করে বাড়াতে থাকো (repeated relaxation):

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) হয়ে যায়।

[1,2,3,...,n] হলে শেষ ঘরের তথ্য বাঁ দিক পর্যন্ত পৌঁছাতে
বহুবার pass লাগে — একই array বারবার ঘোরা।

brute force : ~O(n²) (ধীর, বহু pass)
greedy      : O(n)   (মাত্র দুই pass — বাঁ→ডান, ডান→বাঁ)

9. Better thinking¶

মূল observation: প্রতিটা দিকের শর্ত একটামাত্র directional pass-এ পুরোপুরি মেটানো যায়। তাই দুই pass যথেষ্ট:

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-এর জাদু: একদিকের অর্জন রক্ষা করেই অন্যদিকের শর্ত জোড়ে।

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। প্রতিটা ঘরে এখন দুই দিকের শর্তই সত্য।

12. Python solution¶

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¶

c = [1] * n

প্রথম শর্ত — সবাই অন্তত 1টা ক্যান্ডি পায়।

for i in range(1, n):
    if ratings[i] > ratings[i - 1]:
        c[i] = c[i - 1] + 1

pass 1, বাঁ→ডান। কোনো শিশু তার বাঁ প্রতিবেশীর চেয়ে ভালো হলে, তাকে বাঁ-জনের চেয়ে 1 বেশি দিই। এই pass শেষে সব ঘরে বাঁ প্রতিবেশীর শর্ত সত্য।

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 কখনো মান কমায় না, শুধু দরকারে বাড়ায়।

return sum(c)

প্রতিটা শিশুর ন্যূনতম দরকার মেটানো ক্যান্ডির যোগফলই minimum মোট।

candy_brute repeated relaxation দিয়ে একই minimum বের করে (ধীর); itertools.product দিয়ে ছোট সব rating-array বানিয়ে two-pass আর brute মিলিয়ে দেখা হয়েছে।

14. Output walkthrough¶

চালালে ছাপবে:

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!।

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 করা — শুধু বাঁ→ডান বা শুধু ডান→বাঁ করলে অন্য পাশের শর্ত ভাঙবে; দুটোই চাই।

18. Harder problems that inherit this idea¶

LeetCode — Trapping Rain Water (https://leetcode.com/problems/trapping-rain-water/) — ক্লাসিক two-pass (left-max ও right-max আলাদা pass, তারপর min) — একই "দুই দিক থেকে তথ্য জড়ো" দর্শন।
LeetCode — Product of Array Except Self (https://leetcode.com/problems/product-of-array-except-self/) — prefix product (বাঁ→ডান) ও suffix product (ডান→বাঁ) — two-pass-এর আরেক রূপ।
LeetCode — Candy (https://leetcode.com/problems/candy/) — মূল problem নিজেই; constant-space O(1) variant ভাবলে আরও গভীরে যাওয়া যায় (peak/valley গোনা)।

19. Pattern learned¶

Two pass (directional sweeps + max/min merge) — যখন এক ঘরের শর্ত দুই দিক থেকে আসে, প্রতিটা দিক আলাদা pass-এ মেটাও, তারপর max (বা min) দিয়ে মেলাও যাতে কোনো দিকের guarantee না ভাঙে। বড় শিক্ষা: এক pass-এ দুই দিকের তথ্য ধরা না গেলে, উল্টোদিক থেকে আরেক pass চালাও।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Candy = two pass; বাঁ→ডান-এ বাঁ শর্ত, ডান→বাঁ-এ max দিয়ে ডান শর্ত — দুই দিকের দাবি একসাথে মেটাও, প্রতিটা ঘরে ন্যূনতম দিয়ে।"

পরের ধাপ → 107 — Interval Scheduling (exchange argument-এর সবচেয়ে পরিষ্কার উদাহরণ — earliest finish first)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; কোনো problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।