Largest Rectangle in Histogram - C Solution

1. Introduction

This blog post explores a complex problem in C programming related to histograms: finding the largest rectangle in a histogram. This problem is significant in various fields, including computer graphics, statistical analysis, and data visualization, and it challenges one's understanding of data structures and algorithms.

Problem

Given an array of integers 'heights' representing the heights of bars in a histogram where each bar has a width of 1, the task is to find the area of the largest rectangle that can be formed within the histogram.

2. Solution Steps

1. Use a stack to store indices of bars.

2. Traverse the array and for each bar, do the following:

- While the stack is not empty and the current bar's height is less than the height of the bar at the top of the stack, pop from the stack and calculate the area.

- Push the current index onto the stack.

3. After traversing, calculate the area for remaining bars in the stack.

4. Return the maximum area found.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Function to find the largest rectangle in a histogram
int largestRectangleArea(int* heights, int heightsSize) {
    int *stack = (int *)malloc(sizeof(int) * heightsSize);
    int top = -1;
    int maxArea = 0;

    for (int i = 0; i <= heightsSize; i++) {
        while (top != -1 && (i == heightsSize || heights[stack[top]] >= heights[i])) {
            int height = heights[stack[top--]];
            int width = (top == -1) ? i : i - stack[top] - 1;
            maxArea = (height * width > maxArea) ? height * width : maxArea;
        }
        stack[++top] = i;
    }

    free(stack);
    return maxArea;
}

// Main function to demonstrate largestRectangleArea function
int main() {
    int heights[] = {2, 1, 5, 6, 2, 3}; // Example histogram heights
    int heightsSize = sizeof(heights) / sizeof(heights[0]);

    int result = largestRectangleArea(heights, heightsSize); // Call the function
    printf("Output: %d\n", result); // Print the result

    return 0;
}

Output:

10

Explanation:

The program calculates the area of the largest rectangle in a histogram given by heights [2, 1, 5, 6, 2, 3]. It uses a stack to efficiently find the next smaller bar for each bar in the histogram. 

When a smaller bar is found, the program calculates the area of the rectangle with the bar at the top of the stack as height and updates the maximum area. 

In the given histogram, the largest rectangle has an area of 10 (formed by bars with heights 5 and 6 and width 2), so the output is 10. 

This approach is efficient and optimizes the calculation by reducing the need for nested loops.