Skip to content

025 — Trapping Rain Water

Source

  • Original source: Classic capstone interview problem (elevation map water trapping)
  • Platform: LeetCode — https://leetcode.com/problems/trapping-rain-water/
  • Topic: arrays + stacks + prefix-max
  • Difficulty: Hard
  • Pattern: monotonic stack AND two pointers (দুটোই করো)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 02 arrays (bar-গুলোর height array scan), stacks (04/stacks-এর monotonic stack), আর 01 math-এর prefix-max idea (বাঁ ও ডানের সর্বোচ্চ wall)। তিন tool তিন রকম সমাধান দেয়, উত্তর এক।

1. Problem in simple words

তোমাকে একটা non-negative integer array দেওয়া আছে, যেখানে প্রতিটা সংখ্যা একটা bar-এর উচ্চতা (width 1 ধরা)। বৃষ্টি হলে এই উঁচু-নিচু ভূদৃশ্যের গর্তগুলোতে জল জমে। মোট কত একক জল আটকে থাকবে, সেটা বের করো।

প্রতিটা position-এ জমা জল = বাঁ দিকের সর্বোচ্চ wall আর ডান দিকের সর্বোচ্চ wall — এই দুটোর মধ্যে ছোটটা, বিয়োগ ওই position-এর নিজের উচ্চতা (যদি positive হয়)।

heights : [0,1,0,2,1,0,1,3,2,1,2,1]
জমা জল  : 6 একক

2. Which basic idea does this inherit from?

এই problem তিনটা আগের ধারণা জোড়া দেয়:

  • 02 arrays থেকে: height array-র উপর index-ধরে scan, আর কোন bar কোথায় বসে সেই thinking।
  • stacks (04/stacks) থেকে: একটা monotonic (decreasing) stack — index জমিয়ে রেখে যখন উঁচু bar আসে তখন গর্ত "settle" করা।
  • 01 math-এর prefix-max idea থেকে: প্রতিটা position-এর বাঁ-সর্বোচ্চ আর ডান-সর্বোচ্চ wall একটা running maximum (prefix/suffix max)।

একা array দেয় scan; stack দেয় "কখন একটা গর্ত বন্ধ হলো" ধরা; prefix-max দেয় boundary wall। তিনটে মিলে O(n)।

3. What is the hidden math or logic?

লুকানো logic একটা bounded-by-the-shorter-wall নিয়ম: position i-তে জল জমে min(leftMax[i], rightMax[i]) - height[i] (negative হলে 0)। জল কখনো তার নিচু পাশের wall ছাড়িয়ে উঠতে পারে না — তাই ছোট wall-টাই ছাদ ঠিক করে।

পুরো array-র উত্তর = প্রতিটা position-এর এই contribution-এর যোগফল।

4. Which data structure is needed?

তিন পথ, একই উত্তর:

  • Prefix-max (01) path: দুটো array — leftMax, rightMax — অথবা two pointers দিয়ে O(1) space-এ একই হিসাব।
  • Monotonic stack (04) path: একটা stack যেখানে decreasing height-এর index জমা; উঁচু bar এলে layer-by-layer জল যোগ।

5. Why this data structure fits

Brute force প্রতি position-এ আবার বাঁ ও ডান scan করে — অপচয়, কারণ leftMax/rightMax একবার scan করেই জানা যায় (prefix-max, 01)। two pointers সেই দুই running max-কে O(1) space-এ মিশিয়ে দেয়।

Monotonic stack আরেকটা দৃষ্টিভঙ্গি দেয় (04/stacks): এটা "একটা গর্ত কখন বন্ধ হয়" সেই ঘটনা ধরে — যা daily-temperatures-এর মতো "পরের বড় element" pattern-এরই আত্মীয়, তাই দুটো একসাথে শেখা mutually reinforcing।

6. Real-life analogy

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

তাই প্রতিটা জায়গায় প্রশ্ন একটাই: "আমার দুই পাশের সবচেয়ে উঁচু দেয়াল দুটোর মধ্যে ছোটটা কত উঁচু?" — সেটাই জলের ছাদ।

7. Visual explanation

[0,1,0,2,1,0,1,3,2,1,2,1]-এ জল (~ = জল, # = bar):

height
  3                #
  2        #     # # ~ #
  1    # ~ # # ~ # # # # #
  0  # # # # # # # # # # # #
     0 1 2 3 4 5 6 7 8 9 ...

position 2: leftMax=1, rightMax=3 -> min=1, height=0 -> জল 1
position 4: leftMax=2, rightMax=3 -> min=2, height=1 -> জল 1
position 5: leftMax=2, rightMax=3 -> min=2, height=0 -> জল 2
position 6: leftMax=2, rightMax=3 -> min=2, height=1 -> জল 1
position 9: leftMax=3, rightMax=2 -> min=2, height=1 -> জল 1
মোট = 1+1+2+1+1 = 6

8. Example input and output

Input : [0,1,0,2,1,0,1,3,2,1,2,1]   -> Output: 6
Input : [4,2,0,3,2,5]               -> Output: 9

Edge case 1 (একঘেয়ে বাড়ছে): [1,2,3,4]  -> 0   (কোনো গর্ত নেই)
Edge case 2 (খুব ছোট): [2,0,2]          -> 2

9. Brute force thinking

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

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

10. Why brute force is slow

প্রতিটা position-এ বাঁ ও ডান দুটোই পুরো scan — position-প্রতি O(n), মোট O(n²)। বড় array-তে ধীর। কারণ একই leftMax/rightMax আমরা বারবার নতুন করে হিসাব করছি — prefix-max (01) precompute সেটা দূর করে, two pointers আবার space-ও O(1)-এ নামায়।

11. Key observation

মূল observation: জলের ছাদ ঠিক করে নিচু পাশের wall, আর leftMax/rightMax দুটোই monotonic (বাঁ থেকে ডান leftMax কখনো কমে না; ডান থেকে বাঁ rightMax কখনো কমে না)। তাই দুই প্রান্ত থেকে এগোতে এগোতে যে পাশের running max ছোট, সেই পাশের জল নিশ্চিতভাবে settle করা যায় — অন্য পাশ না জেনেও।

12. Optimized intuition

Two-pointer (prefix-max, O(1) space): l, r দুই প্রান্তে; leftMax, rightMax ধরো। যে পাশের height ছোট, সেই pointer এগোও, কারণ ওই পাশের জল ছোট-max দিয়েই bounded — water += max(0, sideMax - height[ptr])।

Monotonic stack (04): decreasing index জমাও; নতুন bar আগের bar-এর চেয়ে উঁচু হলে, stack থেকে নিচু bar pop করে তার উপরের জল layer যোগ করো (bounded width × bounded height)।

13. Thinking tweak

মোচড়: "প্রতিটা position-এ দুপাশ scan করব" ভাবার বদলে ভাবো "দুই পাশের running max-ই যথেষ্ট, আর যে পাশ ছোট সেই পাশ এখনই settle করা নিরাপদ।" O(n²) double-scan একটা O(n) two-pointer sweep-এ গুটিয়ে যায়।

14. Step-by-step dry run

Two pointers on [2,0,2]:

  1. l=0 (h=2), r=2 (h=2), leftMax=0, rightMax=0, water=0।
  2. height[l]=2 <= height[r]=2 → বাঁ দিক। leftMax = max(0,2)=2; water += 2-2 = 0; l=1।
  3. height[l]=0 <= height[r]=2 → বাঁ দিক। leftMax = max(2,0)=2; water += 2-0 = 2; l=2।
  4. l == r → থামো। মোট water = 2। ✓

15. Python solution

def trap_two_pointer(height):
    """PREFIX-MAX idea (01) + two pointers (02): O(n) time, O(1) space।
    যে পাশের height ছোট, সেই পাশের জল ছোট-max দিয়েই bounded — তাই settle নিরাপদ।"""
    if not height:
        return 0
    l, r = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while l < r:
        if height[l] <= height[r]:          # বাঁ পাশ ছোট/সমান -> বাঁ settle
            left_max = max(left_max, height[l])
            water += left_max - height[l]    # bounded by left_max
            l += 1
        else:                               # ডান পাশ ছোট -> ডান settle
            right_max = max(right_max, height[r])
            water += right_max - height[r]   # bounded by right_max
            r -= 1
    return water


def trap_monotonic_stack(height):
    """MONOTONIC STACK (04/stacks): decreasing index জমাই; উঁচু bar এলে
    নিচু bar pop করে তার উপরের জল layer যোগ করি (width × bounded height)।"""
    stack = []                              # decreasing height-এর index
    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
        stack.append(i)
    return water


def trap_prefix_arrays(height):
    """obviously-correct reference: leftMax আর rightMax array আলাদা করে বানিয়ে যোগ।"""
    n = len(height)
    if n == 0:
        return 0
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))


# ---- tests ----
ex1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
assert trap_two_pointer(ex1) == 6
assert trap_monotonic_stack(ex1) == 6
assert trap_prefix_arrays(ex1) == 6

ex2 = [4, 2, 0, 3, 2, 5]
assert trap_two_pointer(ex2) == 9
assert trap_monotonic_stack(ex2) == 9

# edge cases
assert trap_two_pointer([]) == 0                  # খালি
assert trap_two_pointer([5]) == 0                 # একটা bar
assert trap_two_pointer([1, 2, 3, 4]) == 0        # একঘেয়ে বাড়ছে
assert trap_two_pointer([4, 3, 2, 1]) == 0        # একঘেয়ে কমছে
assert trap_two_pointer([2, 0, 2]) == 2           # ছোট গর্ত
assert trap_monotonic_stack([2, 0, 2]) == 2

# তিন method সবসময় একমত: random fuzz
import random
random.seed(25)
for _ in range(500):
    n = random.randint(0, 15)
    h = [random.randint(0, 8) for _ in range(n)]
    a = trap_two_pointer(h)
    b = trap_monotonic_stack(h)
    c = trap_prefix_arrays(h)
    assert a == b == c, (h, a, b, c)

print("সব test pass!")

16. Line-by-line code explanation

  • trap_two_pointer — l, r দুই প্রান্তে; ছোট-height পাশের running max দিয়ে জল bounded, তাই সেই pointer এগিয়ে settle (prefix-max + two pointers)।
  • trap_monotonic_stack — decreasing index stack; উঁচু bar এলে নিচু bar pop করে width × (min(দুই দেয়াল) - তলা) জল যোগ; বাঁ দেয়াল না থাকলে break।
  • trap_prefix_arrays — leftMax/rightMax array আলাদা precompute করে position-প্রতি min - height যোগ; obviously-correct reference।
  • random fuzz তিন method-কে 500 case-এ মিলিয়ে দেখে।

17. Output walkthrough

[0,1,0,2,1,0,1,3,2,1,2,1]-এ তিন method-ই 6 দেয়; [4,2,0,3,2,5]-এ 9। একঘেয়ে বাড়া/কমা array-তে 0 (গর্ত নেই), [2,0,2]-তে 2। শেষে 500 random fuzz-এ two-pointer, monotonic stack, আর prefix-array তিনটাই একমত — তিন দৃষ্টিভঙ্গি, এক উত্তর। শেষে print: সব test pass!।

18. Time complexity

তিন method-ই O(n) — two-pointer একবার sweep, monotonic stack প্রতি index একবার push + একবার pop, prefix-array দুটো scan + একটা যোগ।

19. Space complexity

  • two-pointer: O(1) (শুধু কয়েকটা variable) — সবচেয়ে ভালো।
  • monotonic stack: O(n) (worst case সব index stack-এ)।
  • prefix-array: O(n) (দুটো max array)।

20. Common mistakes

  • min(leftMax, rightMax)-এর বদলে শুধু এক পাশের max ব্যবহার করা — জল নিচু পাশ দিয়ে গড়িয়ে পড়ে, তাই ছোটটাই ছাদ।
  • two-pointer-এ ভুল পাশ এগোনো — সবসময় ছোট-height পাশ এগোতে হবে, তবেই সেই পাশ settle নিরাপদ।
  • monotonic stack-এ pop-এর পর stack খালি হলে জল যোগ করা — বাঁ দেয়াল ছাড়া জল ধরে না।

21. Which basic problem this inherits from

ভিত্তি: array single-pass scan (02 arrays, ../../02-arrays-and-strings/) + monotonic stack (04/stacks, "পরের বড় element" pattern, এই tracker-এর #14 Daily Temperatures) + prefix/suffix max (01 math, ../../01-math-based-programming-fundamentals/)। তিনটা cold-এ জানা থাকলে তিন সমাধানই নিজে থেকে আসে।

22. Similar harder problems

23. Pattern learned

Monotonic stack AND two pointers: একই trapping problem দুই লেন্সে দেখা — (a) প্রতিটা position-এ min(leftMax, rightMax) - height, two-pointer-এ O(1) space; (b) monotonic stack দিয়ে গর্ত layer-by-layer settle। arrays + stacks + prefix-max-এর canonical মেলবন্ধন।

24. Final summary

ভবিষ্যতের আমাকে: "elevation/wall-এর মাঝে জল" দেখলেই দুটো সমাধান মনে করবে। Two-pointer: ছোট-height পাশ এগোও, ওই পাশের running max দিয়ে জল bounded — O(1) space। Monotonic stack: decreasing index জমাও, উঁচু bar এলে নিচু pop করে layer যোগ। দুটোই interview-তে দেখানো ভালো — একটা space-optimal, একটা stack-thinking দেখায়।

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