021 — Trapping Rain Water¶

Problem link ও উৎস

Original source: Classic two-pointer / prefix-max exercise
Platform: LeetCode — https://leetcode.com/problems/trapping-rain-water/
Topic: array / two pointers
Difficulty: Hard
Pattern: two pointers / prefix max (প্রতিটা ঘরের উপর জমা পানি)
Basic idea inherited from: prefix-max array + two-pointer discard — দুই প্রান্তের boundary বুঝে candidate বাদ দেওয়া

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

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

একটা array height দেওয়া, যেখানে প্রতিটা সংখ্যা একটা দেয়াল/বারের উচ্চতা (প্রস্থ 1)। বৃষ্টির পর এই বারগুলোর মাঝের গর্তে কতটুকু পানি জমে থাকবে, তার মোট পরিমাণ বের করো।

উদাহরণ

height = [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

Edge case 1 (খালি/monotonic): []      -> 0 ;  [1,2,3] -> 0  (কোনো গর্ত নেই)
Edge case 2 (এক গর্ত):         [3,0,2] -> 2

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

ভাবো দুই পাশে দুজন বালতি হাতে দাঁড়িয়ে, মাঝখানে অসমান উঁচু-নিচু দেয়াল। যে পাশের সবচেয়ে উঁচু দেয়াল ছোট, সেই পাশ থেকে এক ঘর ভেতরে এসো — কারণ ওই ঘরে পানি কতটা দাঁড়াবে তা ওই ছোট পাশের উচ্চতাই ঠিক করে দেয়, ওপাশে নিশ্চিত আরও উঁচু দেয়াল আছে। এভাবে ছোট পাশ থেকে এগোতে এগোতে মাঝে মিলে যাও।

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

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

ভিত দুটো: (১) prefix-max thinking — কোনো ঘরের উপর কতটা পানি জমবে তা নির্ভর করে তার বাঁ দিকের সর্বোচ্চ দেয়াল আর ডান দিকের সর্বোচ্চ দেয়ালের ছোটটার উপর। (২) two-pointer discard (problem 12, Container With Most Water-এর জ্ঞাতি) — দুই প্রান্ত থেকে এগিয়ে এসে, যে দিকের boundary ছোট সেই দিকটা নিরাপদে নিষ্পত্তি করা। prefix চিন্তার গভীরে: ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

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

লুকানো logic একটা সূত্র: index i-এর উপর জমা পানি = min(leftMax_i, rightMax_i) - height[i] (ঋণাত্মক হলে 0)। এখানে leftMax_i = 0..i পর্যন্ত সর্বোচ্চ, rightMax_i = i..n-1 পর্যন্ত সর্বোচ্চ। মোট পানি = সব i-এর এই মানের যোগফল। two-pointer চাল এই সত্যকে কাজে লাগায়: যদি leftMax < rightMax হয়, তবে বাঁ দিকের ঘরের ভাগ্য শুধু leftMax-ই ঠিক করে দেয় (ডান দিকে এর চেয়ে উঁচু দেয়াল নিশ্চিত আছে), তাই সেই ঘর এখনই হিসাব করে ফেলা নিরাপদ।

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

দুটো সংস্করণ:

Prefix-max array (সহজ বোঝা): দুটো array leftMax, rightMax (O(n) extra)।
Two pointers (optimal): কোনো extra array নয় — শুধু left, right pointer আর left_max, right_max দুটো scalar; O(1) extra space।

এখানে optimal দুই-pointer version-টাই দেখাব।

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

পানি জমার শর্ত পুরোটাই "বাঁয়ের সর্বোচ্চ বনাম ডানের সর্বোচ্চ" নিয়ে — তাই দুই প্রান্ত থেকে দুটো running max রাখলেই চলে। array-র O(1) random access-এ দুই প্রান্তের উচ্চতা সাথে সাথে পড়া যায়। ছোট-boundary-ওয়ালা দিকটা যেহেতু চূড়ান্ত হয়ে গেছে, সেটা এগিয়ে দিলে প্রতিটা ঘর ঠিক একবার নিষ্পত্তি হয় — extra array ছাড়াই।

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

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

প্রথম সরল চিন্তা: প্রতিটা ঘর i-এর জন্য আলাদা করে তার বাঁ দিকের সর্বোচ্চ আর ডান দিকের সর্বোচ্চ scan করে বের করো, তারপর min(leftMax, rightMax) - height[i] যোগ করো।

উদাহরণ

total = 0
for i in range(n):
    leftMax  = max(height[0..i])     # বাঁ স্ক্যান
    rightMax = max(height[i..n-1])   # ডান স্ক্যান
    total += max(0, min(leftMax, rightMax) - height[i])

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

প্রতিটা ঘরের জন্য দুই দিকেই আবার scan — O(n^2)। একই max বারবার গোনা হচ্ছে। দুটো সমাধান: (ক) আগে থেকে leftMax/rightMax prefix array বানিয়ে O(n) time কিন্তু O(n) space; (খ) two-pointer দিয়ে O(n) time এবং O(1) space — এই শেষেরটাই সেরা।

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

মূল observation: কোনো ঘরের পানি কেবল min(leftMax, rightMax)-এর উপর নির্ভর করে। দুই প্রান্ত থেকে এগোলে, যে দিকের running max ছোট, সেই দিকের বর্তমান ঘরের জন্য min নিশ্চিতভাবেই সেই ছোট max — কারণ অন্য প্রান্তে এর চেয়ে বড় কিছু আছে বলেই সে ছোট। তাই ওই ঘর এখনই হিসাব করে ফেলা নিরাপদ, ওপাশ না জেনেও।

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

left=0, right=n-1, left_max=height[left], right_max=height[right]। যতক্ষণ left < right: যদি left_max < right_max, তবে left এক ঘর ডানে নাও, left_max update করো, আর left_max - height[left] পানি যোগ করো (সবসময় ≥ 0, কারণ left_max update-এর পর ≥ height[left])। নইলে ডান দিকে symmetric কাজ করো। মাঝে মিলে গেলে শেষ। এক pass, O(1) extra।

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

মোচড়: "প্রতিটা ঘরের জন্য দুই দিকে max খুঁজব" (O(n^2)) ছাড়ো। ভাবো "যে পাশের সর্বোচ্চ দেয়াল ছোট, সেই পাশের ঘরের পানি ঐ ছোট দেয়ালই ঠিক করে — তাই সেই পাশ এগিয়ে এখনই গুনে ফেলি।" এই discard-যুক্তিই Container With Most Water (#12)-এর সাথে মেলে।

ছবিতে বোঝা¶

height = [4,2,0,3,2,5] — দুই pointer ভেতরে আসছে (ছোট max-এর দিক এগোয়):

উদাহরণ

L=0(4)            R=5(5)   leftMax=4 < rightMax=5 -> L এগোও
 idx1 h=2: water += 4-2 = 2
 idx2 h=0: water += 4-0 = 4   (মোট 6)
 idx3 h=3: water += 4-3 = 1   (মোট 7)
 idx4 h=2: water += 4-2 = 2   (মোট 9)
 idx5: leftMax max(4,5)=5, water += 0   L==R থামো

answer: 9

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

Input [3, 0, 2]:

left=0(3), right=2(2), left_max=3, right_max=2, water=0।
left_max(3) < right_max(2)? না → ডান শাখা: right=1, right_max=max(2, height[1]=0)=2, water += 2-0 = 2।
left=0, right=1: left_max(3) < right_max(2)? না → ডান শাখা: right=0, right_max=max(2, height[0]=3)=3, water += 3-3 = 0।
left=0, right=0: left < right মিথ্যা → থামো। ফল: 2।

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

Python¶

Python

def trap(height):
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    while left < right:
        if left_max < right_max:           # বাঁ boundary ছোট -> বাঁ ঘর চূড়ান্ত
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:                              # ডান boundary ছোট-সমান -> ডান ঘর চূড়ান্ত
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    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([]) == 0           # খালি
assert trap([1, 2, 3]) == 0    # monotonic, কোনো গর্ত নেই
assert trap([3, 0, 2]) == 2    # এক গর্ত
print("সব test pass!")

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

if not height: return 0 — খালি array-তে পানি নেই।
left, right = 0, len(height)-1 — দুই প্রান্তের pointer।
left_max, right_max = height[left], height[right] — দুই পাশের running সর্বোচ্চ।
while left < right: — মাঝে মেলা পর্যন্ত।
if left_max < right_max: — বাঁ পাশের boundary ছোট, তাই বাঁ ঘরের ভাগ্য left_max-ই ঠিক করে।
left += 1; left_max = max(...); water += left_max - height[left] — এক ঘর ভেতরে, max হালনাগাদ, জমা পানি যোগ (অঋণাত্মক)।
else: — ডান পাশ ছোট-সমান হলে আয়নায় উল্টো কাজ।
return water — মোট জমা পানি।

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

[0,1,0,2,1,0,1,3,2,1,2,1] → দুই pointer এগোতে এগোতে প্রতিটা গর্তের ভাগ যোগ হয়ে 6, assert pass। [4,2,0,3,2,5] → 9; [] → 0; [1,2,3] → ক্রমশ উঁচু, কোনো ঘরে max - height ধনাত্মক হয় না → 0; [3,0,2] → মাঝের গর্তে 2। শেষে print: সব test pass!।

JavaScript ও test cases¶

দুই প্রান্তের running max — ছোট-boundary-ওয়ালা পাশ এগিয়ে সেই ঘর তখনই গোনো।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// total trapped rain water (two pointers, O(1) space)
function trap(height) {
  if (height.length === 0) return 0;
  let left = 0, right = height.length - 1;
  let leftMax = height[left], rightMax = height[right];
  let water = 0;
  while (left < right) {
    if (leftMax < rightMax) {           // বাঁ boundary ছোট -> বাঁ ঘর চূড়ান্ত
      left++;
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
    } else {                            // ডান boundary ছোট-সমান -> ডান ঘর চূড়ান্ত
      right--;
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
    }
  }
  return water;
}
// ---- test cases (example + edge) ----
assert(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) === 6, "classic");
assert(trap([4, 2, 0, 3, 2, 5]) === 9, "valley");
assert(trap([]) === 0, "empty");                                 // edge
assert(trap([1, 2, 3]) === 0, "monotonic");                      // edge
assert(trap([3, 0, 2]) === 2, "one-pit");
console.log("সব JS test pass!");

JS টীকা: leftMax/rightMax আগে Math.max-এ update করে তবেই পানি যোগ করো — তখন মান সবসময় ≥ 0, আলাদা Math.max(0, …) লাগে না। ছোট max-এর দিক এগোও; বড় max-এর দিক এগোলে min নিশ্চিত নয়, হিসাব ভুল।

TypeScript ও test cases¶

TypeScript

function trap(height: number[]): number {
  if (height.length === 0) return 0;
  let left = 0, right = height.length - 1;
  let leftMax: number = height[left], rightMax: number = height[right];
  let water = 0;
  while (left < right) {
    if (leftMax < rightMax) {
      left++;
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
    } else {
      right--;
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
    }
  }
  return water;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), 6, "classic");
expect(trap([]), 0, "empty");
expect(trap([3, 0, 2]), 2, "one-pit");
console.log("সব TS test pass!");

TS টীকা: height: number[] ও leftMax: number annotate করায় index access আর running max সব number; ভুল type পাস করলে compile-time-এ ধরা পড়ে, boundary-reasoning invariant সুরক্ষিত।

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

সময়¶

O(n) — left আর right মিলে array-র উপর মোট একবারই হাঁটে; প্রতিটা step O(1)।

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

O(1) — শুধু কয়েকটা scalar (left, right, left_max, right_max, water); prefix-array version-এর O(n)-ও এড়িয়ে গেলাম।

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

প্রতিটা ঘরে min(leftMax, rightMax) বের করতে গিয়ে দুই দিকে আবার scan করা — O(n^2)।
two-pointer-এ ভুল দিক এগোনো (বড় max-এর দিক) — তখন বর্তমান ঘরের min নিশ্চিত নয়, হিসাব ভুল।
water += ...-এ ঋণাত্মক যোগ করা — left_max/right_max আগে update করলে মান সবসময় ≥ 0, তাই আলাদা max(0, …) লাগে না; update না করলে লাগবে।
boundary বার দুটোকেও গর্ত ভাবা — প্রান্তের বারের উপরে পানি দাঁড়ায় না।

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

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

ভিত্তি: prefix-max array চিন্তা (math 05-prefix-difference-contribution) + two-pointer discard (Container With Most Water #12)। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" আর "Pattern 3 — Prefix Sums" দুটোরই ছোঁয়া এখানে।

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

Container With Most Water (discard-যুক্তির ভিত্তি) — https://leetcode.com/problems/container-with-most-water/ (#12)
Trapping Rain Water II (2D grid, heap লাগে) — https://leetcode.com/problems/trapping-rain-water-ii/
Largest Rectangle in Histogram (boundary + stack) — https://leetcode.com/problems/largest-rectangle-in-histogram/

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

Two pointers with boundary reasoning: "প্রতিটা ঘরের ভাগ্য দুই পাশের max-এর ছোটটার উপর" দেখলে দুই প্রান্ত থেকে running max রাখো, ছোট-boundary-ওয়ালা পাশ এগিয়ে সেই ঘর তখনই গুনে ফেলো — O(n) time, O(1) space।

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

ভবিষ্যতের আমাকে: "পানি = min(leftMax, rightMax) - height; ছোট max-এর দিক এগোও, সেই ঘর চূড়ান্ত।" "জমা পানি / boundary-এর min দিয়ে fill" দেখলেই two-pointer (বা prefix-max array) মনে করবে — O(n), O(1) space।

কোথায় কাজে লাগে¶

Terrain/flood modeling: ভূ-পৃষ্ঠের উঁচু-নিচু profile-এ কতটা পানি জমবে তার estimate।
Reservoir/drainage design: boundary উচ্চতা থেকে captured volume হিসাব।
Histogram/skyline analytics: profile-এর গর্তে "fill" পরিমাণ বের করা।
Memory/buffer utilization: দুই high-watermark-এর মাঝে অব্যবহৃত "trapped" capacity।
Finance: দুই peak-এর মাঝে drawdown-area জাতীয় পরিমাপ।
Image processing: intensity profile-এ valley-fill পরিমাণ নির্ণয়।

মূল pattern: প্রতিটা ঘরের পানি = min(leftMax, rightMax) − height; ছোট max-এর দিক এগিয়ে সেই ঘর চূড়ান্ত করো — O(n), O(1) space।

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