022 — Trapping Rain Water II

Source

• Original source: Classic 2D water-trapping via border-first heap BFS
• Platform: LeetCode — https://leetcode.com/problems/trapping-rain-water-ii/
• Topic: heap / priority queue
• Difficulty: Hard
• Pattern: Min-heap + BFS inward from the border (process lowest wall first)
• Basic idea inherited from: 09-graphs BFS + 08 min-heap — সবচেয়ে নিচু সীমানা থেকে ভেতরে এগোনো

1. Problem in simple words

একটা 2D grid দেওয়া, প্রতিটা cell-এ একটা উচ্চতা (heightMap[r][c])। বৃষ্টি হলে cell-গুলোর ওপর কত একক জল জমতে পারে, মোট সেটা বের করো। জল কেবল ততটুকুই জমে যতটুকু চারপাশের দেয়াল ধরে রাখতে পারে; grid-এর বাইরের প্রান্ত দিয়ে জল গড়িয়ে পড়ে যায়। সব cell-এর জমা জলের যোগফল return করো।

[[1,4,3,1,3,2],
 [3,2,1,3,2,4],
 [2,3,3,2,3,1]]   ->  4 একক জল জমে

2. Which basic idea does this inherit from?

ভিত দুটো জিনিসের মিশেল: 09-graphs-এর BFS (grid-কে graph ধরে প্রতিবেশী cell-এ ছড়ানো) আর 08-এর min-heap (negate লাগে না — এখানে আমরা সবচেয়ে নিচু দেয়াল আগে চাই)। 1D Trapping Rain Water-এ দুই pointer দিয়ে "ছোট দেয়ালের দিকটা" সামলাতে; 2D-তে "ছোট দেয়াল" মানে heap-এর top, আর scan হয় সব দিকে BFS-এর মতো।

3. What is the hidden math or logic?

লুকানো logic 1D-র সেই নিয়ম, এক মাত্রা ওপরে তোলা: যেকোনো cell-এ জলের স্তর = তাকে ঘিরে থাকা পথগুলোর মধ্যে সর্বনিম্ন সর্বোচ্চ দেয়াল (min over all escape paths of the path's max wall)। এই "জল ধরে রাখা সবচেয়ে দুর্বল সীমানা" বের করতে সবচেয়ে নিচু border থেকে শুরু করে ভেতরে এগোলেই হয়: কোনো ভেতরের cell-এ পৌঁছানোর সময় তার প্রতিবেশী যত উঁচু border-level পেরিয়ে এসেছ, সেটার নিচে হলে জল জমে = পার্থক্য; সমান বা উঁচু হলে সেই নতুন উচ্চতাই দেয়াল হয়ে যায়।

4. Which data structure is needed?

একটা min-heap (priority queue), entry (height, row, col) — যাতে সবসময় সবচেয়ে নিচু পরিদর্শিত-সীমানা cell আগে বের করা যায়। সাথে একটা visited 2D boolean grid — কোন cell ইতিমধ্যে heap-এ ঢুকেছে/process হয়েছে তা মনে রাখতে (BFS-এর মতো)।

5. Why this data structure fits

জল আটকানোর বাধা সবসময় সবচেয়ে নিচু দেয়াল থেকে ভাঙে। min-heap ঠিক সেই "এখন সবচেয়ে নিচু সীমানা কে?" প্রশ্নের উত্তর top-এ O(1)-এ দেয়, push/pop O(log(m·n))। তাই আমরা সবচেয়ে দুর্বল border আগে process করি, ভেতরে এগোই, আর জলের স্তর সঠিক ক্রমে নির্ধারণ হয় — কোনো cell দুবার ভাবতে হয় না।

6. Real-life analogy

ভাবো একটা এবড়োখেবড়ো পাহাড়ি অববাহিকা (basin), চারপাশে পাঁচিল। বৃষ্টির জল ততক্ষণই জমবে যতক্ষণ সবচেয়ে নিচু পাঁচিলের ফাঁক দিয়ে গড়িয়ে না পড়ে। তাই জল কতটা জমবে বুঝতে চারপাশের পাঁচিলের সবচেয়ে নিচু অংশ থেকে শুরু করো, একটু একটু করে ভেতরে এগোও; ভেতরের কোনো গর্ত যদি বাইরের ওই নিচু প্রান্তের চেয়েও নিচু হয়, ঠিক ততটুকু জল ধরে রাখবে। "এখনকার সবচেয়ে নিচু পাঁচিল চট করে দাও" — সেই যন্ত্রই min-heap।

7. Visual explanation

ছোট 3×6 grid, border সব heap-এ ঢুকিয়ে সবচেয়ে নিচু থেকে এগোই:

heightMap:
 1 4 3 1 3 2
 3 2 1 3 2 4
 2 3 3 2 3 1

ধাপ: সব border cell heap-এ (visited চিহ্নিত)। min-heap top = সবচেয়ে নিচু border।
   ভেতরের cell (1,1)=2, (1,2)=1, (1,3)=3, (1,4)=2 process হবে প্রতিবেশী
   border-level-এর সাপেক্ষে।

   cell (1,2) উচ্চতা 1, তার চারপাশ থেকে আসা সর্বনিম্ন-সর্বোচ্চ border ≈ 3
      -> জল = 3 - 1 = 2
   cell (1,1) উচ্চতা 2, কার্যকর দেয়াল 3 -> জল = 1
   cell (1,4) উচ্চতা 2, কার্যকর দেয়াল 3 -> জল = 1
   (1,3)=3 যথেষ্ট উঁচু -> জল 0

মোট জল = 2 + 1 + 1 = 4

8. Example input and output

Input : [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]   -> Output: 4
Input : [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]  -> Output: 10
Input : [[1,2,3],[4,5,6]]                              -> Output: 0   (কোনো গর্ত নেই)
Input : [[5]]                                          -> Output: 0   (একটাই cell)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা cell-এর জন্য আলাদা করে বের করো তার চারপাশের সব দিকে পালানোর পথের সর্বোচ্চ দেয়ালের সর্বনিম্ন — অর্থাৎ প্রতিটা cell থেকে সব দিকে scan/DFS চালিয়ে দেখো কত উঁচু দেয়াল পেরোতে হয় বাইরে যেতে।

প্রতিটা cell -> চার দিকে পথ খুঁজে সবচেয়ে নিচু "পালানোর দেয়াল" বের করো
   cell-প্রতি পুরো grid ঘোরা -> ভয়ানক খরচ

10. Why brute force is slow

প্রতিটা cell থেকে আলাদা করে সব escape path দেখা মানে cell-প্রতি O(m·n) কাজ, মোট প্রায় O((m·n)²) বা তারও বেশি — বড় grid-এ অসম্ভব। অথচ পুরো grid-এর জলের স্তর একসাথে, সবচেয়ে নিচু border থেকে একবার ভেতরে এগিয়েই নির্ধারণ করা যায়; প্রতিটা cell আলাদা করে দেখার দরকার নেই।

11. Key observation

মূল observation: কোনো ভেতরের cell-এ জল কতটা জমবে তা ঠিক করে দেয় তার চারপাশের সবচেয়ে নিচু কার্যকর দেয়াল। আর সেই দেয়ালগুলো বাইরে থেকে ভেতরে, সবচেয়ে নিচু border আগে — এই ক্রমে process করলে, যখনই কোনো cell-এ পৌঁছাই, তার "ধরে রাখা স্তর" তার প্রবেশ-পথের সর্বোচ্চ border-level দিয়েই নির্ধারিত। তাই প্রতিটা cell ঠিক একবার দেখলেই চলে।

12. Optimized intuition

সব border cell (height, r, c) হিসেবে min-heap-এ ঢালো, border-গুলো visited চিহ্নিত করো। Loop: top (এখনকার সবচেয়ে নিচু দেয়াল) pop করো; তার প্রতিটা অ-visited প্রতিবেশীর জন্য — যদি প্রতিবেশীর উচ্চতা এই দেয়ালের চেয়ে নিচু হয়, পার্থক্যটুকু জল যোগ করো; প্রতিবেশীকে heap-এ ঢালো তার নিজের আর এই দেয়ালের মধ্যে যেটা বড় সেই উচ্চতায় (কারণ এখন ওটাই কার্যকর দেয়াল)। visited মার্ক করো। heap খালি হলে থামো। মোট O(m·n·log(m·n))।

13. Thinking tweak

মোচড়: "জল ভরা" না ভেবে ভাবো "সবচেয়ে নিচু পাঁচিল থেকে শুরু করে একটা BFS, যেখানে priority = উচ্চতা; ভেতরে এগোনোর সময় কার্যকর জল-স্তর কেবল ওঠে, নামে না।" 1D Trapping Rain Water-এর "ছোট দিক আগে সামলাও" নিয়মটাই এখানে min-heap রূপে। "grid + জল/তরল/সীমানা থেকে ভেতরে ছড়ানো" শুনলেই heap-driven BFS মনে করবে।

14. Step-by-step dry run

Input [[1,2,3],[4,5,6]] (2×3, কোনো ভেতরের গর্ত নেই):

1. border = সব cell (2×3-এ ভেতরের cell নেই, সব প্রান্তে): heap-এ (1,0,0),(2,0,1),(3,0,2),(4,1,0),(5,1,1),(6,1,2); সব visited
2. pop (1,0,0): প্রতিবেশী (0,1) ও (1,0) — দুটোই visited → কিছু করার নেই
3. pop (2,0,1): প্রতিবেশী সব visited → কিছু না
4. একইভাবে বাকি cell pop হয়, কোনো অ-visited প্রতিবেশী নেই → জল যোগ হয় না
5. heap খালি → return 0

(যেহেতু সব cell border, কোনো cell আটকে নেই — জল 0, ঠিক।)

15. Python solution

import heapq

def trap_rain_water(height_map):
    if not height_map or not height_map[0]:
        return 0
    rows, cols = len(height_map), len(height_map[0])
    if rows < 3 or cols < 3:
        return 0                       # ভেতরের cell না থাকলে জল জমার জায়গাই নেই

    visited = [[False] * cols for _ in range(rows)]
    heap = []

    # সব border cell heap-এ ঢালো, visited চিহ্নিত করো
    for r in range(rows):
        for c in range(cols):
            if r in (0, rows - 1) or c in (0, cols - 1):
                heapq.heappush(heap, (height_map[r][c], r, c))
                visited[r][c] = True

    water = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while heap:
        wall, r, c = heapq.heappop(heap)    # এখনকার সবচেয়ে নিচু কার্যকর দেয়াল
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                visited[nr][nc] = True
                # প্রতিবেশী দেয়ালের নিচে হলে পার্থক্যটুকু জল জমে
                water += max(0, wall - height_map[nr][nc])
                # নতুন কার্যকর দেয়াল = প্রতিবেশী নিজে আর বর্তমান দেয়ালের বড়টা
                heapq.heappush(heap, (max(wall, height_map[nr][nc]), nr, nc))
    return water

# ---- tests ----
assert trap_rain_water([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]) == 4
assert trap_rain_water(
    [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]) == 10
assert trap_rain_water([[1,2,3],[4,5,6]]) == 0       # কোনো গর্ত নেই
assert trap_rain_water([[5]]) == 0                    # একটাই cell
assert trap_rain_water([[12,13,1,12],[13,4,13,12],[13,8,10,12],
                        [12,13,12,12],[13,13,13,13]]) == 14
print("সব test pass!")

16. Line-by-line code explanation

• if rows < 3 or cols < 3: return 0 — অন্তত 3×3 না হলে কোনো ভেতরের cell নেই, জল জমার জায়গাই নেই।
• visited = [[False]*cols ...] — কোন cell heap-এ ঢুকেছে/process হয়েছে তা মনে রাখার BFS-grid।
• border-ঢালার দুই loop — সব প্রান্তের cell (height, r, c) হিসেবে min-heap-এ; প্রান্ত দিয়ে জল পালায়, তাই এরাই শুরুর দেয়াল।
• wall, r, c = heapq.heappop(heap) — এই মুহূর্তের সবচেয়ে নিচু কার্যকর দেয়াল আর তার অবস্থান।
• if ... not visited[nr][nc]: — প্রতিটা অ-পরিদর্শিত প্রতিবেশীর দিকে এগোই; visited মার্ক করি যাতে দুবার না হয়।
• water += max(0, wall - height_map[nr][nc]) — প্রতিবেশী দেয়ালের নিচে হলে ঠিক পার্থক্যটুকু জল; নাহলে 0।
• heapq.heappush(heap, (max(wall, height_map[nr][nc]), nr, nc)) — এই cell-এর কার্যকর দেয়াল = নিজে আর আসা-দেয়ালের বড়টা; সেই উচ্চতায় heap-এ ঢালি।

17. Output walkthrough

প্রথম example-এ সবচেয়ে নিচু border থেকে ভেতরে এগিয়ে cell (1,2)=1-এ 2, আর দুটো প্রতিবেশী গর্তে 1+1 জল জমে → মোট 4 — assert pass। দ্বিতীয়টা একটা bowl: চারপাশ 3, কেন্দ্র 1, মাঝের ring 2 — মোট 10। [[1,2,3],[4,5,6]] section 14 মেনে সব cell border, জল 0। single [[5]] → 3×3-এর ছোট, 0। শেষ 5×4 grid-এ মিশ্র উচ্চতায় 14 জল। জল একটা নির্দিষ্ট integer, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: সব test pass!।

18. Time complexity

O(m·n·log(m·n)) — প্রতিটা cell ঠিক একবার heap-এ ঢোকে আর একবার বের হয় (মোট m·n cell), প্রতিটা push/pop O(log(m·n))। visited check O(1)। তাই dominant term এই log-যুক্ত পদ।

19. Space complexity

O(m·n) — visited grid O(m·n), আর heap-এ সবচেয়ে খারাপ ক্ষেত্রে O(m·n) entry (যদিও সাধারণত কম)। আউটপুট শুধু একটা সংখ্যা।

20. Common mistakes

• max-heap ব্যবহার করা — এখানে সবচেয়ে নিচু দেয়াল আগে চাই, তাই min-heap; উল্টো করলে জলের স্তর ভুল।
• প্রতিবেশী push করার সময় max(wall, neighbor) না নিয়ে শুধু প্রতিবেশীর উচ্চতা push করা — তখন কার্যকর দেয়াল হারিয়ে যায়, জল কম গোনা হয়।
• pop-এর সময় visited মার্ক করা (push-এর বদলে) — তখন একই cell একাধিকবার heap-এ ঢুকে ভুল হিসাব।
• 3×3-এর ছোট grid গার্ড না দেওয়া — ভেতরের cell নেই, তবু কোড চালালে শুধু অপচয়; পরিষ্কার করে 0 ফেরানো ভালো।

21. Which basic problem this inherits from

ভিত্তি 09-graphs-এর BFS (grid-কে graph ধরে প্রতিবেশীতে ছড়ানো, visited দিয়ে) আর 08-এর concept.md-র min-heap basics। আসল মোচড়টা 1D "Trapping Rain Water"-এর — যেখানে দুই pointer ছোট দিকটা আগে সামলায়; এখানে "ছোট দিক" মানে min-heap-এর top, আর ছড়ানো হয় চার দিকে।

22. Similar harder problems

• Smallest Range Covering Elements from K Lists — https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/ (এই tracker-এর #20; min-heap frontier এগিয়ে নেওয়া)
• Sliding Window Median — https://leetcode.com/problems/sliding-window-median/ (#21; heap + আরেকটা structure)
• Swim in Rising Water — https://leetcode.com/problems/swim-in-rising-water/ (একই border-first min-heap BFS ভাবনা, grid-এ)

23. Pattern learned

Min-heap + border-first BFS: সবচেয়ে নিচু সীমানা থেকে শুরু করে min-heap দিয়ে ভেতরে এগোও; প্রতিটা নতুন cell-এ কার্যকর দেয়াল = পথের সর্বোচ্চ, আর তার নিচে হলে জল জমে। "grid + তরল/সীমানা থেকে ভেতরে ছড়ানো, সবচেয়ে দুর্বল প্রান্ত আগে" — এই গন্ধ পেলেই এই pattern; এটাই পরে Dijkstra-ধাঁচের heap-BFS-এর আত্মীয়।

24. Final summary

ভবিষ্যতের আমাকে: Trapping Rain Water II = min-heap-driven BFS, border থেকে ভেতরে। সব প্রান্ত heap-এ ঢালো, সবচেয়ে নিচু দেয়াল pop করো, প্রতিবেশীতে জল = max(0, দেয়াল − উচ্চতা) যোগ করো, প্রতিবেশীকে max(দেয়াল, তার উচ্চতা) উচ্চতায় push করো, visited মার্ক করো। মনে রেখো — min-heap (max নয়), আর কার্যকর দেয়াল কখনো নামে না। এটা 1D water-trapping-এরই 2D, heap-এর পোশাকে — আর 09-graphs-এ Dijkstra ঠিক এই heap-BFS।

---

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