Largest Rectangle in Histogram Using Stack in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Largest Rectangle Calculation

What is the output of the following C# code that calculates the largest rectangle area in a histogram using a stack?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int LargestRectangleArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.Length) {
            if (stack.Count == 0 || heights[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;
        }
        return maxArea;
    }

    static void Main() {
        int[] histogram = {2, 1, 5, 6, 2, 3};
        Console.WriteLine(LargestRectangleArea(histogram));
    }
}

A 8

B 12

C 10

D 6

💡 Hint

Think about the largest rectangle that can be formed by consecutive bars.

The largest rectangle area in the histogram {2,1,5,6,2,3} is 10, formed by bars with heights 5 and 6 (width 2).

❓ Predict Output

intermediate

Output for Uniform Height Histogram

What is the output of the largest rectangle area calculation for a histogram where all bars have the same height?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int LargestRectangleArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.Length) {
            if (stack.Count == 0 || heights[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;
        }
        return maxArea;
    }

    static void Main() {
        int[] histogram = {4, 4, 4, 4};
        Console.WriteLine(LargestRectangleArea(histogram));
    }
}

A 16

B 8

C 12

D 4

💡 Hint

All bars have the same height, so the largest rectangle covers all bars.

With all bars height 4 and count 4, the largest rectangle area is 4 * 4 = 16.

🔧 Debug

advanced

Identify the Runtime Error in Stack Usage

What runtime error will occur when running this modified largest rectangle code?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int LargestRectangleArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int 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);
                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;
            }
        }
        return maxArea;
    }

    static void Main() {
        int[] histogram = {2, 4};
        Console.WriteLine(LargestRectangleArea(histogram));
    }
}

A IndexOutOfRangeException

B No runtime error

C NullReferenceException

D InvalidOperationException

💡 Hint

Consider what happens when popping from an empty stack.

The code tries to pop from the stack without checking if it's empty, causing InvalidOperationException.

🧠 Conceptual

advanced

Why Use a Stack for Largest Rectangle in Histogram?

Why is a stack used in the algorithm to find the largest rectangle in a histogram?

A To keep track of indices of bars in increasing height order for efficient area calculation

B To store the heights of bars in sorted order for binary search

C To reverse the histogram array for easier processing

D To store all possible rectangle areas for later comparison

💡 Hint

Think about how the stack helps find boundaries for rectangles.

The stack keeps indices of bars in increasing height order, allowing quick calculation of rectangle widths when a smaller bar is found.

🚀 Application

expert

Largest Rectangle Area for Complex Histogram

Given the histogram heights {6, 2, 5, 4, 5, 1, 6}, what is the largest rectangle area calculated by the stack-based algorithm?

A 10

B 12

C 15

D 9

💡 Hint

Consider rectangles formed by bars 5,4,5 or 6,2,5,4.

The largest rectangle area is 12, formed by bars with heights 5,4,5 spanning width 3.

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