021 — Trapping Rain Water¶

Source¶

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 বাদ দেওয়া

1. Problem in simple words¶

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

height = [0,1,0,2,1,0,1,3,2,1,2,1]
জমা পানি (#) মোট = 6 একক

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

লুকানো 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-ই ঠিক করে দেয় (ডান দিকে এর চেয়ে উঁচু দেয়াল নিশ্চিত আছে), তাই সেই ঘর এখনই হিসাব করে ফেলা নিরাপদ।

4. Which data structure is needed?¶

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

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-টাই দেখাব।

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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

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

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

9. Brute force thinking¶

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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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।

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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।

15. Python solution¶

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

16. Line-by-line code explanation¶

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 — মোট জমা পানি।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

ভিত্তি: 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" দুটোরই ছোঁয়া এখানে।

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

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

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 নিশ্চিত নয়, হিসাব ভুল।

26. TypeScript solution (with test cases)¶

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 সুরক্ষিত।

27. কোথায় কাজে লাগে (real-world use)¶

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।