100 — Split Array Largest Sum

অভিনন্দন — তুমি এই level-এর 100 নম্বর মাইলফলকে! 099-এ বই-ছাত্র ভাগ করেছিলে; এখন সেটারই আক্ষরিক যমজ, শুধু "ছাত্র"-এর জায়গায় "subarray" আর "বই"-এর জায়গায় "সংখ্যা"। গল্প বদলেছে, হাড়-পাঁজর এক। তাই এই note-টা একদিকে পুরোনো বন্ধুর সাথে দেখা, অন্যদিকে minimize-the-maximum pattern-টা চিরস্থায়ীভাবে গেঁথে নেওয়ার সুযোগ। (বোনাস হিসেবে শেষে DP রাস্তাটাও ছুঁয়ে যাব।)

Source

• Original source: LeetCode — Split Array Largest Sum
• Platform: LeetCode — https://leetcode.com/problems/split-array-largest-sum/
• Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
• Difficulty: Hard
• Pattern: minimize max load (সবচেয়ে ভারী ভাগকে যত হালকা সম্ভব)
• Basic idea inherited from: 099 — Allocate Minimum Pages

1. Problem in simple words

একটা non-negative integer-এর array nums দেওয়া, আর একটা সংখ্যা m (কতগুলো টুকরো করতে হবে)। array-কে ঠিক mটা পরপর (contiguous), non-empty টুকরোয় ভাগ করতে হবে — কোনো উপাদান বাদ যাবে না, ক্রম বদলানো যাবে না।

প্রতিটা টুকরোর "ওজন" = তার ভেতরের সংখ্যাগুলোর যোগফল। mটা টুকরোর মধ্যে যেটা সবচেয়ে ভারী, সেটাই হলো ওই ভাগের "largest sum"। প্রশ্ন: এমনভাবে ভাগ করো যাতে এই largest sum যত ছোট সম্ভব হয়। সেই সর্বনিম্ন largest sum-ই উত্তর।

উদাহরণ: nums = [7, 2, 5, 10, 8], m = 2। সবচেয়ে ভালো ভাগ [7, 2, 5] আর [10, 8] → ওজন 14 আর 18 → largest = 18। অন্য যেকোনো 2-ভাগে largest 18-এর চেয়ে বড় বা সমান।

2. What is the math idea?

ভিত্তি হলো monotonic feasibility + binary search on the answer (BSoA)। সরাসরি "সেরা ভাগ" খোঁজা কঠিন, তাই আমরা প্রশ্নটা উল্টে দিই: "largest sum সর্বোচ্চ cap হতে দিলে, কি m বা তার কম টুকরোয় ভাগ করা যায়?" — এই can(cap) প্রশ্নের উত্তর হ্যাঁ/না।

মূল গাণিতিক সত্য — can(cap) monotonic: cap বাড়ালে কাজ সহজ হয় (কম টুকরো লাগে), কমালে কঠিন। তাই উত্তরের রেখায় একটা স্পষ্ট সীমা আছে — সীমার নিচে সব "না", সীমা থেকে সব "হ্যাঁ"। সেই প্রথম "হ্যাঁ" খুঁজতে binary search। আর কোনো cap-এ ন্যূনতম কত টুকরো লাগে সেটা greedy বলে দেয় — সামনে থেকে যতক্ষণ পারো এক টুকরোয় ভরো, cap ছাড়ালে নতুন টুকরো খোলো।

3. Which basic idea does this inherit from?

এটা 099 — Allocate Minimum Pages-এর হুবহু যমজ। 099-এ ছিল বই (পৃষ্ঠা) আর ছাত্র; এখানে সংখ্যা আর subarray — কিন্তু গণিত একদম এক: "consecutive ভাগ + সবচেয়ে ভারী ভাগকে minimize"। 099-এর can(cap) greedy আর binary search কাঠামো এখানে প্রায় copy-paste।

আর 099 নিজে দাঁড়িয়ে ছিল 097 (Ship Packages)-এর উপর, 097 দাঁড়িয়ে 096 (Koko Eating Bananas)-এর উপর। মানে Koko → Ship → Pages → Split — চারটেই একই minimize-BSoA পরিবার, প্রতিটায় শুধু "guess করি একটা সীমা, greedy-তে গুনি কয়টা লাগে" গল্পের মোড়ক বদলায়। এই note-এ এসে pattern-টা পুরো পরিণত — তাই এটাকে Hard বলা হলেও তোমার কাছে এটা এখন চেনা।

4. Real-life analogy

ভাবো তোমার কাছে পরপর সাজানো কয়েকটা বাক্স আছে, প্রত্যেকটার আলাদা ওজন। m জন কুলিকে এগুলো ভাগ করে বইতে দিতে হবে — কিন্তু প্রত্যেক কুলি পরপর কয়েকটা বাক্সই নিতে পারে (মাঝখান থেকে তুলে নেওয়া বারণ, লাইন ভাঙা যাবে না)।

তুমি ন্যায্য নেতা — চাও যে কুলি সবচেয়ে ভারী বোঝা পায়, তার বোঝাটাও যেন যথাসম্ভব হালকা হয়। কীভাবে ঠিক করবে? মনে মনে একটা সীমা ধরো — "কেউ X কেজির বেশি বইবে না"। তারপর লাইন ধরে কুলি বসাও: একজনকে যতক্ষণ X-এর মধ্যে থাকে বাক্স দাও, ছাড়িয়ে গেলে পরের কুলি ডাকো। শেষে গোনো — কতজন কুলি লাগল? m-এর কম-সমান হলে X যথেষ্ট ছোট (আরও ছোট চেষ্টা করো); বেশি লাগলে X বাড়াও। ঠিক যেখানে "ঠিক m জনে কুলিয়ে যায় কিন্তু এক কেজি কমালেই বেশি লাগে" — সেই X-ই উত্তর।

5. Visual explanation

nums = [7, 2, 5, 10, 8], m = 2। answer space [max(nums), sum(nums)] = [10, 32]। কয়েকটা cap-এ greedy চালিয়ে দেখি কত টুকরো লাগে:

nums:   7   2   5   10   8        sum = 32,  max = 10

cap=10:  [7,2]=9 | [5]=5 | [10]=10 | [8]=8        -> 4 টুকরো  (>2, না)
cap=14:  [7,2,5]=14 | [10]=10 | [8]=8             -> 3 টুকরো  (>2, না)
cap=18:  [7,2,5]=14 | [10,8]=18                   -> 2 টুকরো  (<=2, হ্যাঁ)
cap=17:  [7,2,5]=14 | [10]=10 ...[8]=8            -> 3 টুকরো  (>2, না)

F/T সিঁড়ি (can ≤ m টুকরোয় ভাগ?):
 cap:  10  11  12 ... 17  18  19 ... 32
 can:  F   F   F  ... F   T   T  ... T
                          ^
                     প্রথম T = 18 = উত্তর

লক্ষ করো: cap যত বাড়ে, টুকরো তত কমে (monotonic)। cap=17-এ 3 টুকরো লাগে (না), cap=18-এ 2 (হ্যাঁ) — সীমাটা ঠিক 18-এ। সেটাই minimize-করা largest sum।

6. Example input and output

nums                  m     output   কেন
-----------------------------------------------------------
[7, 2, 5, 10, 8]      2     18       [7,2,5]=14 আর [10,8]=18
[1, 2, 3, 4, 5]       2     9        [1,2,3]=6 আর [4,5]=9
[1, 4, 4]             3     4        প্রতিটা একা; max single = 4
[10]                  1     10       এক উপাদান, এক ভাগ
[1, 1, 1, 1]          4     1        চারটে একা, largest = 1
[2, 3, 1, 2, 4, 3]    5     4        বেশি ভাগ -> largest ছোট

মূল edge case: m = 1 → পুরো array এক ভাগ → উত্তর sum(nums); m = len(nums) → প্রতিটা একা → উত্তর max(nums)। আর সবসময় 1 <= m <= len(nums) ধরা হয় (m বেশি হলে non-empty ভাগ অসম্ভব)।

7. Brute force thinking

সরল চিন্তা — সব রকম ভাবে array-কে m টুকরোয় কাটো, প্রতিবার largest sum বের করো, সবচেয়ে ছোটটা রাখো। n লম্বা array-কে m টুকরোয় ভাগ করতে m−1টা "কাটা দাগ" বসাতে হয় n−1টা সম্ভব ফাঁকে — সেটা recursion দিয়ে করা যায়:

def split_brute(nums, m):
    n = len(nums)
    best = [float('inf')]

    def rec(start, parts_left, cur_max):
        if parts_left == 1:               # বাকিটা শেষ ভাগ
            seg = sum(nums[start:])
            best[0] = min(best[0], max(cur_max, seg))
            return
        s = 0
        # এই ভাগ start থেকে শুরু, অন্তত 1 উপাদান, পরের ভাগের জন্য জায়গা রেখে
        for end in range(start, n - parts_left + 1):
            s += nums[end]
            rec(end + 1, parts_left - 1, max(cur_max, s))

    rec(0, m, 0)
    return best[0]

এটা প্রতিটা সম্ভব ভাগ পরীক্ষা করে — তাই নিশ্চিত ঠিক উত্তর। ছোট input-এ চমৎকার, আমাদের asserts-এ এটাই reference।

8. Why brute force may be slow

কাটা-দাগ বসানোর উপায় C(n−1, m−1) — combinatorially বিস্ফোরক। n = 30, m = 15 হলেই কোটি কোটি সম্ভাবনা; বড় input-এ recursion গাছ এত চওড়া যে নিশ্চিত Time Limit Exceeded।

n=30, m=15 হলে:
  brute force: C(29, 14) ≈ 67,863,915 সম্ভাব্য ভাগ   (বিস্ফোরক)
  BSoA       : ~log2(sum) × n ≈ 30 × 30 = 900 ধাপ      (চোখের নিমেষে)

মূল অপচয় — একই subarray-র যোগফল বারবার নতুন করে হিসাব, আর প্রায় একরকম ভাগ বহুবার পরীক্ষা। (DP দিয়ে overlapping অংশ মনে রাখা যায় — সেটা O(m·n²), কাজ করে কিন্তু BSoA আরও দ্রুত ও সহজ।)

9. Better thinking

উত্তর সরাসরি খোঁজার বদলে উত্তরের উপর binary search। largest sum-এর সম্ভাব্য মান [max(nums), sum(nums)]-এর মধ্যে: কখনো একটা একক সংখ্যার চেয়ে ছোট হতে পারে না (সেই সংখ্যাকে কোনো ভাগে তো রাখতেই হবে), আর সবচেয়ে বড় হলে সবটা এক ভাগে (sum)।

প্রতিটা guess cap-এর জন্য greedy-তে গুনি ন্যূনতম কত টুকরো লাগে:

def split_array(nums, m):
    def need(cap):                  # cap সীমায় কয়টা টুকরো লাগে
        parts, cur = 1, 0
        for x in nums:
            if cur + x > cap:       # এই সংখ্যা যোগ করলে cap ছাড়ায়
                parts += 1          # নতুন টুকরো খোলো
                cur = x
            else:
                cur += x
        return parts

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if need(mid) <= m:          # mid যথেষ্ট বড় -> আরও ছোট চেষ্টা
            hi = mid
        else:                       # ছোট পড়ছে -> বড় cap লাগবে
            lo = mid + 1
    return lo

log(sum) ধাপ, প্রতি ধাপে greedy O(n) — সব মিলিয়ে O(n log(sum))।

10. Thinking tweak

আসল মোচড় — "সেরা ভাগ কোনটা?" প্রশ্নটা সরাসরি কঠিন, কিন্তু "largest sum ≤ cap রাখা যায় কি?" প্রশ্নটা সহজ — আর সেটাই যথেষ্ট।

কারণ এই সহজ প্রশ্নের উত্তর cap-এর সাথে monotonic: cap বাড়লে "হ্যাঁ" থেকে আর কখনো "না"-তে ফেরে না। তাই একটা সাজানো F...FT...T রেখা পাই, আর binary search সেই প্রথম "T" খুঁজে আনে এক ঝটকায়। "minimize the maximum" দেখলেই এই উল্টে-দেওয়া (decision version + BSoA) চিন্তাটা মাথায় আসুক — Koko, Ship, Pages, Split, সব এই একই দরজা দিয়ে ঢোকে।

11. Step-by-step dry run

nums = [7, 2, 5, 10, 8], m = 2। lo = max = 10, hi = sum = 32:

lo	hi	mid = (lo+hi)//2	need(mid) টুকরো	need ≤ 2?	নতুন lo, hi
10	32	21	[7,2,5]=14, [10,8]=18 → 2	হ্যাঁ	hi = 21
10	21	15	[7,2,5]=14, [10]=10... → 3	না	lo = 16
16	21	18	[7,2,5]=14, [10,8]=18 → 2	হ্যাঁ	hi = 18
16	18	17	[7,2,5]=14, [10]... → 3	না	lo = 18
18	18	—	lo == hi, loop থামল	—	উত্তর 18

need(21) কীভাবে 2 হলো একটু দেখি: cur=0; +7→7, +2→9, +5→14 (≤21), +10→24>21 নতুন টুকরো cur=10, +8→18 (≤21)। শেষ → 2 টুকরো। শেষ অবস্থায় lo = hi = 18 — সেটাই minimize-করা largest sum, brute force-এর সাথে মিলে গেল।

12. Python solution

def split_array(nums, m):
    """nums-কে m contiguous ভাগে কেটে largest ভাগের sum minimize করে। O(n log sum)।"""
    def need(cap):
        """largest sum <= cap রাখতে ন্যূনতম কয়টা টুকরো লাগে (greedy)।"""
        parts, cur = 1, 0
        for x in nums:
            if cur + x > cap:        # এই সংখ্যা ঢোকালে cap ছাড়ায়
                parts += 1           # নতুন টুকরো
                cur = x
            else:
                cur += x
        return parts

    lo, hi = max(nums), sum(nums)    # answer space
    while lo < hi:
        mid = (lo + hi) // 2
        if need(mid) <= m:           # mid যথেষ্ট -> আরও ছোট খোঁজো
            hi = mid
        else:                        # mid ছোট পড়ছে -> বড় লাগবে
            lo = mid + 1
    return lo


def split_brute(nums, m):
    """সব ভাগ পরীক্ষা করে — reference (ছোট input)।"""
    n = len(nums)
    best = [float('inf')]

    def rec(start, parts_left, cur_max):
        if parts_left == 1:
            seg = sum(nums[start:])
            best[0] = min(best[0], max(cur_max, seg))
            return
        s = 0
        for end in range(start, n - parts_left + 1):
            s += nums[end]
            rec(end + 1, parts_left - 1, max(cur_max, s))

    rec(0, m, 0)
    return best[0]


# --- হাতে বাছা test ---
assert split_array([7, 2, 5, 10, 8], 2) == 18
assert split_array([1, 2, 3, 4, 5], 2) == 9
assert split_array([1, 4, 4], 3) == 4
assert split_array([10], 1) == 10
assert split_array([1, 1, 1, 1], 4) == 1
assert split_array([1, 2, 3, 4, 5], 1) == 15      # m=1 -> sum

# --- brute force-এর সাথে cross-check ---
import random
random.seed(100)
for _ in range(1500):
    n = random.randint(1, 7)
    arr = [random.randint(0, 9) for _ in range(n)]
    m = random.randint(1, n)
    assert split_array(arr, m) == split_brute(arr, m), (arr, m)

print(split_array([7, 2, 5, 10, 8], 2))   # 18
print(split_array([1, 2, 3, 4, 5], 2))    # 9
print("সব test pass!")

13. Line-by-line explanation

def need(cap):
    parts, cur = 1, 0

cap সীমা মেনে ন্যূনতম টুকরো গুনি। parts শুরুতে 1 (অন্তত এক টুকরো লাগবেই), cur চলতি টুকরোর জমা যোগফল।

if cur + x > cap: parts += 1; cur = x
else: cur += x

চলতি টুকরোয় x যোগ করলে cap ছাড়িয়ে গেলে — এই x দিয়ে নতুন টুকরো শুরু (parts += 1, cur = x)। নাহলে চলতি টুকরোয় ঢুকিয়ে দাও। (x <= cap সবসময়, কারণ lo >= max(nums) — তাই একটা সংখ্যা একাই কখনো cap ছাড়ায় না; না হলে greedy ভুল হতো।)

lo, hi = max(nums), sum(nums)

answer space। lo = max(nums): largest sum কখনো সবচেয়ে বড় একক সংখ্যার চেয়ে ছোট হতে পারে না। hi = sum(nums): সবটা এক ভাগে নিলে largest = sum, এটা সবসময় feasible (m >= 1)।

if need(mid) <= m: hi = mid   else: lo = mid + 1

minimize move: cap=mid-এ m-এর কম-সমান টুকরোয় কুলিয়ে গেলে — এই cap যথেষ্ট, আরও ছোট খোঁজো (hi = mid)। বেশি টুকরো লাগলে — cap ছোট পড়ছে, বাড়াও (lo = mid + 1)। lo == hi-তে loop থামে; সেটাই প্রথম feasible cap = উত্তর। (099-এর হুবহু এক।)

cross-check অংশে 1500টা random কেসে BSoA আর সম্পূর্ণ-অনুসন্ধান brute মিলিয়ে দেখা — সব মিললে সব test pass!।

14. Output walkthrough

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

18
9
সব test pass!

প্রথম লাইন: [7, 2, 5, 10, 8], m=2 → dry run-এ পাওয়া 18। দ্বিতীয়: [1, 2, 3, 4, 5], m=2 → [1,2,3]=6 আর [4,5]=9 → largest 9। তার আগের সব assert (হাতে বাছা + 1500টা random cross-check) চুপচাপ pass। সবশেষে সব test pass! — minimize-the-maximum কাঠামো নিখুঁতভাবে কাজ করছে।

15. Time complexity

O(n log(sum(nums))) — answer space [max, sum]-এ binary search, ধাপ সংখ্যা log(sum − max) ≈ log(sum)। প্রতি ধাপে need(mid) greedy-তে array একবার ঘোরে, O(n)। তাই মোট O(n log(sum))। (DP রাস্তাটা O(m·n²) — কাজ করে, কিন্তু এটা দ্রুত ও সহজ।)

16. Space complexity

O(1) — need-এ শুধু parts, cur; binary search-এ lo, hi, mid। কোনো বাড়তি array বা DP table লাগছে না। input ছাড়া স্মৃতি ধ্রুবক। (brute reference recursion-এ O(m) stack লাগে, কিন্তু আসল সমাধান O(1)।)

17. Common mistakes

1. lo = 0 বা lo = 1 দিয়ে শুরু — cap যদি max(nums)-এর ছোট হয়, সবচেয়ে বড় সংখ্যাটা কোনো ভাগে ধরে না; lo = max(nums) লাগবেই।
2. parts 0 থেকে শুরু — অন্তত 1 টুকরো লাগবেই; parts = 1, নইলে এক কম গোনা হয়ে ভুল উত্তর।
3. maximize move লিখে ফেলা — এটা minimize the maximum; feasible হলে hi = mid (ছোট cap), lo = mid নয়। 098 (Aggressive Cows)-এর maximize-এর সাথে গুলিও না।
4. >= বনাম > ভুল — cur + x > cap হলে নতুন টুকরো; >= লিখলে cap-এ ঠিক পৌঁছানো বৈধ ভাগও ভেঙে বেশি টুকরো গোনা হবে।
5. hi = mid - 1 লেখা — minimize-এ hi = mid (mid নিজেই উত্তর হতে পারে); mid - 1 করলে সঠিক উত্তর হারিয়ে যেতে পারে।

18. Harder problems that inherit this idea

• LeetCode — Capacity To Ship Packages Within D Days (https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/) — এই repo-র 097; ওজন-জাহাজ গল্পে হুবহু একই minimize-max।
• LeetCode — Koko Eating Bananas (https://leetcode.com/problems/koko-eating-bananas/) — এই repo-র 096; "খাওয়ার গতি minimize" — পরিবারের গোড়া।
• LeetCode — Minimum Number of Days to Make m Bouquets (https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/) — ভিন্ন গল্প, একই minimize + greedy/counting check।

19. Pattern learned

Minimize the maximum (via minimize BSoA + greedy split) — guess করো একটা cap, greedy-তে গুনে ন্যূনতম টুকরো <= m কিনা check করো; lo = max, hi = sum; feasible → hi = mid। বড় শিক্ষা: "সবচেয়ে বড় ভাগকে যত ছোট সম্ভব" = cap guess করে 'কয়টা ভাগ লাগে?' গোনা — Koko/Ship/Pages-এর হুবহু কাঠামো, শুধু গল্পের মোড়ক আলাদা।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Split Array = minimize-the-maximum BSoA, Allocate Pages-এর আক্ষরিক যমজ; answer = largest segment sum, check = greedy-তে টুকরো গুনে ≤ m, lo=max(nums), hi=sum(nums), feasible→hi=mid। Signal: 'split into m parts, minimize largest sum' দেখলেই এই ছক মনে পড়ুক।"

পরের ধাপ → 101 — Median of Two Sorted Arrays (partition খোঁজার ভিন্ন স্বাদের binary search)। ভিত্তি → 099 — Allocate Minimum Pages। সম্পর্কিত → 097 — Ship Packages Within D Days।

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

---

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