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 code that calculates the largest rectangle area in a histogram using a stack?

DSA C

int largestRectangleArea(int* heights, int heightsSize) {
    int maxArea = 0;
    int stack[heightsSize];
    int top = -1;
    int i = 0;
    while (i < heightsSize) {
        if (top == -1 || heights[i] >= heights[stack[top]]) {
            stack[++top] = i++;
        } else {
            int h = heights[stack[top--]];
            int width = top == -1 ? i : i - stack[top] - 1;
            int area = h * width;
            if (area > maxArea) maxArea = area;
        }
    }
    while (top != -1) {
        int h = heights[stack[top--]];
        int width = top == -1 ? i : i - stack[top] - 1;
        int area = h * width;
        if (area > maxArea) maxArea = area;
    }
    return maxArea;
}

int main() {
    int histogram[] = {2, 1, 5, 6, 2, 3};
    int size = sizeof(histogram) / sizeof(histogram[0]);
    int result = largestRectangleArea(histogram, size);
    printf("%d\n", result);
    return 0;
}

A 8

B 12

C 6

D 10

💡 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).

🧠 Conceptual

intermediate

Understanding Stack Usage in Histogram Problem

Why do we use a stack to solve the Largest Rectangle in Histogram problem efficiently?

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

B To sort the histogram bars by height before calculating areas

C To store the maximum area found so far

D To reverse the histogram array for easier processing

💡 Hint

Think about how the stack helps find the width of rectangles.

The stack stores indices of bars in increasing height order. When a smaller bar is found, it means the rectangle with the height of the popped bar ends there, allowing area calculation.

🔧 Debug

advanced

Identify the Error in Stack Implementation

What error will occur if we forget to check 'top == -1' before accessing 'stack[top]' in the largest rectangle code?

DSA C

if (heights[i] >= heights[stack[top]]) {
    stack[++top] = i++;
} else {
    int h = heights[stack[top--]];
    int width = i - stack[top] - 1; // Potential error here
    int area = h * width;
    if (area > maxArea) maxArea = area;
}

A The width calculation will always be zero

B The code will run correctly without any error

C Accessing stack[top] when top == -1 causes undefined behavior or crash

D The stack will overflow

💡 Hint

What happens if you access an array with a negative index?

If top is -1, accessing stack[top] is invalid and can cause a crash or undefined behavior.

❓ Predict Output

advanced

Output with All Bars of Same Height

What is the output of the largest rectangle area code when all histogram bars have the same height?

DSA C

int histogram[] = {4, 4, 4, 4, 4};
int size = sizeof(histogram) / sizeof(histogram[0]);
int result = largestRectangleArea(histogram, size);
printf("%d\n", result);

A 20

B 16

C 4

D 5

💡 Hint

Largest rectangle covers all bars since they have equal height.

All bars have height 4 and count 5, so largest rectangle area is 4 * 5 = 20.

🚀 Application

expert

Maximum Rectangle Area in a Binary Matrix Using Histogram Logic

Given a binary matrix, we convert each row into a histogram of heights of consecutive 1s. Which approach correctly applies the largest rectangle in histogram logic to find the maximum rectangle of 1s in the matrix?

A Sum all 1s in the matrix and multiply by the number of rows

B For each row, update heights array by adding 1 for 1s and resetting to 0 for 0s, then apply largest rectangle area function

C Apply largest rectangle area function only on the first row's histogram

D Count the maximum number of consecutive 1s in any column without using histogram logic

💡 Hint

Think about how each row builds on the previous row's histogram.

We build a histogram for each row by counting consecutive 1s vertically, then apply the largest rectangle in histogram algorithm to find max area.