Skip to content

020 — Smallest Range Covering Elements from K Lists

Source

1. Problem in simple words

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]

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

লুকানো 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 শেষ হলে থামো।

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] — frontier min-heap (value, list):

শুরু: frontier = (4,L0) (0,L1) (5,L2)   max = 5
   min=0, max=5 -> range [0,5], width 5    (best এখন [0,5])

0 (L1) pop -> L1-এর পরের 9 push -> frontier (4,L0)(9,L1)(5,L2)  max=9
   min=4, max=9 -> [4,9] width 5

4 (L0) pop -> 10 push -> (10,L0)(9,L1)(5,L2)  max=10
   min=5, max=10 -> [5,10] width 5
...
   শেষমেশ frontier (24,L0)(20,L1)(22,L2)  max=24
   min=20, max=24 -> [20,24] width 4   <- সবচেয়ে ছোট
20 (L1) pop -> L1 শেষ -> থামো

উত্তর: [20, 24]

8. Example input and 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]

9. Brute force thinking

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

প্রতি list থেকে এক একটা পছন্দ -> (4,0,5),(4,0,18),... সব combo
   প্রতিটার max-min -> সবচেয়ে ছোট রাখো

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

প্রতিটা 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)।

13. Thinking tweak

মোচড়: "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 মাথায় আনবে।

14. Step-by-step dry run

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

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

15. Python solution

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!")

16. Line-by-line code explanation

  • 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-এ আনো।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • 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 আপনাআপনি ধরে থাকে।

21. Which basic problem this inherits from

ভিত্তি 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 মিশেছে।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: 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।