84. Largest Rectangle in Histogram

Efficiently Solving the Largest Rectangle in Histogram Problem

In this post, we’ll explore an efficient solution to one of the classic problems in data structures—finding the largest rectangle in a histogram. This problem is particularly popular in coding interviews and is a great example of using stacks to solve complex problems in linear time.

Problem Statement

Given an array of integers where each element represents the height of a bar in a histogram, the goal is to find the area of the largest rectangle that can be formed using contiguous bars. The width of each bar is 1 unit.

For example, in the histogram represented by [2,1,5,6,2,3], the largest rectangle has an area of 10.

Approach

To solve this problem efficiently, we can use a stack-based approach. The idea is to preprocess two pieces of information for each bar:

  1. Next Smaller Element: The index of the first bar to the right that has a smaller height.
  2. Previous Smaller Element: The index of the first bar to the left that has a smaller height.

Once we have this information, we can easily compute the maximum rectangle area for each bar.

Solution Breakdown

Here is the Java code to implement this solution:

java 

class Solution {
    public int largestRectangleArea(int[] heights) {
        int size = heights.length;
        Stack<Integer> stack = new Stack();
        int[] nextSmall = new int[size];
        //calculating next small elements;
        stack.push(size - 1);
        nextSmall[size - 1] = size;
        for(int i = size - 2; i >= 0; i--) {
            while(stack.size() > 0 && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if(stack.size() == 0) {
                nextSmall[i] = size;
            }else {
                nextSmall[i] = stack.peek();
            }
            stack.push(i);
        }
        //claer the stack
        stack.clear();
        //calculate the previous small elements
        int[] prevSmall = new int[size];
        stack.push(0);
        prevSmall[0] = -1;
        for(int i = 1; i < size; i++) {
            while(stack.size() > 0 && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if(stack.size() == 0){
                prevSmall[i] = -1;
            }else {
                prevSmall[i] = stack.peek();
            }
            stack.push(i);
        }
        //claculating the area
        int max = -1;
        for(int i = 0; i < size; i++) {
            int area = heights[i] * (nextSmall[i] - prevSmall[i] - 1);
            max = Math.max(area, max);
        }
        return max;
    }
}

Step-by-Step Explanation

Let’s break down the logic behind the code:

  1. Next Smaller Element Calculation:

    • We iterate through the heights array in reverse order.
    • For each bar at index i, we check the top of the stack to find the next smaller bar. If the current bar is taller than the bar at the top of the stack, we pop the stack. Otherwise, we record the index of the next smaller bar.
    • If there is no smaller bar to the right, we set the index to size (i.e., beyond the last bar).

  2. Previous Smaller Element Calculation:

    • Now we clear the stack and process the array from left to right.
    • Similar to the previous step, for each bar, we find the first smaller bar on the left and record its index.
    • If no smaller bar exists, we set the index to -1.

  3. Calculating the Maximum Area:

    • For each bar at index i, the width of the rectangle it can form is calculated as:
      Width = nextSmall[i] - prevSmall[i] - 1
    • The area of the rectangle is simply the height of the bar multiplied by the width:
      Area = heights[i] * Width
    • We track the maximum area across all bars and return it as the result.

Time Complexity

  • Next Smaller Element: Each element is pushed and popped from the stack at most once, so this part takes O(n) time.
  • Previous Smaller Element: Similarly, this part also takes O(n) time.
  • Calculating the Area: This step is a simple linear pass through the array, which takes O(n) time.

Thus, the overall time complexity is O(n), making this solution highly efficient compared to a brute-force approach which would have taken O(n²) time.

Key Insights

  1. Stacks: The use of stacks helps efficiently compute the next and previous smaller elements.
  2. Optimality: By reducing the problem to linear time, we significantly improve performance for large histograms.
  3. Edge Cases: The code handles cases where there are no smaller elements on either side, ensuring the entire array is considered when needed.

Conclusion

The problem of finding the largest rectangle in a histogram is a great example of how a stack can be used to solve a seemingly complex problem in linear time. By breaking the problem into smaller subproblems (finding the next and previous smaller elements), we reduce the complexity and arrive at an optimal solution.

This approach is not only efficient but also highlights the importance of understanding data structures, particularly stacks, in solving real-world algorithmic problems.

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic 🚀 leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more