Problem link ও উৎস
- **Original source:** LeetCode — Split Array Largest Sum
- **Platform:** LeetCode —
- **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
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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-এর চেয়ে বড় বা সমান।
### Input ও output {#6-example-input-and-output}
```text
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 ভাগ অসম্ভব)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে পরপর সাজানো কয়েকটা বাক্স আছে, প্রত্যেকটার আলাদা ওজন। `m` জন কুলিকে এগুলো ভাগ করে বইতে দিতে হবে — কিন্তু প্রত্যেক কুলি **পরপর কয়েকটা** বাক্সই নিতে পারে (মাঝখান থেকে তুলে নেওয়া বারণ, লাইন ভাঙা যাবে না)।
তুমি ন্যায্য নেতা — চাও যে কুলি সবচেয়ে ভারী বোঝা পায়, তার বোঝাটাও যেন যথাসম্ভব হালকা হয়। কীভাবে ঠিক করবে? মনে মনে একটা সীমা ধরো — "কেউ X কেজির বেশি বইবে না"। তারপর লাইন ধরে কুলি বসাও: একজনকে যতক্ষণ X-এর মধ্যে থাকে বাক্স দাও, ছাড়িয়ে গেলে পরের কুলি ডাকো। শেষে গোনো — কতজন কুলি লাগল? `m`-এর কম-সমান হলে X যথেষ্ট ছোট (আরও ছোট চেষ্টা করো); বেশি লাগলে X বাড়াও। ঠিক যেখানে "ঠিক `m` জনে কুলিয়ে যায় কিন্তু এক কেজি কমালেই বেশি লাগে" — সেই X-ই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 বলা হলেও তোমার কাছে এটা এখন চেনা।
### ভেতরের অঙ্ক {#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 ছাড়ালে নতুন টুকরো খোলো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল চিন্তা — সব রকম ভাবে array-কে `m` টুকরোয় কাটো, প্রতিবার largest sum বের করো, সবচেয়ে ছোটটা রাখো। `n` লম্বা array-কে `m` টুকরোয় ভাগ করতে `m−1`টা "কাটা দাগ" বসাতে হয় `n−1`টা সম্ভব ফাঁকে — সেটা recursion দিয়ে করা যায়:
```python
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।
```text
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-তে গুনি ন্যূনতম কত টুকরো লাগে:
```python
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, সব এই একই দরজা দিয়ে ঢোকে।
### ছবিতে বোঝা {#5-visual-explanation}
`nums = [7, 2, 5, 10, 8]`, `m = 2`। answer space `[max(nums), sum(nums)] = [10, 32]`। কয়েকটা cap-এ greedy চালিয়ে দেখি কত টুকরো লাগে:
```text
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।
### ছোট input-এ ধাপে ধাপে {#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-এর সাথে মিলে গেল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
def need(cap):
parts, cur = 1, 0
```
`cap` সীমা মেনে ন্যূনতম টুকরো গুনি। `parts` শুরুতে 1 (অন্তত এক টুকরো লাগবেই), `cur` চলতি টুকরোর জমা যোগফল।
```text
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 ভুল হতো।)
```text
lo, hi = max(nums), sum(nums)
```
answer space। `lo = max(nums)`: largest sum কখনো সবচেয়ে বড় একক সংখ্যার চেয়ে ছোট হতে পারে না। `hi = sum(nums)`: সবটা এক ভাগে নিলে largest = sum, এটা সবসময় feasible (`m >= 1`)।
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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 কাঠামো নিখুঁতভাবে কাজ করছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` করলে সঠিক উত্তর হারিয়ে যেতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Capacity To Ship Packages Within D Days** (