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 under the skyline formed by these buildings.

🎯 Goal: Build a program that finds the largest rectangle area in a histogram using a stack.

📋 What You'll Learn

Create an array called heights with exact values: 2, 1, 5, 6, 2, 3

Create an integer variable n to store the number of buildings

Use a stack to help find the largest rectangle area

Calculate the largest rectangle area using the stack method

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 span problems, and land area calculations.

💼 Career

Understanding stack-based algorithms is important for software engineers working on performance-critical applications and technical interviews.

1

Create the histogram data

Create an integer array called heights with these exact values: 2, 1, 5, 6, 2, 3. Also create an integer variable n and set it to the number of elements in heights.

DSA C

# Create the array heights and variable n
# Your code here

Hint

Use sizeof to find the number of elements in the array.

2

Set up stack and variables

Create an integer array called stack with size n to use as a stack. Create integer variables top initialized to -1, max_area initialized to 0, and i initialized to 0.

DSA C

int heights[] = {2, 1, 5, 6, 2, 3};
int n = sizeof(heights) / sizeof(heights[0]);
// Create stack array and variables top, max_area, i
// Your code here

Hint

The stack is an array with size n. top keeps track of the last element index.

3

Calculate largest rectangle area using stack

Write a while loop that runs while i is less than n. Inside, if top is -1 or heights[i] is greater than or equal to heights[stack[top]], push i onto stack and increment i. Otherwise, pop from stack, calculate area with popped height, and update max_area if needed. After the loop, pop remaining elements from stack and update max_area similarly.

DSA C

int heights[] = {2, 1, 5, 6, 2, 3};
int n = sizeof(heights) / sizeof(heights[0]);
int stack[n];
int top = -1;
int max_area = 0;
int i = 0;
// Write the while loop to calculate max_area using stack
// Your code here

Hint

Use the stack to keep indexes of bars. Calculate area when current bar is smaller than top of stack.

4

Print the largest rectangle area

Write a printf statement to print the integer value of max_area.

DSA C

int heights[] = {2, 1, 5, 6, 2, 3};
int n = sizeof(heights) / sizeof(heights[0]);
int stack[n];
int top = -1;
int max_area = 0;
int i = 0;

while (i = heights[stack[top]]) {
        stack[++top] = i;
        i++;
    } else {
        int tp = stack[top--];
        int area = heights[tp] * (top == -1 ? i : i - stack[top] - 1);
        if (area > max_area) {
            max_area = area;
        }
    }
}

while (top != -1) {
    int tp = stack[top--];
    int area = heights[tp] * (top == -1 ? i : i - stack[top] - 1);
    if (area > max_area) {
        max_area = area;
    }
}
// Print max_area
// Your code here

Hint

Use printf("%d\n", max_area); to print the result.