020 — Smallest Range Covering Elements from K Lists¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

Original source: Classic k-way merge with a coverage window
Platform: LeetCode — https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
Topic: heap / priority queue
Difficulty: Hard
Pattern: K-way merge (min-heap of frontiers) + tracking the current max → window
Basic idea inherited from: 02-arrays-and-strings sliding window + 08 k-way merge

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

k-টা list দেওয়া আছে, প্রতিটা বাড়তে থাকা (sorted) ক্রমে সাজানো। তোমাকে এমন একটা ছোট range [a, b] খুঁজতে হবে যেটার ভেতরে প্রতিটা list থেকে অন্তত একটা করে সংখ্যা পড়ে। range যত ছোট (b - a যত কম) তত ভালো; tie হলে যে range-এর a ছোট সেটা নাও। সেই [a, b] return করো।

উদাহরণ

[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]  ->  [20, 24]

Input ও output¶

উদাহরণ

Input : [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]   -> Output: [20, 24]
Input : [[1,2,3],[1,2,3],[1,2,3]]                     -> Output: [1, 1]   (সব মিলে যায়)
Input : [[10],[11]]                                    -> Output: [10, 11]
Input : [[1,10,11],[20,30]]                            -> Output: [11, 20]

চেনা উদাহরণে বোঝা¶

ভাবো k-টা দৌড়বিদ, প্রত্যেকে নিজের track-এ সামনে এগোচ্ছে (sorted)। তুমি চাও এক মুহূর্ত যেখানে সবাই একে অপরের যত কাছাকাছি সম্ভব। সবচেয়ে পিছিয়ে থাকা দৌড়বিদকে এক পা সামনে এগিয়ে দাও (তার পরের checkpoint-এ) — এতে দলটা কুঁকড়ে আসে, আর সবচেয়ে এগিয়ে থাকা জন তো পিছায় না। প্রতিবার দলের "ছড়ানো" (max − min) মেপে রাখো; কোনো একজন track শেষ করলে খেলা শেষ। "সবচেয়ে পিছিয়ে থাকাকে চট করে দাও" — সেই যন্ত্রই min-heap।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত দুটো জিনিসের জোড়: 08-এর k-way merge (প্রতিটা list-এর সামনের element নিয়ে একটা min-heap, বারবার সবচেয়ে ছোটটা টানা — যেমন 012/017-এ), আর 02-arrays-and-strings-এর sliding window চিন্তা (একটা window যেটার ভেতরে সব list "covered" থাকে)। এখানে window-টা সরাসরি index-এর না, বরং প্রতিটা list থেকে একটা করে value নিয়ে গড়া।

ভেতরের যুক্তি¶

লুকানো logic: যদি প্রতিটা list থেকে ঠিক একটা করে value বেছে নাও, তাহলে সেই k-টা value-এর [min, max]-ই একটা valid range। তুমি চাও max - min ছোট করতে। min-টা যে list থেকে এসেছে, সেই list-এ একটু বড় value-এ এগোলে min বাড়ে (range সঙ্কুচিত হওয়ার সুযোগ), কিন্তু max কখনো কমে না। তাই বারবার বর্তমান min-কে তার পরের element দিয়ে replace করে min বাড়াও, প্রতিবার [min, max] মেপে রাখো — কোনো list শেষ হলে থামো।

কী দিয়ে তথ্য রাখব¶

একটা min-heap (k-way merge frontier)। প্রতিটা entry (value, list_index, element_index) — কোন list-এর কোন position থেকে এসেছে তা মনে রাখার জন্য। সাথে একটা সাধারণ variable current_max — heap-এ এই মুহূর্তে থাকা সব value-এর মধ্যে সবচেয়ে বড়টা।

এটি কেন উপযুক্ত¶

প্রতি step-এ তোমার দরকার শুধু বর্তমান minimum (যাকে এগিয়ে দিলে window সঙ্কুচিত হতে পারে)। min-heap সেটা top-এ O(1)-এ দেয়, pop/push O(log k)। max আলাদা variable-এ রাখা সস্তা, কারণ নতুন value push করার সময়ই সেটা update করা যায়। পুরো merged sequence কখনো বানাতে হয় না — heap-এ একসাথে বড়জোর k-টা element থাকে।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা list থেকে একটা করে value-এর সব combination বানাও, প্রতিটার [min, max] মাপো, সবচেয়ে ছোট range রাখো।

উদাহরণ

ছোট example: L0=[1,4], L1=[2,6]
choices: (1,2)->width 1; (1,6)->width 5; (4,2)->width 2; (4,6)->width 2
সব combination-এর মধ্যে best range [1,2]

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা list-এর length যদি গড়ে m হয়, combination-সংখ্যা O(mᵏ) — exponential, k একটু বড় হলেই অসম্ভব। অথচ আমাদের সব combination দেখার দরকার নেই: কেবল min-কে এগিয়ে যাওয়াটাই range সঙ্কুচিত করার একমাত্র productive move, তাই smart traversal-এ O(n log k)-তে নামা যায়।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: একটা valid window-এ window সঙ্কুচিত করার একমাত্র উপায় হলো বর্তমান minimum-কে বড় করা — অর্থাৎ যে list থেকে min এসেছে সেই list-এ পরের element-এ যাওয়া। max কমানোর কোনো উপায় নেই (সেটা শুধু বাড়ে), তাই min-কে যতটা সম্ভব max-এর কাছে টেনে আনাই খেলা। আর min সবসময় heap-এর top-এ।

আরও কম কাজে সমাধান¶

প্রতিটা list-এর প্রথম element নিয়ে min-heap বানাও, current_max = তাদের সর্বোচ্চ। Loop: top (current min) pop করো; [min, current_max] যদি আগের best-এর চেয়ে ছোট হয়, best update করো। সেই list-এ পরের element থাকলে push করো (আর current_max দরকারমতো update করো); না থাকলে থামো — ওই list আর কোনো value দিতে পারবে না, তাই কোনো future window সম্পূর্ণ হবে না। মোট O(n log k)।

ভাবনার পরিবর্তন¶

মোচড়: "smallest range" না ভেবে ভাবো "k-টা sorted stream একসাথে merge করছি, আর প্রতি মুহূর্তে heap-এ থাকা k-টা frontier value-ই আমার current window।" min এগোলে window নড়ে। "প্রতিটা group থেকে অন্তত একটা cover করতে হবে, sorted lists" — শুনলেই k-way-merge-min-heap + একটা running max মাথায় আনবে।

ছবিতে বোঝা¶

Lists: L0=[4,10,15,24,26], L1=[0,9,12,20], L2=[5,18,22,30]। নিচে frontier-এর column-গুলো list order-এ, heap-এর internal array order-এ নয়। প্রতি row-তে তিন list-ই represented।

L0	L1	L2	বর্তমান range	পরের কাজ	এখন পর্যন্ত best
4	0	5	[0,5], width 5	L1: 0→9	[0,5]
4	9	5	[4,9], width 5	L0: 4→10	[0,5]
10	9	5	[5,10], width 5	L2: 5→18	[0,5]
10	9	18	[9,18], width 9	L1: 9→12	[0,5]
10	12	18	[10,18], width 8	L0: 10→15	[0,5]
15	12	18	[12,18], width 6	L1: 12→20	[0,5]
15	20	18	[15,20], width 5	L0: 15→24	[0,5]
24	20	18	[18,24], width 6	L2: 18→22	[0,5]
24	20	22	[20,24], width 4	L1 শেষ; থামুন	[20,24]

Width সমান হলে ছোট left boundary জেতে, তাই প্রথম কয়েকটি width-5 range [0,5]-কে সরায়নি। শেষ row-তে range ছোট হয়েছে।

ছোট input-এ ধাপে ধাপে¶

Input [[1,10,11],[20,30]]:

frontier min-heap: (1, L0, idx0), (20, L1, idx0); current_max = 20
best = কিছু না (∞ width)
pop (1, L0): window [1, 20], width 19 → best = [1, 20]; L0-এ পরের 10 push; current_max = max(20, 10) = 20
pop (10, L0): window [10, 20], width 10 < 19 → best = [10, 20]; L0-এ পরের 11 push; current_max = 20
pop (11, L0): window [11, 20], width 9 < 10 → best = [11, 20]; L0-এ পরের element নেই → থামো
return [11, 20]

কোড ও ব্যাখ্যা¶

Python¶

Python

import heapq

def smallest_range(nums):
    # প্রতিটা list-এর প্রথম element নিয়ে frontier min-heap: (value, list_idx, elem_idx)
    heap = [(rows[0], i, 0) for i, rows in enumerate(nums)]
    heapq.heapify(heap)
    current_max = max(rows[0] for rows in nums)   # frontier-এর সর্বোচ্চ

    best_lo, best_hi = heap[0][0], current_max     # একটা valid window দিয়ে শুরু

    while True:
        val, li, ei = heapq.heappop(heap)          # বর্তমান minimum
        if current_max - val < best_hi - best_lo:  # আরও ছোট window?
            best_lo, best_hi = val, current_max
        if ei + 1 == len(nums[li]):                # এই list শেষ -> আর cover সম্ভব না
            break
        nxt = nums[li][ei + 1]                      # একই list-এ পরের element
        current_max = max(current_max, nxt)        # max শুধু বাড়তে পারে
        heapq.heappush(heap, (nxt, li, ei + 1))
    return [best_lo, best_hi]

# ---- tests ----
assert smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]) == [20, 24]
assert smallest_range([[1,2,3],[1,2,3],[1,2,3]]) == [1, 1]   # সব মিলে যায়
assert smallest_range([[10],[11]]) == [10, 11]
assert smallest_range([[1,10,11],[20,30]]) == [11, 20]
assert smallest_range([[5]]) == [5, 5]                       # একটাই list, একটাই value
print("সব test pass!")

কোডের প্রতিটি অংশ¶

heap = [(rows[0], i, 0) for i, rows in enumerate(nums)] — প্রতিটা list-এর প্রথম element, সাথে (list index, element index) যাতে জানি কোথা থেকে এলো।
heapq.heapify(heap) — O(k)-এ min-heap; top সবসময় frontier-এর সবচেয়ে ছোট value।
current_max = max(...) — frontier-এ এই মুহূর্তে থাকা সব value-এর সর্বোচ্চ; window-এর উপরের প্রান্ত।
best_lo, best_hi = heap[0][0], current_max — শুরুতেই একটা valid window (min ও max) রেখে দিই, পরে ছোট পেলে update।
val, li, ei = heapq.heappop(heap) — বর্তমান minimum আর সে কোন list-এর কোন position।
if current_max - val < best_hi - best_lo: — [val, current_max] আগের best-এর চেয়ে সরু হলে best update।
if ei + 1 == len(nums[li]): break — যে list থেকে min এলো সেটা শেষ → আর এগোনো গেলে ওই list cover হবে না, তাই থামো।
current_max = max(current_max, nxt) — নতুন value push-এর আগে max দরকারমতো বাড়াও (কখনো কমে না)।
heapq.heappush(heap, (nxt, li, ei + 1)) — একই list-এর পরের element frontier-এ আনো।

Output মিলিয়ে দেখা¶

smallest_range([[1,10,11],[20,30]]) section 14-এর dry run মেনে [11, 20] দেয় — assert pass। প্রথম বড় example-এ frontier ধীরে ধীরে এগিয়ে [20, 24]-এ সবচেয়ে সরু window পায়। [[1,2,3]] x3-এ শুরুতেই সব list-এ 1 আছে → [1, 1]। [[10],[11]] → শুরুর frontier-ই উত্তর [10, 11]। single list [[5]] → একটাই value [5, 5]। range একটা নির্দিষ্ট জোড়া, তাই সরাসরি list-সমতা assert। সব pass-এর পরে print হয়: সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n log k) — মোট n-টা element (সব list মিলে), প্রতিটা বড়জোর একবার push/pop হয় (প্রতিটা O(log k), কারণ heap-এ সর্বদা ≤ k entry)। heapify O(k)। তাই dominant term O(n log k)।

অতিরিক্ত জায়গা¶

O(k) — heap-এ একসাথে ঠিক k-টা entry (প্রতিটা list থেকে একটা)। আউটপুট ছাড়া বাড়তি memory heap-সমান, input-এর মোট আকারের উপর নির্ভর করে না।

যে ভুলগুলো এড়াতে হবে¶

current_max track না করা, প্রতিবার heap-এর সব ঘেঁটে max বের করা — এতে step-প্রতি O(k) যোগ হয়, অযথা ধীর।
কোন list থেকে value এলো (list_idx) tuple-এ না রাখা — তখন পরের element কোথা থেকে push করবে জানবে না।
list শেষ হলে break না দেওয়া — খালি index access করে IndexError, বা ভুলভাবে অসম্পূর্ণ window গোনা।
tie-breaking ভুল করা — "strictly smaller width হলে তবেই update" রাখলে প্রথম (সবচেয়ে ছোট a-ওয়ালা) best আপনাআপনি ধরে থাকে।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি 08-এর patterns.md-র Pattern 4 (K-way merge — প্রতিটা sorted source-এর frontier একটা min-heap-এ, বারবার ছোটটা টানো) — যেমন 012 Kth Smallest in Sorted Matrix আর 017 Merge k Sorted Lists। তার সাথে 02-arrays-and-strings-এর sliding-window "একটা valid window সঙ্কুচিত করো" idea মিশেছে।

পরের অনুশীলন¶

Merge k Sorted Lists — https://leetcode.com/problems/merge-k-sorted-lists/ (এই tracker-এর #17; বিশুদ্ধ k-way merge, window ছাড়া)
Kth Smallest Element in a Sorted Matrix — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/ (#12; k-way merge দিয়ে kth element)
Sliding Window Median — https://leetcode.com/problems/sliding-window-median/ (#21; window + heap, ভিন্ন twist)

কৌশলটি মনে রাখুন¶

K-way merge + coverage window: প্রতিটা sorted source-এর frontier একটা min-heap-এ রাখো, আর একটা running max ধরে রাখো; min-কে বারবার এগিয়ে দিয়ে [min, max] window সঙ্কুচিত করো, কোনো source শেষ হলে থামো। "প্রতিটা group থেকে অন্তত একটা cover করো, যত সরু window সম্ভব" — এই গন্ধ পেলেই এই pattern।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: smallest range = k-way merge-এর frontier min-heap + একটা current_max। প্রতি step-এ min pop করো, [min, current_max] best-এর সাথে তুলনা করো, সেই list-এর পরের element push করো (max update সহ); কোনো list ফুরোলে থামো। মনে রেখো — min এগোলেই window সঙ্কুচিত হয়, max কখনো কমে না। heap top সবসময় সেই "সবচেয়ে পিছিয়ে থাকা দৌড়বিদ"।

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