012 — Container With Most Water¶

Source¶

Original source: Classic converging two-pointer exercise
Platform: LeetCode — https://leetcode.com/problems/container-with-most-water/
Topic: array / two pointers
Difficulty: Medium
Pattern: two pointers (দুই প্রান্ত থেকে, ছোট দেয়াল discard)
Basic idea inherited from: pair-sum-এর discard argument — প্রতিটা move-এ একটা candidate চিরতরে বাদ দেওয়া যায় বলে O(n)

1. Problem in simple words¶

একটা array height দেওয়া, যেখানে height[i] হলো i-তম খাড়া দেয়ালের উচ্চতা (সব দেয়ালের মধ্যে দূরত্ব 1)। দুটো দেয়াল বেছে তাদের মধ্যে পানি ধরলে কত পানি ধরে = min(দুই দেয়ালের উচ্চতা) * (দুই দেয়ালের মধ্যে দূরত্ব)। সবচেয়ে বেশি কত পানি (area) ধরা সম্ভব, সেটা বের করো।

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
index 1 (উচ্চতা 8) আর index 8 (উচ্চতা 7) -> min(8,7) * (8-1) = 7 * 7 = 49

2. Which basic idea does this inherit from?¶

ভিত two pointers-এর discard argument: দুই প্রান্ত থেকে শুরু করো, আর প্রতিটা step-এ এমনভাবে এক pointer সরাও যাতে কোনো সম্ভাব্য সেরা উত্তর হারিয়ে না যায়। pair-sum-এ "L বাড়ালে sum বাড়ে, R কমালে sum কমে" যেমন; এখানে "ছোট দেয়াল সরালে কিছুই হারাই না"। দুই-pointer-এর math যুক্তি ../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/-তে।

3. What is the hidden math or logic?¶

লুকানো logic: area = min(h[L], h[R]) * (R - L)। দুই প্রান্ত থেকে শুরুতে width সবচেয়ে বড়। এখন ছোট দেয়ালটা সরানোই যুক্তিযুক্ত — কারণ সেই ছোট দেয়াল ধরে রাখলে width তো কমবেই, আর উচ্চতাও ওই ছোট দেয়ালেই আটকে; তাই ছোট দেয়াল ফেলে দিলে কোনো বড় উত্তর হারানোর ভয় নেই। বড় দেয়াল সরালে উল্টো ভালো জোড়া হারাতে পারতাম।

4. Which data structure is needed?¶

কোনো extra data structure লাগে না — শুধু দুটো integer pointer (left, right) আর একটা best। O(1) extra space।

5. Why this data structure fits¶

Array-র O(1) random access-এ height[left] আর height[right] সাথে সাথে পড়া যায়। দুই প্রান্ত থেকে ভেতরে আসা two-pointer scan-এ প্রতিটা index একবারই ছোঁয়া হয়, তাই সব O(n^2) জোড়া না দেখেও সেরা area পাওয়া যায়।

6. Real-life analogy¶

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

7. Visual explanation¶

height = [1, 8, 6, 2, 5, 4, 8, 3, 7] দিয়ে দুই pointer:

L=0(1)  R=8(7): area = min(1,7)*8 = 8 ;  h[L]<h[R] -> L++
L=1(8)  R=8(7): area = min(8,7)*7 = 49;  h[L]>=h[R]-> R--   best 49
L=1(8)  R=7(3): area = min(8,3)*6 = 18;  R--
L=1(8)  R=6(8): area = min(8,8)*5 = 40;  R--
... কোনো জোড়াই 49 ছাড়ায় না
answer: 49

8. Example input and output¶

Input : [1, 8, 6, 2, 5, 4, 8, 3, 7] -> 49
Input : [1, 1]                       -> 1

Edge case 1 (সমান উচ্চতা): [4, 3, 2, 1, 4] -> 16  (দুই প্রান্তের 4, width 4)
Edge case 2 (ছোট):         [1, 2, 1]       -> 2

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা জোড়া দেয়াল (i, j) ধরে area হিসাব করে সবচেয়ে বড়টা রাখো — দুটো nested loop।

best = 0
for i in range(n):
    for j in range(i+1, n):
        area = min(height[i], height[j]) * (j - i)
        best = max(best, area)

10. Why brute force is slow¶

দুটো nested loop মানে প্রায় n*(n-1)/2 জোড়া — O(n^2)। array বড় হলে খুব ধীর। অথচ দুই প্রান্ত থেকে শুরু করে প্রতিটা step-এ ছোট দেয়াল ফেলে দিলে এক pass-এই সেরা area পাওয়া যায়।

11. Key observation¶

মূল observation: দুই প্রান্তের জোড়ায় width সর্বোচ্চ। এখান থেকে ছোট দেয়াল সরালে সম্ভাব্য সেরা উত্তর হারানো যায় না (ছোট দেয়াল ধরে রাখলে height ওতেই সীমিত, width-ও কমবে)। তাই প্রতিটা step একটা দেয়াল চিরতরে বাদ দেয় — n step-এ শেষ।

12. Optimized intuition¶

left=0, right=n-1। যতক্ষণ left < right: এখনকার area (min(h[left],h[right]) * (right-left)) দিয়ে best update করো, তারপর যে প্রান্তের দেয়াল ছোট সেটা ভেতরে সরাও (সমান হলে যেকোনো একটা)। ওরা দেখা করলেই শেষ। এক pass, O(n)।

13. Thinking tweak¶

মোচড়: "সব জোড়া try করব" (O(n^2)) ভুলে গিয়ে ভাবো "দুই প্রান্ত থেকে শুরু করব, সবসময় ছোট দেয়ালটা ফেলে ভেতরে আসব।" ছোট দেয়াল-ই bottleneck, তাই সেটা সরানোই একমাত্র যুক্তিসঙ্গত move।

14. Step-by-step dry run¶

Input [1, 2, 1]:

শুরু: left=0 (1), right=2 (1), best=0।
area = min(1,1) * (2-0) = 1 * 2 = 2; best=2। height[0] < height[2]? 1 < 1 মিথ্যা → right কমাও → right=1।
left=0 (1), right=1 (2): area = min(1,2) * 1 = 1; best 2-ই থাকে। 1 < 2 সত্য → left=1।
left < right মিথ্যা (1 < 1 নয়) → loop শেষ। ফল: best = 2।

15. Python solution¶

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        if height[left] < height[right]:   # ছোট দেয়াল ভেতরে সরাও
            left += 1
        else:
            right -= 1
    return best

# ---- tests ----
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert max_area([1, 1]) == 1
assert max_area([4, 3, 2, 1, 4]) == 16     # দুই প্রান্তের 4
assert max_area([1, 2, 1]) == 2
print("সব test pass!")

16. Line-by-line code explanation¶

left, right = 0, len(height) - 1 — দুই pointer দুই প্রান্তে, width সর্বোচ্চ থেকে শুরু।
while left < right — ওরা দেখা করার আগ পর্যন্ত।
h = min(height[left], height[right]) — পানির উচ্চতা ছোট দেয়ালেই সীমিত।
best = max(best, h * (right - left)) — এখনকার area দিয়ে সেরা update।
if height[left] < height[right]: left += 1 else: right -= 1 — ছোট দেয়ালটা ফেলে ভেতরে আসা; সমান হলে যেকোনো একটা সরালেই চলে।

17. Output walkthrough¶

[1,8,6,2,5,4,8,3,7] → L=1,R=8 জোড়ায় min(8,7)*7 = 49, এর পরের কোনো জোড়া আর ছাড়ায় না → 49, assert pass। [1,1] → 1; [4,3,2,1,4] → দুই প্রান্তের 4, 4*4=16; [1,2,1] → 2। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — দুই pointer একসাথে মিলিয়ে মোট n step; প্রতিটা step O(1)।

19. Space complexity¶

O(1) — শুধু left, right, best — তিনটা scalar।

20. Common mistakes¶

বড় দেয়াল সরিয়ে ফেলা — তখন bottleneck (ছোট দেয়াল) থেকেই যায়, আর ভালো জোড়া হারাতে পারো।
area-তে height যোগ করা বা width ভুলে যাওয়া — area = min(height) * width, যোগ নয় গুণ।
while left <= right লেখা — left == right হলে width 0, অপ্রয়োজনীয় iteration (ক্ষতি নেই, তবে < পরিষ্কার)।

21. Which basic problem this inherits from¶

ভিত্তি: converging two pointers (Reverse String #1, Two Sum II-এর discard যুক্তি)। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো; "প্রতিটা move candidate চিরতরে বাদ দেয়" — এটাই এখানে ছোট দেয়াল discard।

22. Similar harder problems¶

Trapping Rain Water (দুই প্রান্ত + prefix max) — https://leetcode.com/problems/trapping-rain-water/ (#21)
3Sum (sort + two pointers) — https://leetcode.com/problems/3sum/ (#16)
Two Sum II — Input Array Is Sorted — https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

23. Pattern learned¶

Two pointers (discard argument): দুই প্রান্ত থেকে শুরু করে এমন pointer সরাও যেটা কোনো সেরা উত্তর হারায় না। "container / pair of walls / max area" দেখলেই এই ছোট-দেয়াল-discard মনে করো — O(n)।

24. Final summary¶

ভবিষ্যতের আমাকে: "area = min(দুই দেয়াল) × width; দুই প্রান্ত থেকে শুরু করে সবসময় ছোট দেয়াল ফেলে ভেতরে আসো।" "max area / best pair of walls" দেখলেই converging two-pointer মনে করবে — O(n) time, O(1) space।

25. JavaScript solution (with test cases)¶

দুই প্রান্তের pointer আর Math.min দিয়ে area — ছোট দেয়াল সরিয়ে ভেতরে আসা।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// max water area between two walls (converging two pointers)
function maxArea(height) {
  let left = 0, right = height.length - 1;
  let best = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    best = Math.max(best, h * (right - left));
    if (height[left] < height[right]) left++;   // ছোট দেয়াল ভেতরে সরাও
    else right--;
  }
  return best;
}
// ---- test cases (example + edge) ----
assert(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) === 49, "classic");
assert(maxArea([1, 1]) === 1, "min-two");
assert(maxArea([4, 3, 2, 1, 4]) === 16, "equal-ends");          // edge
assert(maxArea([1, 2, 1]) === 2, "small");
console.log("সব JS test pass!");

JS টীকা: Math.min/Math.max দিয়ে height আর best হিসাব; area = min(walls) * width — গুণ, যোগ নয়। while (left < right)-এ < রাখলে width 0-এর অপ্রয়োজনীয় iteration এড়ানো যায়।

26. TypeScript solution (with test cases)¶

function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1;
  let best = 0;
  while (left < right) {
    const h: number = Math.min(height[left], height[right]);
    best = Math.max(best, h * (right - left));
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49, "classic");
expect(maxArea([4, 3, 2, 1, 4]), 16, "equal-ends");
expect(maxArea([1, 2, 1]), 2, "small");
console.log("সব TS test pass!");

TS টীকা: height: number[] type-এ index access সব number, তাই Math.min-এ ভুল type ঢোকার সুযোগ নেই; return-ও number বলে caller নিশ্চিন্ত।

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

Resource/capacity planning: দুই সীমানার মধ্যে সর্বোচ্চ ধারণক্ষমতা (bottleneck = ছোট সীমা) বের করা — যেমন দুই pillar-এর মাঝে সর্বোচ্চ load।
Two-pointer optimization base: যেকোনো "best pair under a constraint" সমস্যায় O(n²) এড়িয়ে converging pointer ব্যবহার।
Image/UI layout: দুই boundary-র মাঝে সবচেয়ে বড় fit-করা rectangle/panel বের করা।
Reservoir/tank design: দুই দেয়ালের উচ্চতার ছোটটা দিয়ে সর্বোচ্চ ধারণযোগ্য আয়তন আন্দাজ করা।
Trading spreads: দুই price level-এর মধ্যে সর্বোচ্চ সম্ভাব্য area/coverage হিসাব।
Networking: দুই node-এর মধ্যে bottleneck bandwidth (min link) দিয়ে throughput estimate।

মূল pattern: bottleneck হলো ছোট প্রান্ত — তাই সেটাই সরাও; "max area / best pair of walls" দেখলেই converging two-pointer।

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