021 — Trapping Rain Water¶

Source¶

Original source: Classic monotonic-stack variant exercise
Platform: LeetCode — https://leetcode.com/problems/trapping-rain-water/
Topic: stack (monotonic variant)
Difficulty: Hard
Pattern: monotonic stack variant (bounded by neighbors)
Basic idea inherited from: Problem 20-এর geometry + "প্রতিবেশী দিয়ে আবদ্ধ" idea — পানি জমে দুই পাশের দেয়ালের নিচু-টার সমান উচ্চতায়

1. Problem in simple words¶

তোমাকে কিছু বারের উচ্চতার একটা array height দেওয়া আছে (প্রতিটার প্রস্থ 1), যেটা একটা উঁচু-নিচু ভূমিরূপের মতো। বৃষ্টি হলে বারগুলোর মাঝের গর্তে কতটা পানি আটকে থাকবে, তার মোট পরিমাণ বের করো।

height = [0,1,0,2,1,0,1,3,2,1,2,1]-এর জন্য আটকে থাকা পানি 6:

              #
      #~~~~~~~# #
  #~~~# #~~# # # #
  0 1 0 2 1 0 1 3 2 1 2 1
~ = আটকে থাকা পানি; মোট 6 ইউনিট

2. Which basic idea does this inherit from?¶

এটা Problem 20 (largest rectangle)-এর geometry-চিন্তার জ্ঞাতি, কিন্তু উল্টো প্রশ্ন নিয়ে। সেখানে বারগুলো নিজেই আয়তক্ষেত্র ছিল; এখানে আমরা বারের ফাঁকা জায়গায় জমা পানির হিসাব করি। মূল ভাবনা — bounded by neighbors: যেকোনো জায়গায় পানির উচ্চতা ঠিক হয় বাঁ আর ডান দিকের সবচেয়ে উঁচু দেয়ালের মধ্যে যেটা ছোট, তার সমান। monotonic stack এই "বাঁ দেয়াল – গর্ত – ডান দেয়াল" তিনটে এক pass-এ মিলিয়ে দেয়।

3. What is the hidden math or logic?¶

লুকানো logic: একটা নিচু bar-এর উপরে পানি জমবে ঠিক ততটুকু, যতটা তাকে বাঁয়ে আর ডানে ঘিরে রাখা দুই দেয়ালের নিচু-টা অনুমতি দেয়, বিয়োগ ওই bar-এর নিজের উচ্চতা।

stack দিয়ে আমরা এই হিসাব স্তরে স্তরে (layer by layer) করি। stack-এ উচ্চতা decreasing রাখি। যখন একটা নতুন bar আসে যেটা top-এর চেয়ে উঁচু, তখন top (bottom) হলো গর্তের তলা; pop করি, এর নিচের bar (left) হলো বাঁ দেয়াল, আর নতুন bar (right সীমা) হলো ডান দেয়াল। ওই layer-এ পানি = (min(left_height, right_height) - bottom_height) * width।

4. Which data structure is needed?¶

একটা monotonic stack (Python-এ list) যেখানে index রাখি, উচ্চতা decreasing। index লাগে দুটো কারণে: প্রস্থ (width) বের করতে, আর বাঁ-দেয়ালের উচ্চতা height[left] দেখতে। আলাদা কিছু লাগে না।

5. Why this data structure fits¶

পানির হিসাবের জন্য প্রতিটা গর্তের দরকার তার বাঁ দিকের নিকটতম উঁচু দেয়াল আর ডান দিকের নিকটতম উঁচু দেয়াল। decreasing stack ঠিক এই "এখনো ডান দেয়াল খুঁজছে" এমন bar-দের ধরে রাখে; একটা উঁচু bar এলে সে stack-এর উপরের নিচু bar-দের ডান দেয়াল হয়ে যায়, আর তাদের নিচের bar বাঁ দেয়াল। প্রতিটা bar একবার push একবার pop → O(n)।

6. Real-life analogy¶

ভাবো তুমি বাঁ থেকে ডানে হাঁটছ আর সিঁড়ির মতো নামতে-থাকা ধাপ দেখছ — প্রতিটা ধাপ stack-এ জমছে (decreasing)। হঠাৎ সামনে একটা উঁচু দেয়াল পেলে বুঝলে, পেছনের নামতে-থাকা ধাপগুলোর আর এই দেয়ালের মাঝে একটা "বালতি" তৈরি হয়েছে। তুমি তখন স্তরে স্তরে পানি ঢালো: সবচেয়ে নিচের ধাপ থেকে শুরু করে, যতক্ষণ না বাঁ পাশের দেয়াল বা ডান পাশের দেয়াল বাধা দেয়। প্রতিটা স্তরের পানি মেপে যোগ করতে থাকো।

7. Visual explanation¶

height = [0,1,0,2,1,0,1,3,...]-এর শুরুর অংশে index-এর decreasing stack (top ডানে) আর পানির layer:

i  h  action                                                   water যোগ
0  0  push                                                     —
1  1  h[0]=0<1 pop bottom0; stack খালি -> বাঁ দেয়াল নেই, break  0
      push 1
2  0  h[1]=1<0? না; push 2
3  2  h[2]=0<2 pop bottom2; left=1, W=3-1-1=1,
         bounded=min(h[1]=1, 2)-h[2]=0 = 1 -> +1*1            +1
      h[1]=1<2 pop bottom1; stack খালি -> break               0
      push 3
...   (এভাবে চলতে চলতে index 7-এ 3 আসার সময় বড় layer যোগ হয়)
মোট আটকে থাকা পানি = 6

bottom = গর্তের তলা, left = বাঁ দেয়াল index, ডান দেয়াল = current i।

8. Example input and output¶

Input : [0,1,0,2,1,0,1,3,2,1,2,1] -> 6
Input : [4,2,0,3,2,5]             -> 9
Input : [2,0,2]                   -> 2   (মাঝের গর্তে min(2,2)-0 = 2)

Edge case 1 (শুধু বাড়ছে) : [1,2,3] -> 0   (পানি ধরে রাখার দেয়াল নেই)
Edge case 2 (শুধু কমছে)  : [3,2,1] -> 0
Edge case 3 (খালি)       : []      -> 0

9. Brute force thinking¶

সরল চিন্তা: প্রতিটা index i-র জন্য তার বাঁ দিকের সর্বোচ্চ উচ্চতা আর ডান দিকের সর্বোচ্চ উচ্চতা বের করি; ওই ঘরে পানি = min(left_max, right_max) - height[i] (ঋণাত্মক হলে 0)।

for i in range(n):
    left_max  = max(height[0 .. i])
    right_max = max(height[i .. n-1])
    water += max(0, min(left_max, right_max) - height[i])

10. Why brute force is slow¶

প্রতিটা i-র জন্য বাঁ ও ডানে আবার scan করলে O(n^2)। (precomputed left/right-max array দিয়ে O(n) করা যায়, কিন্তু সেটা অন্য কৌশল।) এখানে আমরা stack দিয়ে এক pass-এ, প্রতিটা bar-কে একবার ছুঁয়ে O(n)-তে পুরো হিসাব সারি — কোনো বাড়তি দুই array না বানিয়েও।

11. Key observation¶

মূল observation: পানি জমে সবসময় একটা "নিচু জায়গা যাকে দুই পাশে উঁচু দেয়াল ঘিরে রেখেছে" — সেখানে। আর "ডান দিকের নিকটতম উঁচু দেয়াল কখন এল" সেটা ধরা monotonic stack-এর কাজ: যেই একটা উঁচু bar আসে, সে stack-এর উপরের নিচু bar-দের ডান দেয়াল হয়ে যায়, তখনই সেই layer-এর পানি হিসাব করা যায়।

12. Optimized intuition¶

index-এর decreasing stack রাখো। প্রতিটা (i, h)-তে: যতক্ষণ stack খালি নয় আর top-এর উচ্চতা h-এর চেয়ে ছোট, ততক্ষণ — bottom = stack.pop() (গর্তের তলা)। এরপর stack খালি হলে বাঁ দিকে কোনো দেয়াল নেই, break। নাহলে left = stack[-1], প্রস্থ width = i - left - 1, আবদ্ধ উচ্চতা bounded = min(height[left], h) - height[bottom], পানি water += width * bounded। শেষে i push করো।

13. Thinking tweak¶

মোচড়: পানিকে "প্রতি কলামে কতটা" ভাবার বদলে ভাবো "প্রতিটা অনুভূমিক স্তর কখন বন্ধ হয়"। একটা উঁচু bar এসে পেছনের গর্তের উপরে একটা একটা স্তর ছাদ দিয়ে দেয় — তখনই সেই স্তরের পানি (প্রস্থ × আবদ্ধ-উচ্চতা) যোগ হয়ে যায়। stack ঠিক এই "কোন গর্ত এখনো ডান দেয়ালের অপেক্ষায়" তা মনে রাখে।

14. Step-by-step dry run¶

Input [2, 0, 2]:

i=0 (2): push → [0]
i=1 (0): height[0]=2 < 0? না; push 1 → [0,1]
i=2 (2): height[1]=0 < 2 → bottom=1 pop; stack [0] খালি নয়, left=0, width=2-0-1=1, bounded=min(height[0]=2, 2)-height[1]=0 = 2, water += 1*2 = 2; এরপর height[0]=2 < 2? না; push 2 → [0,2]
return water = 2

15. Python solution¶

def trap(height):
    stack = []                       # index রাখে; উচ্চতা decreasing
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()                 # গর্তের তলা
            if not stack:
                break                            # বাঁয়ে দেয়াল নেই -> পানি ধরে না
            left = stack[-1]                      # বাঁ দেয়াল
            width = i - left - 1                  # দুই দেয়ালের মাঝের প্রস্থ
            bounded = min(height[left], h) - height[bottom]
            water += width * bounded             # এই layer-এর পানি
        stack.append(i)
    return water

# ---- tests ----
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9
assert trap([2, 0, 2]) == 2          # একটা গর্ত
assert trap([1, 2, 3]) == 0          # শুধু বাড়ছে -> পানি ধরে না
assert trap([3, 2, 1]) == 0          # শুধু কমছে
assert trap([]) == 0                  # খালি
print("সব test pass!")

16. Line-by-line code explanation¶

stack = [] — index জমবে; উচ্চতা decreasing রাখা invariant।
while stack and height[stack[-1]] < h: — top-এর bar current-এর চেয়ে নিচু মানে current bar তার ডান দেয়াল হতে পারে, একটা layer বন্ধ হতে চলেছে।
bottom = stack.pop() — pop-করা bar-ই এই layer-এর তলা।
if not stack: break — pop-এর পর stack খালি মানে বাঁ দিকে কোনো দেয়াল নেই; দেয়াল ছাড়া পানি ধরে না, তাই এই i-র loop থামাও।
left = stack[-1] / width = i - left - 1 — বাঁ দেয়াল আর তার-current-এর মাঝের ফাঁকা প্রস্থ।
bounded = min(height[left], h) - height[bottom] — দুই দেয়ালের নিচু-টা পানির ছাদ ঠিক করে; তলা বাদ দিলে এই layer-এর উচ্চতা।
water += width * bounded — এই layer-এর আয়তন যোগ।
stack.append(i) — current bar এখন stack-এ, ভবিষ্যতের দেয়াল/তলা হিসেবে।

17. Output walkthrough¶

trap([0,1,0,2,1,0,1,3,2,1,2,1]) → বিভিন্ন layer যোগ হয়ে মোট 6; বিশেষ করে index 7-এর 3 এসে পেছনের কয়েকটা bar-এর উপর বড় layer বন্ধ করে। trap([1,2,3]) → প্রতিবার pop-এর পরই stack খালি হয়ে break, কোনো পানি যোগ হয় না, ফল 0। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity¶

O(n) — প্রতিটা index ঠিক একবার push হয় আর বড়জোর একবার pop হয়; nested while সত্ত্বেও মোট pop সংখ্যা n-এর বেশি নয়।

19. Space complexity¶

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (কঠোর কমতে-থাকা উচ্চতা, যেমন [5,4,3,2,1]) কোনো pop হয় না, সব index stack-এ জমে।

20. Common mistakes¶

pop-এর পর if not stack: break ভুলে যাওয়া — বাঁ দেয়াল না থাকলেও পানি যোগ করার চেষ্টায় ভুল উত্তর/error।
bounded হিসাবে min(height[left], h) না নিয়ে শুধু একটা দেয়াল ধরা — পানি দুই দেয়ালের নিচু-টা দিয়ে আবদ্ধ, একটা দিয়ে নয়।
প্রস্থ i - left - 1-এর বদলে i - left লেখা — দেয়াল দুটো নিজে পানির অংশ নয়, তাই -1।
< বনাম <= — সমান উচ্চতার ক্ষেত্রে < রাখলে সমান bar আগে stack-এ জমে, পরে ঠিকঠাক layer হিসাব হয়; <= দিলে অকারণে আগেই pop হয়ে বাঁ-দেয়ালের তথ্য নষ্ট হতে পারে।

21. Which basic problem this inherits from¶

ভিত্তি: Problem 20-এর monotonic-stack geometry + "bounded by neighbors" ধারণা; chapter-এর ../patterns.md Pattern 4-এর variant। নতুন অংশ — pop-এর মুহূর্তে তিনটে bar (বাঁ দেয়াল, তলা, ডান দেয়াল) মিলিয়ে layer-wise আয়তন।

22. Similar harder problems¶

Trapping Rain Water II (2D grid, heap-ভিত্তিক) — https://leetcode.com/problems/trapping-rain-water-ii/
Largest Rectangle in Histogram (একই pop-করে-geometry) — https://leetcode.com/problems/largest-rectangle-in-histogram/ (এই tracker-এর #20)
Container With Most Water (two-pointer variant) — https://leetcode.com/problems/container-with-most-water/

23. Pattern learned¶

Monotonic stack, bounded-by-neighbors: "দুই পাশের দেয়ালের মাঝে আটকে থাকা পরিমাণ" দেখলে index-এর decreasing stack রাখো; উঁচু bar এসে নিচু top-কে তলা ধরে pop করায়, বাঁ দেয়াল = নতুন top, ডান দেয়াল = current; (min(দুই দেয়াল) - তলা) * প্রস্থ যোগ করো।

24. Final summary¶

ভবিষ্যতের আমাকে: rain water (stack) = layer-by-layer। decreasing stack-এ index রাখো; উঁচু bar এলে top pop করে তলা ধরো, বাঁ দেয়াল = পরের top (না থাকলে break), পানি = (min(left, right) - bottom) * (i - left - 1)। দুই দেয়ালের min নাও, প্রস্থে -1। "trapped water / bounded by neighbors" দেখলেই এই pattern (বা left/right-max দুই array)।

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