021 — Trapping Rain Water¶

Problem link ও উৎস

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 — পানি জমে দুই পাশের দেয়ালের নিচু-টার সমান উচ্চতায়

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

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

তোমাকে কিছু বারের উচ্চতার একটা 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 ইউনিট

Input ও 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

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

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

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

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

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

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

লুকানো 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।

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

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

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

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

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

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

সরল চিন্তা: প্রতিটা 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])

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

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

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

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

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

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 করো।

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

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

ছবিতে বোঝা¶

height=[0,1,0,2,1,0,1,3,2,1,2,1]। Stack-এ index থাকে; top ডানে। প্রতিটি pop-এর layer নিচে দেখানো।

i / height	pop ও পানির হিসাব	push-এর পরে stack	মোট পানি
0 / 0	pop নেই	`[0]`	0
1 / 1	pop 0: বাঁ দেয়াল নেই	`[1]`	0
2 / 0	pop নেই	`[1, 2]`	0
3 / 2	pop 2: width 1 × layer 1 = 1; pop 1: বাঁ দেয়াল নেই	`[3]`	1
4 / 1	pop নেই	`[3, 4]`	1
5 / 0	pop নেই	`[3, 4, 5]`	1
6 / 1	pop 5: width 1 × layer 1 = 1	`[3, 4, 6]`	2
7 / 3	pop 6: width 2 × layer 0 = 0; pop 4: width 3 × layer 1 = 3; pop 3: বাঁ দেয়াল নেই	`[7]`	5
8 / 2	pop নেই	`[7, 8]`	5
9 / 1	pop নেই	`[7, 8, 9]`	5
10 / 2	pop 9: width 1 × layer 1 = 1	`[7, 8, 10]`	6
11 / 1	pop নেই	`[7, 8, 10, 11]`	6

width=i-left-1; layer=min(height[left],height[i])-height[bottom]। শেষ stack-এর অবশিষ্ট bar-এর জন্য আর ডান দেয়াল নেই; কোনো অতিরিক্ত পানি যোগ হয় না। উত্তর 6।

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

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

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

Python¶

Python

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

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

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-এ, ভবিষ্যতের দেয়াল/তলা হিসেবে।

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

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

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

সময়¶

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

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

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

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

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

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

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

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

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

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/

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

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

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

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