Skip to content

012 — Kth Smallest Element in a Sorted Matrix

Source

1. Problem in simple words

একটা n x n matrix দেওয়া, যেখানে প্রতিটা row বাম-থেকে-ডান sorted আর প্রতিটা column উপর-থেকে-নিচ sorted। তোমাকে পুরো matrix-এর সব সংখ্যার মধ্যে k-তম সবচেয়ে ছোট সংখ্যাটা বের করতে হবে। মনে রেখো এটা sorted order-এ k-তম, distinct নয় — duplicate থাকলে তারাও আলাদা করে গোনা হয়।

matrix = [[1, 5, 9],
          [10, 11, 13],
          [12, 13, 15]],  k = 8   ->  13

2. Which basic idea does this inherit from?

ভিত 08-এর k-way merge। প্রতিটা row নিজে একটা sorted list; তুমি যদি সব row একসাথে merge করতে থাকো, sorted order-এ একটা একটা করে element বের হবে — k-তম বার যেটা বেরোয় সেটাই উত্তর। পুরো merge শেষ করার দরকার নেই, প্রথম k-টা element হলেই থামবে।

3. What is the hidden math or logic?

লুকানো logic: overall sorted sequence-এর পরের element সবসময় কোনো না কোনো row-cursor যেদিকে দেখাচ্ছে তার মধ্যে সবচেয়ে ছোট। Row sorted বলে একটা row থেকে শুধু তার বর্তমান cursor-value-ই candidate; সব row-এর candidate-দের মধ্যে min-টাই next। এই min বারবার পেতে heap, আর প্রতিবার সেই row-এর cursor এক ঘর ডানে সরাও।

4. Which data structure is needed?

একটা min-heap of triples (value, row, col) — প্রতিটা active row-এর current cursor value ধরে রাখে। সাথে matrix-টা তো আছেই, cursor advance করতে।

5. Why this data structure fits

heap-এ কখনো n-টার (row সংখ্যা) বেশি entry থাকে না — প্রতি row-এর একটা cursor। smallest-টা peek করা O(1)-এর মতো (top), pop/push O(log n)। তাই k-তম element পেতে O(k log n) — পুরো n² element sort করার (O(n² log n)) দরকার নেই।

6. Real-life analogy

ভাবো n-টা আলাদা queue, প্রতিটা ভেতরে আগে-থেকে ছোট-থেকে-বড় সাজানো লোকজন। একজন officer প্রতিবার সব queue-এর সামনের লোকদের দেখে সবচেয়ে ছোট number-ওয়ালাকে ডাকেন; ওই queue তখন এক ধাপ এগোয়। k-তম বার যাকে ডাকা হলো, সে-ই উত্তর। officer-এর চোখে শুধু n-টা front — পুরো ভিড় না; সেই চোখটাই heap।

7. Visual explanation

matrix = [[1,5,9],[10,11,13],[12,13,15]], k=8 — heap-এ প্রতি row-এর প্রথম element দিয়ে শুরু:

heap (value,row,col):  (1,0,0) (10,1,0) (12,2,0)

pop 1  (row0)  -> push (5,0,1)     count 1
pop 5  (row0)  -> push (9,0,2)     count 2
pop 9  (row0)  -> row শেষ          count 3
pop 10 (row1)  -> push (11,1,1)    count 4
pop 11 (row1)  -> push (13,1,2)    count 5
pop 12 (row2)  -> push (13,2,1)    count 6
pop 13 (row1)  -> push (15,1,? শেষ) count 7
pop 13 (row2)  -> ...              count 8  -> উত্তর 13

8. Example input and output

Input : matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8  -> Output: 13
Input : matrix = [[-5]], k = 1                            -> Output: -5
Input : matrix = [[1,2],[1,3]], k = 2                     -> Output: 1   (duplicate গোনা হয়)
Input : matrix = [[1,2],[1,3]], k = 4                     -> Output: 3

9. Brute force thinking

প্রথম সরল চিন্তা: পুরো matrix-এর সব সংখ্যা একটা flat list-এ ঢালো, list-টা sort করো, তারপর (k-1)-তম index নাও।

সব নাও -> [1,5,9,10,11,12,13,13,15] -> sort -> index 7 (k=8) -> 13

10. Why brute force is slow

সব n² element collect করে sort করা মানে O(n² log n) time আর O(n²) extra space। অথচ আমাদের row/column sortedness ব্যবহারই করা হলো না, আর আমাদের পুরো order লাগেও না — শুধু প্রথম k-টা। তাই পুরো matrix sort করা অপচয়, বিশেষত k ছোট হলে।

11. Key observation

মূল observation: পুরো sequence sort না করেও, k-way merge দিয়ে শুধু প্রথম k-টা element বের করা যায়। প্রতিটা row sorted বলে heap-এ একসাথে n-টার বেশি candidate লাগে না। আরও smart approach (binary search on value) O(n log(max−min))-এও পারে, কিন্তু heap version-টা সবচেয়ে সরাসরি k-way merge।

12. Optimized intuition

প্রতিটা row-এর প্রথম element (value, row, 0) দিয়ে একটা min-heap বানাও। k বার এই কাজ করো: top pop করো; যদি সেই row-এ আরও element থাকে, পরের (value, row, col+1) push করো। k-তম pop-এর value-ই উত্তর। n-row-এর জায়গায় শুধু প্রথম row নিয়ে শুরু করলেও চলে (column sorted বলে), তবে সব row দিয়ে শুরু করা সহজ আর নিরাপদ।

13. Thinking tweak

মোচড়: "2D matrix-এ k-তম" না ভেবে ভাবো "n-টা sorted list (row) merge করছি, k-তম element-এ থামছি।" "sorted rows/columns / k sorted ... / matrix-এ kth smallest" — এই কথাগুলো শুনলেই k-way merge heap-এর আলো জ্বলা উচিত, ঠিক যেমন Merge k Sorted Lists-এ (#17)।

14. Step-by-step dry run

Input matrix = [[1,2],[1,3]], k=4:

  1. heap = {(1,0,0), (1,1,0)} (প্রতি row-এর প্রথম element)
  2. pop (1,0,0) → count 1; row0-এ col1 আছে → push (2,0,1); heap {(1,1,0),(2,0,1)}
  3. pop (1,1,0) → count 2; row1-এ col1 আছে → push (3,1,1); heap {(2,0,1),(3,1,1)}
  4. pop (2,0,1) → count 3; row0 শেষ; heap {(3,1,1)}
  5. pop (3,1,1) → count 4 → k-তম → return 3

15. Python solution

import heapq

def kth_smallest(matrix, k):
    n = len(matrix)
    # প্রতি row-এর প্রথম element: (value, row, col)
    heap = [(matrix[r][0], r, 0) for r in range(n)]
    heapq.heapify(heap)            # top = সব cursor-এর মধ্যে smallest

    val = None
    for _ in range(k):             # k বার merge-step
        val, r, c = heapq.heappop(heap)
        if c + 1 < len(matrix[r]):     # ওই row-এ আরও element আছে?
            heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
    return val                     # k-তম pop করা value

# ---- tests ----
m1 = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
assert kth_smallest(m1, 8) == 13

assert kth_smallest([[-5]], 1) == -5            # একটাই element

m2 = [[1, 2], [1, 3]]
assert kth_smallest(m2, 1) == 1
assert kth_smallest(m2, 2) == 1                 # duplicate গোনা হয়
assert kth_smallest(m2, 3) == 2
assert kth_smallest(m2, 4) == 3

m3 = [[1, 3, 5], [6, 7, 12], [11, 14, 14]]
assert kth_smallest(m3, 6) == 11

print("সব test pass!")

16. Line-by-line code explanation

  • n = len(matrix) — row সংখ্যা (square matrix বলে column সংখ্যাও n, তবে কোডে len(matrix[r]) ধরে নিরাপদ)।
  • heap = [(matrix[r][0], r, 0) ...] — প্রতি row-এর প্রথম element, সাথে row index আর col index।
  • heapq.heapify(heap) — O(n)-এ heap; top = সব cursor-এর smallest value।
  • for _ in range(k): — ঠিক k বার smallest টানব।
  • val, r, c = heappop(heap) — এখনকার smallest cursor value আর তার অবস্থান।
  • if c + 1 < len(matrix[r]): heappush(...) — ওই row-এ পরের element থাকলে cursor advance করে heap-এ ঢালো।
  • return val — loop শেষে val হলো k-তম pop করা value, অর্থাৎ উত্তর।

17. Output walkthrough

kth_smallest([[1,2],[1,3]], 4) section 14-এর dry run মেনে 3 দেয় — assert pass। বড় matrix m1-এ k=8 → 13; single-cell [[-5]] → -5; duplicate-ভরা m2-তে k=1,2 দুটোই 1 (duplicate আলাদা গোনা হয়)। order এখানে fixed (k-তম মানে নির্দিষ্ট), তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: সব test pass!।

18. Time complexity

O(k log n) — n = row সংখ্যা; heap-এ কখনো n-টার বেশি entry না, আর আমরা k বার pop/push করি (প্রতিটা O(log n))। heapify O(n)। সাধারণত k ≤ n² বলে এটা naive O(n² log n)-এর থেকে ভালো, বিশেষত ছোট k-তে।

19. Space complexity

O(n) — heap-এ বড়জোর n-টা cursor entry (প্রতি row একটা)। flat-list-sort approach যেখানে O(n²) লাগত, তার তুলনায় এটা অনেক কম memory।

20. Common mistakes

  • প্রতি row-এর শুধু প্রথম element-ই push না করা / ভুল index দেওয়া — তখন merge ভেঙে যায়।
  • duplicate-কে distinct ভেবে বাদ দেওয়া — kth smallest মানে multiset-এ kth, distinct নয়।
  • column-sorted property-কে row-sorted ভেবে গুলিয়ে ফেলা — এখানে আমরা row ধরে merge করছি, তাই row-cursor-ই advance করতে হবে।
  • k-তম pop-এর আগে থেমে যাওয়া বা একবার বেশি pop করা — ঠিক range(k) লুপ চালাও।

21. Which basic problem this inherits from

ভিত্তি 08-এর patterns.md-র Pattern 2 (K-way merge) — "k-টা cursor-value heap-এ রাখো, smallest pop করো, সেই cursor advance করো"। এটা merge sort-এর two-pointer merge-এরই k-pointer রূপ, যেখানে কোন pointer নড়বে সেটা heap ঠিক করে।

22. Similar harder problems

23. Pattern learned

K-way merge: k-টা sorted source, প্রতিটায় একটা cursor; heap সবসময় "এখন কোন cursor-এ smallest" বলে দেয়। smallest নাও, সেই cursor এক ধাপ এগোও, পরের value push করো। sorted source জুড়ে কিছু খোঁজা মানেই এই pattern-এর কথা ভাবা।

24. Final summary

ভবিষ্যতের আমাকে: "sorted rows/columns matrix-এ kth smallest" = k-way merge, প্রতি row-এ cursor, min-heap-এ (value, row, col), k বার pop। Binary-search-on-value আরও fast হলেও, এই heap version সবচেয়ে সহজে মনে থাকে আর Merge k Sorted Lists-এর সরাসরি প্রস্তুতি।

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