Largest Rectangle in Histogram Using Stack in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to push the current index onto the stack.

DSA C#

stack.[1](i);

Drag options to blanks, or click blank then click option'

APush

BPop

CPeek

DClear

Attempts:

3 left

💡 Hint

Common Mistakes

Using Pop instead of Push.

Using Peek which only reads the top element.

Using Clear which empties the stack.

We use stack.Push(i) to add the current index to the stack.

2fill in blank

medium

Complete the condition to check if the current bar is lower than the bar at the top of the stack.

DSA C#

while (stack.Count > 0 && heights[i] [1] heights[stack.Peek()])

Drag options to blanks, or click blank then click option'

A<

B>

C==

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' which is the opposite condition.

Using '==' which only checks equality.

Using '>=' which includes equal heights.

We compare if the current height is less than the height at the top index of the stack.

3fill in blank

hard

Fix the error in calculating the width when the stack is empty after popping.

DSA C#

int width = stack.Count == 0 ? [1] : i - stack.Peek() - 1;

Drag options to blanks, or click blank then click option'

Aheights[i]

Bi

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 which gives zero width.

Using 1 which is incorrect width.

Using heights[i] which is a height, not width.

If the stack is empty, the width is the current index i because the rectangle extends from 0 to i-1.

4fill in blank

hard

Fill both blanks to correctly update the max area after popping from the stack.

DSA C#

int height = heights[stack.[1]] ;
int width = stack.Count == 0 ? i : i - stack.[2] - 1;
maxArea = Math.Max(maxArea, height * width);

Drag options to blanks, or click blank then click option'

APop

BPeek

CCount

DClear

Attempts:

3 left

💡 Hint

Common Mistakes

Using Peek instead of Pop to get height.

Using Pop instead of Peek to get width index.

Using Count or Clear which are not correct here.

We pop the top index to get the height, then peek the new top to calculate width.

5fill in blank

hard

Fill all three blanks to complete the final loop that processes remaining bars in the stack.

DSA C#

while (stack.Count > 0) {
    int height = heights[stack.[1]];
    int width = stack.Count == 0 ? [2] : [3] - stack.Peek() - 1;
    maxArea = Math.Max(maxArea, height * width);
}

Drag options to blanks, or click blank then click option'

APop

Bheights.Length

Dstack.Count

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack.Count instead of heights.Length for width.

Using Peek instead of Pop for height.

Using wrong boundary values.

We pop the top index for height, use heights.Length as the right boundary for width calculation.

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