020 — Largest Rectangle in Histogram

Source

• Original source: Classic monotonic-stack exercise
• Platform: LeetCode — https://leetcode.com/problems/largest-rectangle-in-histogram/
• Topic: stack (monotonic)
• Difficulty: Hard
• Pattern: monotonic stack
• Basic idea inherited from: Problem 9-এর previous/next-smaller machinery — প্রতিটা bar কতদূর বাঁয়ে আর ডানে নিজের উচ্চতা ধরে ছড়াতে পারে

1. Problem in simple words

তোমাকে একটা histogram দেওয়া আছে — পরপর কিছু বার, প্রতিটার প্রস্থ 1 আর উচ্চতা heights[i]। এই বারগুলোর ভেতরে আঁকা যায় এমন সবচেয়ে বড় আয়তক্ষেত্রের ক্ষেত্রফল বের করো। আয়তক্ষেত্রটা পরপর কয়েকটা বার জুড়ে থাকতে পারে, কিন্তু তার উচ্চতা ওই অংশের সবচেয়ে খাটো বারের সমান।

heights = [2, 1, 5, 6, 2, 3]-এর জন্য:

        #
      # #
      # #
      # #   #
  #   # #   #
  # # # # # #
  2 1 5 6 2 3
সবচেয়ে বড়: index 2..3 (উচ্চতা min(5,6)=5, প্রস্থ 2) -> 5*2 = 10

2. Which basic idea does this inherit from?

এটা Problem 9 (monotonic stack)-এর geometry রূপ। সেখানে প্রতিটা element-এর জন্য "next greater" খুঁজছিলে; এখানে প্রতিটা bar-এর জন্য খুঁজি previous-smaller আর next-smaller — কারণ একটা bar-কে উচ্চতা ধরে রেখে আয়তক্ষেত্র যতদূর বাঁয়ে আর ডানে টানা যায়, সেটা থামে ঠিক যেখানে তার চেয়ে খাটো বার পড়ে। সেই বাঁ-সীমা আর ডান-সীমার মধ্যেকার প্রস্থ × bar-এর উচ্চতা = সেই bar-কে নিচু-সীমা ধরে বানানো সবচেয়ে চওড়া আয়তক্ষেত্র।

3. What is the hidden math or logic?

লুকানো logic: প্রতিটা সম্ভাব্য আয়তক্ষেত্রের উচ্চতা কোনো-না-কোনো একটা বারের সমান (যে বারটা ওই আয়তক্ষেত্রের সবচেয়ে খাটো)। তাই প্রতিটা bar i-কে "আমিই সবচেয়ে খাটো" ধরে জিজ্ঞেস করি — আমি বাঁয়ে কতদূর আর ডানে কতদূর heights[i] উচ্চতা ধরে ছড়াতে পারি?

বাঁয়ে থামি প্রথম heights[i]-এর চেয়ে খাটো বারে (previous-smaller), ডানেও তাই (next-smaller)। সেই দুই সীমার মধ্যে প্রস্থ width, আর ক্ষেত্রফল heights[i] * width। সব bar-এর জন্য এই ক্ষেত্রফলের সর্বোচ্চটাই উত্তর। monotonic stack এই previous/next-smaller এক pass-এই দেয় — pop করার মুহূর্তেই দুই সীমা জানা হয়ে যায়।

4. Which data structure is needed?

একটা monotonic stack (Python-এ list) যেখানে index রাখি, আর stack-এ উচ্চতা গুলো নিচ-থেকে-উপর বাড়তে থাকে (increasing)। একটা bar যখন pop হয়, তখন তার ডান-সীমা = current index, আর বাঁ-সীমা = pop-এর পরে যে index top-এ থাকে। সাথে একটা sentinel (শেষে একটা 0-উচ্চতার bar) যোগ করি যাতে loop শেষে stack-এ পড়ে থাকা সবাইকে pop করানো যায়।

5. Why this data structure fits

increasing stack-এ যতক্ষণ বার উঁচু হতে থাকে, ততক্ষণ কেউ pop হয় না — তারা সবাই এখনো ডান দিকে আরও ছড়াতে পারে। যেই একটা খাটো bar আসে, সে stack-এর উপরের উঁচু bar-দের "তোমাদের ডান-সীমা পেয়ে গেছ" বলে pop করায়, আর তখনই তাদের ক্ষেত্রফল হিসাব হয়ে যায়। প্রতিটা bar একবার push, একবার pop → O(n)। index রাখায় প্রস্থ O(1)-তে বেরোয়।

6. Real-life analogy

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

7. Visual explanation

heights = [2, 1, 5, 6, 2, 3] (শেষে sentinel 0 জুড়ে), index-এর increasing stack (top ডানে):

i  h  action                                          stack(idx)   area হিসাব
0  2  push                                            [0]          —
1  1  h[0]=2>1 pop0: H=2,L=-1,W=1-(-1)-1=1 -> 2       [1]          2
2  5  push                                            [1,2]        —
3  6  push                                            [1,2,3]      —
4  2  h[3]=6>2 pop3: H=6,L=2,W=4-2-1=1 -> 6
      h[2]=5>2 pop2: H=5,L=1,W=4-1-1=2 -> 10          [1,4]        10  <- best
5  3  push                                            [1,4,5]      —
6  0  h[5]=3>0 pop5: H=3,L=4,W=6-4-1=1 -> 3
      h[4]=2>0 pop4: H=2,L=1,W=6-1-1=4 -> 8
      h[1]=1>0 pop1: H=1,L=-1,W=6-(-1)-1=6 -> 6       [6]          max=10

H = pop-করা bar-এর উচ্চতা, L = pop-এর পর top index (নেই হলে -1), W = i - L - 1।

8. Example input and output

Input : [2, 1, 5, 6, 2, 3]    -> 10
Input : [2, 4]                -> 4   (4*1, বা 2*2 — দুটোই 4)
Input : [6, 2, 5, 4, 5, 1, 6] -> 12  (5,4,5: উচ্চতা 4, প্রস্থ 3)

Edge case 1 (একটা bar)   : [5]       -> 5
Edge case 2 (একই উচ্চতা) : [3, 3, 3] -> 9   (পুরোটা: 3*3)
Edge case 3 (খালি)       : []        -> 0

9. Brute force thinking

সরল চিন্তা: প্রতিটা জোড়া সীমানা (i, j)-র জন্য ওই অংশের সবচেয়ে খাটো bar বের করি, তারপর min_height * (j - i + 1) হিসাব করে সর্বোচ্চটা রাখি।

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

10. Why brute force is slow

দুটো nested loop মানে O(n^2)-সংখ্যক অংশ, আর min চলমানভাবে রাখলেও মোট O(n^2)। n = 10^5 হলে প্রায় 10^10 step — অসম্ভব। প্রতিটা bar-এর জন্য বাঁ/ডান-সীমা আলাদাভাবে বারবার খোঁজা পুরো অপচয়; monotonic stack এক pass-এ প্রতিটা bar-কে একবার ছুঁয়ে O(n)-তে দুই সীমাই দেয়।

11. Key observation

মূল observation: প্রতিটা সর্বোচ্চ আয়তক্ষেত্রের উচ্চতা কোনো একটা bar-এর সমান, আর সেই bar-ই ওই আয়তক্ষেত্রের সবচেয়ে খাটো। তাই সব আয়তক্ষেত্র দেখার দরকার নেই — শুধু "প্রতিটা bar যদি নিচু-সীমা হয় তবে সর্বোচ্চ কত চওড়া?" এই n-টা প্রশ্নের উত্তর হলেই চলে, আর সেটা previous/next-smaller।

12. Optimized intuition

index-এর increasing stack রাখো; heights-এর শেষে একটা sentinel 0 যোগ করো। প্রতিটা (i, h)-তে: যতক্ষণ stack খালি নয় আর top-এর bar h-এর চেয়ে উঁচু, ততক্ষণ pop করো — pop-করা bar-এর উচ্চতা H, তার ডান-সীমা current i, বাঁ-সীমা pop-এর পরের top (stack[-1], নাহলে -1); প্রস্থ i - left - 1, ক্ষেত্রফল H * width, max আপডেট করো। তারপর i push করো। sentinel 0 শেষে বাকি সবাইকে pop করিয়ে দেয়।

13. Thinking tweak

মোচড়: "সব সম্ভাব্য আয়তক্ষেত্র গুনব" — এভাবে ভেবো না (O(n^2))। বরং প্রতিটা bar-কে আলাদা করে জিজ্ঞেস করো — "আমি যদি সবচেয়ে খাটো হই, তবে বাঁয়ে-ডানে কতদূর আমার উচ্চতা ধরে ছড়াতে পারি?" এই উল্টো দৃষ্টিতে n-টা bar × O(1) করে = O(n), আর প্রতিটা আয়তক্ষেত্র ঠিক একবার (তার নিচু-সীমা bar-এর মাধ্যমে) গোনা হয়।

14. Step-by-step dry run

Input [2, 1, 2] (sentinel দিয়ে [2, 1, 2, 0]):

1. i=0 (2): push → [0]
2. i=1 (1): h[0]=2 > 1 → pop 0: H=2, left=-1, W=1-(-1)-1=1, area 2, best=2; push 1 → [1]
3. i=2 (2): h[1]=1 > 2? না; push 2 → [1,2]
4. i=3 (0): h[2]=2 > 0 → pop 2: H=2, left=1, W=3-1-1=1, area 2, best=2; h[1]=1 > 0 → pop 1: H=1, left=-1, W=3-(-1)-1=3, area 3, best=3; push 3
5. return best = 3

15. Python solution

def largest_rectangle_area(heights):
    stack = []                          # index রাখে; উচ্চতা নিচ->উপর বাড়তে থাকে
    max_area = 0
    extended = heights + [0]            # শেষে sentinel 0 -> বাকি সবাইকে pop করায়
    for i, h in enumerate(extended):
        while stack and extended[stack[-1]] > h:
            height = extended[stack.pop()]      # এই bar-ই আয়তক্ষেত্রের নিচু-সীমা
            left = stack[-1] if stack else -1   # বাঁয়ের previous-smaller
            width = i - left - 1                # দুই সীমার মাঝের প্রস্থ
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

# ---- tests ----
assert largest_rectangle_area([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle_area([2, 4]) == 4
assert largest_rectangle_area([6, 2, 5, 4, 5, 1, 6]) == 12
assert largest_rectangle_area([5]) == 5             # একটা bar
assert largest_rectangle_area([3, 3, 3]) == 9       # একই উচ্চতা, পুরো প্রস্থ
assert largest_rectangle_area([]) == 0              # খালি
print("সব test pass!")

16. Line-by-line code explanation

• stack = [] — index জমবে; উচ্চতা নিচ-থেকে-উপর increasing রাখা invariant।
• extended = heights + [0] — শেষে একটা 0-উচ্চতার ভুয়া bar; এটা loop শেষে stack-এ পড়ে থাকা সব bar-কে pop করায় (আলাদা cleanup লাগে না)। মূল input বদলায় না।
• while stack and extended[stack[-1]] > h: — top-এর bar current-এর চেয়ে উঁচু মানে তার ডান-সীমা পাওয়া গেল।
• height = extended[stack.pop()] — pop-করা bar-ই এই আয়তক্ষেত্রের নিচু-সীমা (উচ্চতা)।
• left = stack[-1] if stack else -1 — pop-এর পরের top-ই বাঁয়ের previous-smaller; কেউ না থাকলে -1 (একদম বাঁ প্রান্ত পর্যন্ত)।
• width = i - left - 1 — বাঁ-সীমা আর ডান-সীমা (i)-র মধ্যেকার পূর্ণ প্রস্থ।
• max_area = max(...) — এই bar-কে নিচু-সীমা ধরে সর্বোচ্চ ক্ষেত্রফল।
• stack.append(i) — current bar এখন stack-এ, ভবিষ্যতের ডান-সীমার অপেক্ষায়।

17. Output walkthrough

largest_rectangle_area([2,1,5,6,2,3]) → section 7-এর trace মতো index 4-এ 5 pop হওয়ার সময় 5*2 = 10 পাওয়া যায়, যা best। largest_rectangle_area([3,3,3]) → কেউ pop হয় না যতক্ষণ sentinel আসে; তখন শেষ 3 থেকে শুরু করে প্রস্থ বাড়তে বাড়তে 1*3 + ... হিসাবে সর্বোচ্চ 3*3 = 9। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

• sentinel 0 যোগ না করা — তখন loop শেষে stack-এ পড়ে থাকা increasing bar-গুলোর ক্ষেত্রফল কখনো হিসাব হয় না; আলাদা cleanup loop লাগে।
• প্রস্থ i - left - 1-এর বদলে i - left বা i - stack[-1] লেখা — এক ঘর ভুল হয়ে ক্ষেত্রফল গণ্ডগোল।
• stack-এ উচ্চতা রাখা, index নয় — তখন প্রস্থ বের করা যায় না।
• > বনাম >= — সমান উচ্চতার ক্ষেত্রে > রাখলে duplicate ঠিকঠাক handle হয় (সমানদের পরে pop করালেও বাঁ-সীমা ঠিক থাকে); এখানে > যথেষ্ট আর নিরাপদ।

21. Which basic problem this inherits from

ভিত্তি: Problem 9-এর monotonic-stack previous/next-smaller machinery; chapter-এর ../patterns.md Pattern 4 (Monotonic Stack)। নতুন অংশ — pop করার মুহূর্তে দুই সীমা (বাঁ ও ডান) মিলিয়ে geometry (ক্ষেত্রফল) বের করা।

22. Similar harder problems

• Maximal Rectangle (2D, প্রতি row-তে histogram) — https://leetcode.com/problems/maximal-rectangle/
• Trapping Rain Water (stack geometry) — https://leetcode.com/problems/trapping-rain-water/ (এই tracker-এর #21)
• Sum of Subarray Minimums (previous/next-smaller contribution) — https://leetcode.com/problems/sum-of-subarray-minimums/ (#17)

23. Pattern learned

Monotonic stack for geometry: "histogram-এর largest rectangle", "প্রতিটা bar কতদূর ছড়ায়" দেখলে index-এর increasing stack রাখো, sentinel 0 জোড়ো; খাটো bar এসে উঁচুদের pop করায়, তখনই height * (i - left - 1) হিসাব করো।

24. Final summary

ভবিষ্যতের আমাকে: largest rectangle = প্রতিটা bar-কে নিচু-সীমা ধরে সর্বোচ্চ প্রস্থ। index-এর increasing stack + শেষে sentinel 0; খাটো এলে pop, H * (i - left - 1)। প্রস্থে -1-টা ভুলো না, index রাখো (উচ্চতা নয়)। "histogram rectangle / previous-next smaller geometry" দেখলেই এই pattern।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function largestRectangleArea(heights) {
  const stack = [];                  // index রাখে; উচ্চতা নিচ->উপর বাড়ে
  let maxArea = 0;
  const extended = [...heights, 0];  // শেষে sentinel 0 -> বাকি সবাইকে pop করায়
  for (let i = 0; i < extended.length; i++) {
    while (stack.length && extended[stack[stack.length - 1]] > extended[i]) {
      const height = extended[stack.pop()];          // এই bar-ই নিচু-সীমা
      const left = stack.length ? stack[stack.length - 1] : -1;
      const width = i - left - 1;                     // দুই সীমার মাঝের প্রস্থ
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

// ---- test cases ----
assert(largestRectangleArea([2, 1, 5, 6, 2, 3]) === 10, "main");
assert(largestRectangleArea([2, 4]) === 4, "two");
assert(largestRectangleArea([6, 2, 5, 4, 5, 1, 6]) === 12, "mid");
assert(largestRectangleArea([5]) === 5, "single");
assert(largestRectangleArea([3, 3, 3]) === 9, "equal");
assert(largestRectangleArea([]) === 0, "empty");
console.log("সব JS test pass!");

JS টীকা: [...heights, 0] দিয়ে spread করে নতুন array বানাই — মূল input বদলায় না, আর শেষে একটা 0-উচ্চতার sentinel যোগ হয় যা loop শেষে stack-এ পড়ে থাকা সব bar-কে pop করিয়ে ক্ষেত্রফল হিসাব করায়। width = i - left - 1-এর -1-টা গুরুত্বপূর্ণ; ভুলে i - left লিখলে এক ঘর বেশি গুনে answer ভুল হবে। left বের করতে stack খালি কিনা ternary দিয়ে দেখি (-1 মানে একদম বাঁ প্রান্ত)।

26. TypeScript solution (with test cases)

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];                  // index রাখে
  let maxArea = 0;
  const extended: number[] = [...heights, 0];  // sentinel
  for (let i = 0; i < extended.length; i++) {
    while (stack.length && extended[stack[stack.length - 1]] > extended[i]) {
      const height = extended[stack.pop()!];
      const left = stack.length ? stack[stack.length - 1] : -1;
      const width = i - left - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
expect(largestRectangleArea([2, 1, 5, 6, 2, 3]), 10, "main");
expect(largestRectangleArea([2, 4]), 4, "two");
expect(largestRectangleArea([6, 2, 5, 4, 5, 1, 6]), 12, "mid");
expect(largestRectangleArea([5]), 5, "single");
expect(largestRectangleArea([3, 3, 3]), 9, "equal");
expect(largestRectangleArea([]), 0, "empty");
console.log("সব TS test pass!");

TS টীকা: stack: number[] টাইপ দেওয়ায় স্পষ্ট থাকে এতে index জমছে (উচ্চতা নয়) — geometry problem-এ এই পার্থক্য ভুললেই বাগ। stack.pop()! দিয়ে non-null assert করি কারণ while-এর stack.length শর্ত নিশ্চিত করে pop undefined দেবে না। সবকিছু number হওয়ায় Math.max(maxArea, height * width)-এ কোনো implicit coercion-এর ঝুঁকি নেই।

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

• Image processing: binary image-এ "সবচেয়ে বড় rectangle of 1s" (maximal rectangle) বের করতে প্রতি row-কে histogram ধরে এই algorithm চলে।
• Data visualization: bar chart/skyline-এ সবচেয়ে বড় ফাঁকা বা ভরা ব্লক বের করা।
• Layout/packing: UI বা PCB layout-এ available rectangular space খোঁজা।
• Stock/market profile: price-volume histogram-এ সবচেয়ে বড় "value area" বের করা।
• Resource utilization: time-vs-capacity bar-এ সবচেয়ে বড় সুষম-উচ্চতা window খোঁজা।

এক কথায়, histogram-জাতীয় bar-data-তে "প্রতিটা bar কতদূর তার উচ্চতা ধরে ছড়ায়" (previous/next-smaller geometry) চাইলে এই monotonic-stack pattern O(n)-তে largest rectangle দেয়।

---

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