Problem link ও উৎস
- **Original source:** Classic exercise
- **Platform:** — (classic; related minimize-max: LeetCode Split Array Largest Sum —
)
- **Topic:** Math-based programming fundamentals → Level 8: Greedy Math Tricks
- **Difficulty:** Medium
- **Pattern:** sort + adjacent / BSoA (sort করে পাশাপাশি ফাঁক দেখা, উত্তরের উপর binary search)
- **Basic idea inherited from:** 100 — Split Array Largest Sum
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `nums` দেওয়া, আর একটা সংখ্যা `k`। array-র সংখ্যাগুলোকে ঠিক `k`টা **দল (group)**-এ ভাগ করতে হবে (প্রতিটা দল non-empty, প্রতিটা সংখ্যা ঠিক একটা দলে)। প্রতিটা দলের "পার্থক্য" = ঐ দলের সবচেয়ে বড় ও সবচেয়ে ছোট সংখ্যার বিয়োগফল (range)। `k`টা দলের মধ্যে যেটার পার্থক্য সবচেয়ে বেশি, সেটাই ওই ভাগের "maximum difference"।
প্রশ্ন: এমনভাবে `k` দলে ভাগ করো যাতে এই **maximum difference যত ছোট সম্ভব** হয়। সেই সর্বনিম্ন মানটাই উত্তর।
মূল চাবি — সংখ্যাগুলো **sort** করলে সমস্যা সহজ হয়ে যায়: তখন প্রতিটা দল sorted array-র একটা **পরপর (contiguous) টুকরো** হলেই সবচেয়ে ভালো, আর দলের পার্থক্য = টুকরোর শেষ − শুরু। উদাহরণ: `nums = [1, 5, 6, 2, 8]`, `k = 2`। sorted `[1, 2, 5, 6, 8]`-কে `[1, 2]` (range 1) আর `[5, 6, 8]` (range 3) ভাগ করলে max difference = **3**, যা সর্বনিম্ন।
### Input ও output {#6-example-input-and-output}
```text
nums k output সেরা ভাগ (sorted-এ)
-----------------------------------------------------------
[1, 5, 6, 2, 8] 2 3 [1,2] | [5,6,8]
[1, 3, 6, 19, 20] 3 2 [1,3] | [6] | [19,20] (বড় ফাঁক দুটো কাটা)
[10, 20, 30] 1 20 এক দল -> range = 30-10
[4, 4, 4] 2 0 সব সমান, range 0
[1, 2, 3, 4] 4 0 প্রতিটা একা -> range 0
[3, 1, 9, 4] 2 3 sorted [1,3,4,9]: [1,3,4] | [9]
```
মূল edge case: **`k >= len(nums)`** → প্রতিটা সংখ্যা একা (বা কিছু দল একক) → প্রতিটা দলের range 0 → উত্তর **0**; **`k = 1`** → পুরোটা এক দল → উত্তর `max(nums) − min(nums)`; **সব সংখ্যা সমান** → যেকোনো ভাগে range 0।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ক্লাসের ছাত্রদের উচ্চতা মেপে তুমি `k`টা সারিতে দাঁড় করাবে ছবি তোলার জন্য — আর চাও প্রতিটা সারির ভেতরে সবচেয়ে লম্বা আর সবচেয়ে বেঁটে ছাত্রের উচ্চতার ফারাক যেন কম হয় (যাতে সারি গুলো "সমান-সমান" দেখায়)। সবচেয়ে বাজে সারিটার ফারাক যত কম রাখা যায়, ছবি তত সুন্দর।
প্রথম কাজ — সবাইকে উচ্চতা অনুযায়ী লাইনে দাঁড় করাও (sort)। তারপর লাইনটাকে `k` টুকরো করো, প্রতি টুকরো এক সারি। এখন বুদ্ধির খেলা — মনে মনে একটা "সর্বোচ্চ অনুমোদিত ফারাক" ধরো; লাইন ধরে এগোও, ফারাক সেই সীমা ছাড়ালেই নতুন সারি শুরু করো, আর গোনো কতগুলো সারি লাগল। `k`-এর কম-সমান লাগলে সীমা আরও ছোট করার চেষ্টা করো; বেশি লাগলে সীমা বাড়াও। ঠিক যেখানে "`k` সারিতে কুলিয়ে যায় কিন্তু এক ইঞ্চি কমালেই বেশি লাগে" — সেই ফারাকই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **100 — Split Array Largest Sum**-এর কাঁধে। 100-এ ছিল: array-কে `m` contiguous ভাগে কেটে সবচেয়ে ভারী ভাগের **sum** minimize করা — BSoA(cap) + greedy "কয়টা ভাগ লাগে" check দিয়ে। এখানে হুবহু সেই ছাঁচ, শুধু "ভাগের sum"-এর জায়গায় "দলের range (max − min)", আর গোড়ায় একটা **sort** ধাপ (যাতে দল contiguous হয়)।
মানে minimize-the-maximum পরিবারেরই আরেক সদস্য (Koko → Ship → Pages → Split → এটা)। 100-এর `can(cap)` greedy আর binary search চলন এখানে প্রায় copy-paste — শুধু check-এর ভেতরে যোগফলের বদলে "চলতি দলের শুরু থেকে দূরত্ব"। তাই আটকে গেলে 100-এ ফিরে দেখো; minimize-move (`hi = mid`) সেখানেই পরিষ্কার হয়েছিল।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো ধারণা একসাথে। **এক — sort করলে দল contiguous হয়।** কেন? কোনো দলের range শুধু তার min ও max-এ নির্ভর করে। যদি দুটো দলের সংখ্যা number line-এ মেশানো (interleaved) থাকে, তাদের "আলাদা করে" পরপর সাজালে কোনো দলের range বাড়ে না — তাই সেরা সমাধানে প্রতিটা দল sorted array-র একটা টানা টুকরো। ফলে দল ভাগ করা = sorted array-তে `k−1`টা "কাটা দাগ" বসানো, আর কাটা শুধু **পাশাপাশি (adjacent) সংখ্যার ফাঁকে** হয়।
**দুই — উত্তরের উপর binary search (BSoA)।** সরাসরি সেরা ভাগ খোঁজা কঠিন, তাই প্রশ্ন উল্টাই: "প্রতিটা দলের পার্থক্য সর্বোচ্চ `limit` রাখলে, কি `k` বা তার কম দলে কুলিয়ে যায়?" — এই `feasible(limit)` **monotonic**: limit বাড়লে কম দল লাগে, কমলে বেশি। তাই F...FT...T রেখায় প্রথম "T" খুঁজতে binary search, আর প্রতিটা limit-এ ন্যূনতম দল গোনে একটা greedy (sorted-এ সামনে থেকে যতক্ষণ range ≤ limit ততক্ষণ এক দলে রাখো, নাহলে নতুন দল)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — sorted array-তে `k−1`টা কাটা দাগ বসানোর **সব** উপায় চেষ্টা করো, প্রতিবার max group-range বের করো, সবচেয়ে ছোটটা রাখো। কাটা বসে `n−1`টা পাশাপাশি ফাঁকে, তাই সব combination:
```python
from itertools import combinations
def minimize_brute(nums, k):
s = sorted(nums)
n = len(s)
if k >= n:
return 0
best = float('inf')
for cuts in combinations(range(1, n), k - 1): # k-1 কাটা দাগ
idx = [0] + list(cuts) + [n]
mx = max(s[b - 1] - s[a] for a, b in zip(idx, idx[1:]))
best = min(best, mx)
return best
```
এটা প্রতিটা সম্ভাব্য ভাগ পরীক্ষা করে, তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। ছোট `n`-এ চমৎকার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
কাটা-দাগ বসানোর উপায় `C(n−1, k−1)` — combinatorially বিস্ফোরক। `n = 30`, `k = 15` হলেই কোটি কোটি সম্ভাবনা; বড় input-এ নিশ্চিত Time Limit Exceeded।
```text
n=30, k=15 হলে:
brute force: C(29, 14) ≈ 6.8 কোটি ভাগ (বিস্ফোরক)
sort + BSoA: n log n (sort) + log(range)·n (search) ≈ অল্প হাজার ধাপ (চটপট)
```
মূল অপচয় — আমরা সব সম্ভাব্য কাটা ঘুরে দেখছি, যেখানে গণিত (monotonicity) আগেই বলে দিয়েছে উত্তরের উপর binary search চলবে। sort-এর পর প্রতিটা limit-এ গোনাটা greedy-তে O(n), আর limit খোঁজা log-ধাপে — সব সম্ভাবনা ঘোরার দরকারই নেই।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — sort করো (দল contiguous হয়), তারপর **উত্তরের (max difference) উপর binary search**। প্রতিটা guess `limit`-এ greedy-তে গোনো ন্যূনতম কত দল লাগে:
```python
def minimize_max_diff(nums, k):
s = sorted(nums)
n = len(s)
if k >= n:
return 0
def groups_needed(limit): # limit সীমায় কয়টা দল লাগে
groups, start = 1, s[0]
for x in s[1:]:
if x - start > limit: # চলতি দলের range সীমা ছাড়াল
groups += 1 # নতুন দল শুরু
start = x
return groups
lo, hi = 0, s[-1] - s[0]
while lo < hi:
mid = (lo + hi) // 2
if groups_needed(mid) <= k: # mid যথেষ্ট বড় -> আরও ছোট খোঁজো
hi = mid
else:
lo = mid + 1
return lo
```
sort O(n log n), তারপর `log(range)` ধাপ, প্রতি ধাপে greedy O(n) — সব মিলিয়ে O(n log n + n log(range))।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" দুটো একসাথে। প্রথম — **sort করলে "কোন সংখ্যা কোন দলে" এর অসীম সম্ভাবনা ভেঙে শুধু "পাশাপাশি ফাঁকে কোথায় কাটব" থেকে যায়** (দল বাধ্যতামূলকভাবে contiguous)। দ্বিতীয় — **"সেরা ভাগ কোনটা?" সরাসরি কঠিন, কিন্তু "max difference ≤ limit রাখা যায় কি?" সহজ — আর সেটাই যথেষ্ট**, কারণ সেই প্রশ্নের উত্তর limit-এর সাথে monotonic।
দুটো মিলিয়ে: sort → পাশাপাশি ফাঁক → limit-এর উপর binary search + greedy দল-গণনা। "k দলে ভাগ করে সবচেয়ে চওড়া/ভারী দলকে minimize" দেখলেই এই "sort + minimize-the-maximum BSoA" ছকটা মাথায় আসুক — 100-এর হুবহু আত্মীয়।
### ছবিতে বোঝা {#5-visual-explanation}
`nums = [1, 5, 6, 2, 8]`, `k = 2`। আগে sort → `[1, 2, 5, 6, 8]`, পাশাপাশি ফাঁক দেখি:
```text
sorted: 1 2 5 6 8
gaps: 1 3 1 2 (পাশাপাশি পার্থক্য)
^^^ সবচেয়ে বড় ফাঁক এখানে
k=2 মানে 1টা কাটা দাগ -> সবচেয়ে বড় ফাঁকে কাটলে সেরা:
[1, 2] | [5, 6, 8]
range 1 range 3 -> max difference = 3
```
BSoA-র F/T সিঁড়ি — predicate "limit সীমায় ≤ k দলে ভাগ হয়?" (groups_needed ≤ 2):
```text
limit: 0 1 2 3 4 5 6 7
groups_need: 5 4 4 2 2 2 2 1
≤ 2 ?: F F F T T T T T
^
প্রথম T = limit 3 -> উত্তর = 3
```
লক্ষ করো — limit যত বাড়ে, দল তত কমে (monotonic), তাই সাজানো F...FT...T রেখা; binary search প্রথম T (=3) এনে দেয়। আর কাটাটা পড়ল সবচেয়ে বড় পাশাপাশি ফাঁকে (2 আর 5-এর মাঝে) — sort + adjacent-এর সৌন্দর্য।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [1, 5, 6, 2, 8]`, `k = 2`। sort → `s = [1, 2, 5, 6, 8]`, range = `8 − 1 = 7`। `k < n` (2 < 5), তাই BSoA। `lo = 0, hi = 7`:
| lo | hi | mid=(lo+hi)//2 | groups_needed(mid) | ≤ 2? | নতুন lo, hi |
| --- | --- | --- | --- | --- | --- |
| 0 | 7 | 3 | [1,2],[5,6,8] → 2 | হ্যাঁ | hi = 3 |
| 0 | 3 | 1 | [1,2],[5,6],[8] → 3 | না | lo = 2 |
| 2 | 3 | 2 | [1,2],[5,6],[8] → 3 | না | lo = 3 |
| 3 | 3 | — | lo == hi, loop থামল | — | উত্তর 3 |
`groups_needed(3)` কীভাবে 2 হলো: start=1; 2−1=1 ≤ 3 (same), 5−1=4 > 3 নতুন দল start=5, 6−5=1 ≤ 3 (same), 8−5=3 ≤ 3 (same)। শেষ → 2 দল। শেষ অবস্থা `lo = hi = 3` — সেই সর্বনিম্ন max difference, brute force-এর সাথে মিলে গেল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def minimize_max_diff(nums, k):
"""nums-কে k দলে ভেঙে সবচেয়ে চওড়া দলের range minimize করে। O(n log n + n log range)।"""
s = sorted(nums)
n = len(s)
if k >= n:
return 0 # প্রতিটা একা -> range 0
def groups_needed(limit):
"""প্রতিটা দলের range <= limit রাখতে ন্যূনতম কয়টা দল (greedy, sorted-এ)।"""
groups, start = 1, s[0]
for x in s[1:]:
if x - start > limit: # চলতি দলের range সীমা ছাড়াবে
groups += 1 # নতুন দল
start = x
return groups
lo, hi = 0, s[-1] - s[0] # answer space: 0 থেকে পুরো range
while lo < hi:
mid = (lo + hi) // 2
if groups_needed(mid) <= k: # mid যথেষ্ট -> আরও ছোট
hi = mid
else: # mid ছোট -> বড় limit লাগবে
lo = mid + 1
return lo
def minimize_brute(nums, k):
"""সব কাটা পরীক্ষা করে — reference (ছোট input)।"""
from itertools import combinations
s = sorted(nums)
n = len(s)
if k >= n:
return 0
best = float('inf')
for cuts in combinations(range(1, n), k - 1):
idx = [0] + list(cuts) + [n]
mx = max(s[b - 1] - s[a] for a, b in zip(idx, idx[1:]))
best = min(best, mx)
return best
# --- হাতে বাছা test ---
assert minimize_max_diff([1, 5, 6, 2, 8], 2) == 3
assert minimize_max_diff([1, 3, 6, 19, 20], 3) == 2
assert minimize_max_diff([10, 20, 30], 1) == 20
assert minimize_max_diff([4, 4, 4], 2) == 0
assert minimize_max_diff([1, 2, 3, 4], 4) == 0
assert minimize_max_diff([3, 1, 9, 4], 2) == 3
# --- brute force-এর সাথে cross-check (random) ---
import random
random.seed(3)
for _ in range(4000):
n = random.randint(1, 7)
arr = [random.randint(0, 12) for _ in range(n)]
k = random.randint(1, n)
assert minimize_max_diff(arr, k) == minimize_brute(arr, k), (arr, k)
print(minimize_max_diff([1, 5, 6, 2, 8], 2)) # 3
print(minimize_max_diff([1, 3, 6, 19, 20], 3)) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
s = sorted(nums)
```
প্রথমেই sort — এতে প্রতিটা দল sorted array-র পরপর টুকরো হতে পারে, আর দলের range = টুকরোর শেষ − শুরু। sort না করলে "কোন সংখ্যা কোন দলে" সমস্যা বহুগুণ কঠিন থাকত।
```text
if k >= n: return 0
```
দল সংখ্যা উপাদান সংখ্যার সমান-বা-বেশি হলে প্রতিটা সংখ্যা একা থাকতে পারে → প্রতিটা দলের range 0 → max difference 0। (এই guard না থাকলে নিচে `hi` ও greedy অপ্রয়োজনীয় কাজ করত, আর অর্থও হারাত।)
```text
def groups_needed(limit):
groups, start = 1, s[0]
if x - start > limit: groups += 1; start = x
```
`limit` সীমা মেনে ন্যূনতম দল গুনি। `start` = চলতি দলের সবচেয়ে ছোট সংখ্যা (sorted, তাই দলের প্রথম)। নতুন সংখ্যা `x` যোগ করলে `x − start` হলো দলের নতুন range; সেটা `limit` ছাড়ালে এই `x` দিয়ে **নতুন** দল শুরু (`groups += 1`, `start = x`)। greedy কারণ — যত দেরিতে সম্ভব নতুন দল খুললে দল সংখ্যা সবচেয়ে কম থাকে।
```text
lo, hi = 0, s[-1] - s[0]
```
answer space। সবচেয়ে ছোট সম্ভাব্য max difference 0 (সব একা/সমান), সবচেয়ে বড় পুরো array-র range (এক দল)। উত্তর এই বন্ধ পরিসরে।
```text
if groups_needed(mid) <= k: hi = mid else: lo = mid + 1
```
minimize move (100-এর হুবহু): limit=mid-এ `k`-এর কম-সমান দলে কুলিয়ে গেলে — mid যথেষ্ট, তবে নিজেও উত্তর হতে পারে (`hi = mid`)। বেশি দল লাগলে — limit ছোট পড়ছে, বাড়াও (`lo = mid + 1`)। `lo == hi`-তে loop থামে; সেটাই সর্বনিম্ন max difference।
cross-check অংশে 4000টা random কেসে BSoA আর সম্পূর্ণ-অনুসন্ধান brute মিলিয়ে দেখা — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
3
2
সব test pass!
```
প্রথম লাইন: `[1, 5, 6, 2, 8]`, `k=2` → dry run-এ পাওয়া 3 (`[1,2]` ও `[5,6,8]`)। দ্বিতীয়: `[1, 3, 6, 19, 20]`, `k=3` → sorted-এ দুটো বড় ফাঁক (6→19, 3→6 নয়) কেটে `[1,3]`, `[6]`, `[19,20]` → max range 2। তার আগের সব `assert` (হাতে বাছা + 4000টা random cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — sort + BSoA প্রতিটা কেসে নিখুঁত।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n log n + n log(range))** — প্রথমে sort O(n log n)। তারপর answer space `[0, range]`-এ binary search, ধাপ `log(range)`; প্রতি ধাপে `groups_needed` greedy O(n)। তাই দ্বিতীয় অংশ O(n log(range))। সাধারণত sort-ই প্রধান খরচ। (brute-এর combinatorial বিস্ফোরণ থেকে বিশাল লাফ।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — `sorted()` একটা নতুন list বানায় (চাইলে in-place sort-এ O(1) বাড়তি)। `groups_needed`-এ শুধু `groups`, `start`; binary search-এ `lo, hi, mid`। মূল গণনায় বাড়তি array লাগে না। (brute reference-এ combinations iterate করতে সামান্য বেশি, কিন্তু আসল সমাধান O(n) sort-এর জন্য।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **sort না করা** — sort ছাড়া দল contiguous ধরে নেওয়া ভুল; greedy তখন বাজে ভাগ দেবে। আগে sort করতেই হবে।
2. **maximize move লিখে ফেলা** — এটা minimize the *maximum*; feasible হলে `hi = mid` (ছোট limit), `lo = mid` নয়। 098 (maximize)-এর সাথে গুলিও না।
3. **`>` বনাম `>=` ভুল** — `x - start > limit` হলে নতুন দল; `>=` লিখলে ঠিক limit ছোঁয়া বৈধ দলও ভেঙে বেশি দল গোনা হবে।
4. **`k >= n` edge না সামলানো** — তখন উত্তর 0; না সামলালে অপ্রয়োজনীয় কাজ বা ভুল।
5. **answer space ভুল** — `lo` 0 থেকে শুরু (range 0 সম্ভব), `hi = max − min`; `hi`-তে শুধু max বা শুধু কোনো একক মান দিলে ভুল।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Split Array Largest Sum** (