112 — Minimize Maximum Difference

এই problem-টা দুটো হাতিয়ারকে এক সুতোয় বাঁধে — sort করে পাশাপাশি (adjacent) দেখা আর উত্তরের উপর binary search (BSoA)। আর এটা 100 (Split Array Largest Sum)-এর কাছের আত্মীয়: সেখানে ছিল "সবচেয়ে ভারী ভাগকে minimize", এখানে "সবচেয়ে চওড়া দলের পার্থক্যকে minimize"। গল্প আলাদা, কাঠামো এক। এই level-এ মনে রেখো — কেন কাজ করে সেই যুক্তিটাই আসল।

Source

• Original source: Classic exercise
• Platform: — (classic; related minimize-max: LeetCode Split Array Largest Sum — https://leetcode.com/problems/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

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, যা সর্বনিম্ন।

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 ততক্ষণ এক দলে রাখো, নাহলে নতুন দল)।

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) সেখানেই পরিষ্কার হয়েছিল।

4. Real-life analogy

ভাবো একটা ক্লাসের ছাত্রদের উচ্চতা মেপে তুমি kটা সারিতে দাঁড় করাবে ছবি তোলার জন্য — আর চাও প্রতিটা সারির ভেতরে সবচেয়ে লম্বা আর সবচেয়ে বেঁটে ছাত্রের উচ্চতার ফারাক যেন কম হয় (যাতে সারি গুলো "সমান-সমান" দেখায়)। সবচেয়ে বাজে সারিটার ফারাক যত কম রাখা যায়, ছবি তত সুন্দর।

প্রথম কাজ — সবাইকে উচ্চতা অনুযায়ী লাইনে দাঁড় করাও (sort)। তারপর লাইনটাকে k টুকরো করো, প্রতি টুকরো এক সারি। এখন বুদ্ধির খেলা — মনে মনে একটা "সর্বোচ্চ অনুমোদিত ফারাক" ধরো; লাইন ধরে এগোও, ফারাক সেই সীমা ছাড়ালেই নতুন সারি শুরু করো, আর গোনো কতগুলো সারি লাগল। k-এর কম-সমান লাগলে সীমা আরও ছোট করার চেষ্টা করো; বেশি লাগলে সীমা বাড়াও। ঠিক যেখানে "k সারিতে কুলিয়ে যায় কিন্তু এক ইঞ্চি কমালেই বেশি লাগে" — সেই ফারাকই উত্তর।

5. Visual explanation

nums = [1, 5, 6, 2, 8], k = 2। আগে sort → [1, 2, 5, 6, 8], পাশাপাশি ফাঁক দেখি:

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):

 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-এর সৌন্দর্য।

6. Example input and output

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।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — sorted array-তে k−1টা কাটা দাগ বসানোর সব উপায় চেষ্টা করো, প্রতিবার max group-range বের করো, সবচেয়ে ছোটটা রাখো। কাটা বসে n−1টা পাশাপাশি ফাঁকে, তাই সব combination:

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।

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-তে গোনো ন্যূনতম কত দল লাগে:

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-এর হুবহু আত্মীয়।

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-এর সাথে মিলে গেল।

12. Python solution

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

s = sorted(nums)

প্রথমেই sort — এতে প্রতিটা দল sorted array-র পরপর টুকরো হতে পারে, আর দলের range = টুকরোর শেষ − শুরু। sort না করলে "কোন সংখ্যা কোন দলে" সমস্যা বহুগুণ কঠিন থাকত।

if k >= n: return 0

দল সংখ্যা উপাদান সংখ্যার সমান-বা-বেশি হলে প্রতিটা সংখ্যা একা থাকতে পারে → প্রতিটা দলের range 0 → max difference 0। (এই guard না থাকলে নিচে hi ও greedy অপ্রয়োজনীয় কাজ করত, আর অর্থও হারাত।)

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 কারণ — যত দেরিতে সম্ভব নতুন দল খুললে দল সংখ্যা সবচেয়ে কম থাকে।

lo, hi = 0, s[-1] - s[0]

answer space। সবচেয়ে ছোট সম্ভাব্য max difference 0 (সব একা/সমান), সবচেয়ে বড় পুরো array-র range (এক দল)। উত্তর এই বন্ধ পরিসরে।

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

14. Output walkthrough

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

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 প্রতিটা কেসে নিখুঁত।

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 বা শুধু কোনো একক মান দিলে ভুল।

18. Harder problems that inherit this idea

• LeetCode — Split Array Largest Sum (https://leetcode.com/problems/split-array-largest-sum/) — এই repo-র 100; "ভাগের sum" minimize, এটার সরাসরি ভিত্তি।
• LeetCode — Divide Chocolate (https://leetcode.com/problems/divide-chocolate/) — k+1 টুকরোয় ভাগ করে সবচেয়ে ছোট টুকরো maximize (উল্টো দিক, একই BSoA+greedy)।
• LeetCode — Minimize the Maximum Difference of Pairs (https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/) — sort + adjacent + BSoA-র আরেক রূপ (জোড়া বানিয়ে max পার্থক্য minimize)।

19. Pattern learned

Minimize the maximum (sort + adjacent grouping + BSoA) — sort করো (দল contiguous হয়), max difference-এর উপর binary search; প্রতি limit-এ greedy-তে দল গুনে <= k check; lo = 0, hi = range, feasible → hi = mid। বড় শিক্ষা: "k দলে ভেঙে সবচেয়ে চওড়া দলকে minimize" = sort তারপর minimize-the-maximum BSoA — 100-এর হুবহু কাঠামো, শুধু 'sum'-এর জায়গায় 'range' আর গোড়ায় একটা sort।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Minimize Max Difference = sort + minimize-the-maximum BSoA (100-এর আত্মীয়); answer = সবচেয়ে চওড়া দলের range, check = greedy-তে দল গুনে ≤ k, lo=0, hi=max−min, feasible→hi=mid। Signal: 'k দলে ভাগ + সবচেয়ে বড় দলকে minimize' দেখলেই sort তারপর BSoA মনে পড়ুক। k≥n → 0।"

পরের ধাপ → এই level শেষ; এবার ../../09-geometry-coordinate-math/problems/README.md। ভিত্তি → 100 — Split Array Largest Sum। সম্পর্কিত → 111 — Make Array Equal with Minimum Moves।

ফিরে দেখা: এই 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" লেখো।