Largest Rectangle in Histogram Using Stack in DSA C# - Build from Scratch

Largest Rectangle in Histogram Using Stack

📖 Scenario: Imagine you have a row of buildings of different heights. You want to find the largest rectangular area that can fit inside the skyline formed by these buildings.

🎯 Goal: Build a program that finds the largest rectangle area in a histogram using a stack to keep track of building heights.

📋 What You'll Learn

Create an integer array called heights with the exact values {2, 1, 5, 6, 2, 3}.

Create an empty stack of integers called stack to store indices.

Use a for loop with variable i to iterate over heights and apply the stack logic to find the largest rectangle.

Print the largest rectangle area as an integer.

💡 Why This Matters

🌍 Real World

Finding the largest rectangle in a histogram helps in image processing, stock market analysis, and land area calculations.

💼 Career

Understanding stack-based algorithms and efficient area calculations is useful for software engineers working on performance-critical applications.

1

Create the histogram data

Create an integer array called heights with these exact values: {2, 1, 5, 6, 2, 3}.

DSA C#

# Create the histogram heights array
# Your code here

Hint

Use int[] heights = {2, 1, 5, 6, 2, 3}; to create the array.

2

Create the stack to store indices

Create an empty stack of integers called stack using Stack<int>.

DSA C#

int[] heights = {2, 1, 5, 6, 2, 3};
// Create an empty stack of integers called stack
// Your code here

Hint

Use Stack<int> stack = new Stack<int>(); to create the stack.

3

Implement the core logic to find largest rectangle

Use a for loop with variable i to iterate from 0 to heights.Length. Inside the loop, use a while loop to pop from stack when current height is less than height at top of stack. Calculate area inside the while loop and update a variable maxArea to keep track of the largest area.

DSA C#

using System.Collections.Generic;

int[] heights = {2, 1, 5, 6, 2, 3};
Stack stack = new Stack();

// Initialize maxArea to 0
// Use a for loop with i from 0 to heights.Length
// Inside, use while loop to pop from stack and calculate area
// Update maxArea accordingly
// Your code here

Hint

Use a while loop to iterate over heights. Push indices when current height is higher or equal. Pop and calculate area when current height is lower. After the loop, pop remaining indices to calculate areas.

4

Print the largest rectangle area

Print the value of maxArea using Console.WriteLine(maxArea);.

DSA C#

using System;
using System.Collections.Generic;

int[] heights = {2, 1, 5, 6, 2, 3};
Stack stack = new Stack();
int maxArea = 0;
int i = 0;

while (i = heights[stack.Peek()])
    {
        stack.Push(i);
        i++;
    }
    else
    {
        int top = stack.Pop();
        int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
        int area = heights[top] * width;
        if (area > maxArea)
            maxArea = area;
    }
}

while (stack.Count > 0)
{
    int top = stack.Pop();
    int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
    int area = heights[top] * width;
    if (area > maxArea)
        maxArea = area;
}

// Print the maxArea
// Your code here

Hint

Use Console.WriteLine(maxArea); to print the largest rectangle area.

Practice

1. What is the main purpose of using a stack in the Largest Rectangle in Histogram problem?

easy

A. To keep track of bars' indices with increasing heights

B. To store the heights of all bars directly

C. To sort the histogram bars by height

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand stack usage in the problem

   The stack stores indices of bars in increasing order of their heights to help calculate areas efficiently.

2. Step 2: Why store indices, not heights?

   Indices allow calculation of width between bars when popping from the stack, which is essential for area calculation.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option A

4. Quick Check:

   Stack stores indices for area calculation [OK]

Hint: Stack holds indices of increasing height bars [OK]

Common Mistakes:

• Storing heights instead of indices
• Using stack to sort bars
• Ignoring width calculation using indices

2. Which of the following C# code snippets correctly initializes a stack to store integers for the histogram problem?

easy

A. int[] stack = new int[10];

B. Stack stack = new Stack();

C. List<int> stack = new List<int>();

D. Stack<int> stack = new Stack<int>();

Solution

1. Step 1: Identify correct stack initialization in C#

   Using generic Stack<int> is the modern and type-safe way to create a stack for integers.

2. Step 2: Why not others?

   The non-generic Stack (like "Stack stack = new Stack();") uses the older style without type safety. A List (like "List<int> stack = new List<int>();") is not a stack. An array (like "int[] stack = new int[10];") is not a stack.

3. Final Answer:

   Stack<int> stack = new Stack<int>(); -> Option D

4. Quick Check:

   Generic Stack<int> is correct stack initialization [OK]

Hint: Use Stack<int> for integer stacks in C# [OK]

Common Mistakes:

• Using non-generic Stack without type safety
• Using List instead of Stack
• Using arrays instead of stack

3. What is the output of the following C# code snippet that calculates the largest rectangle area in histogram heights = [2, 1, 5, 6, 2, 3]?

int[] heights = {2, 1, 5, 6, 2, 3};
int largestRectangleArea(int[] heights) {
    Stack<int> stack = new Stack<int>();
    int maxArea = 0, i = 0;
    while (i < heights.Length) {
        if (stack.Count == 0 || heights[i] >= heights[stack.Peek()]) {
            stack.Push(i++);
        } else {
            int top = stack.Pop();
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, heights[top] * width);
        }
    }
    while (stack.Count > 0) {
        int top = stack.Pop();
        int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
        maxArea = Math.Max(maxArea, heights[top] * width);
    }
    return maxArea;
}

Console.WriteLine(largestRectangleArea(heights));

medium

A. 12

B. 10

C. 15

D. 9

Solution

1. Step 1: Trace the stack operations and area calculations

   For heights [2,1,5,6,2,3], the largest rectangle area is 10 (from bars 5 and 6 with width 2).

2. Step 2: Confirm final maxArea

   After processing all bars and stack cleanup, maxArea is 10.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest area is max height * width using stack [OK]

Common Mistakes:

• Miscomputing width when popping stack
• Forgetting to process remaining stack after loop
• Mixing up indices and heights

4. Identify the bug in this C# code snippet for Largest Rectangle in Histogram:

int largestRectangleArea(int[] heights) {
    Stack<int> stack = new Stack<int>();
    int maxArea = 0, i = 0;
    while (i <= heights.Length) {
        int currentHeight = (i == heights.Length) ? 0 : heights[i];
        if (stack.Count == 0 || currentHeight >= heights[stack.Peek()]) {
            stack.Push(i++);
        } else {
            int top = stack.Pop();
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, heights[top] * width);
        }
    }
    return maxArea;
}

medium

A. Width calculation misses subtracting 1, causing wrong area

B. Stack should store heights, not indices

C. Loop condition should be i < heights.Length, not <=

D. currentHeight assignment is incorrect

Solution

1. Step 1: Check width calculation formula

   Width should be i - stack.Peek() - 1 when stack is not empty, but code misses '-1'.

2. Step 2: Effect of missing '-1'

   Missing '-1' causes width to be larger than actual, leading to incorrect maxArea.

3. Final Answer:

   Width calculation misses subtracting 1, causing wrong area -> Option A

4. Quick Check:

   Width must subtract 1 for correct area [OK]

Hint: Subtract 1 in width calculation after popping stack [OK]

Common Mistakes:

• Forgetting to subtract 1 in width
• Using stack for heights instead of indices
• Incorrect loop boundary causing index errors

5. Given a histogram with heights = [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack approach? Explain how the stack helps find this area.

hard

A. 15

B. 10

C. 12

D. 8

Solution

1. Step 1: Use stack to track indices of increasing heights

   Push indices while heights increase; pop when current height is less, calculating area with popped height and width between indices.

2. Step 2: Calculate largest area for given heights

   For [6,2,5,4,5,1,6], largest rectangle area is 12 (from bars at indices 2,3,4 with min height 4 and width 3, calculated when popping index 3).

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Stack helps find max area = 12 [OK]

Hint: Stack finds max area by tracking increasing bars [OK]

Common Mistakes:

• Not popping all remaining bars after loop
• Incorrect width calculation
• Confusing heights and indices in stack