Largest Rectangle in Histogram Using Stack in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Largest Rectangle Calculation

What is the output of the following Java code that calculates the largest rectangle area in a histogram using a stack?

DSA Java

import java.util.Stack;

public class Histogram {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.length) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, heights[top] * width);
            }
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, heights[top] * width);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] histogram = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(histogram));
    }
}

A 10

B 12

C 8

D 9

💡 Hint

Think about the largest rectangle that can be formed by consecutive bars in the histogram.

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 reverse the histogram array before processing

C To store the heights of bars directly for sorting later

D To count the total number of bars in the histogram

💡 Hint

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

The stack stores indices of bars in increasing height order, allowing quick calculation of rectangle widths when a smaller bar is encountered.

🔧 Debug

advanced

Identify the Error in Stack Implementation

What error will occur if we replace 'stack.peek()' with 'stack.pop()' inside the width calculation in the code below? while (!stack.isEmpty()) { int top = stack.pop(); int width = stack.isEmpty() ? i : i - stack.peek() - 1; maxArea = Math.max(maxArea, heights[top] * width); }

A Runtime error due to popping twice causing incorrect width calculation

B Logical error but no runtime error

C Syntax error because pop() cannot be used in expression

D No error, code works correctly

💡 Hint

Consider what happens if you remove elements from the stack multiple times unintentionally.

Using pop() instead of peek() removes an extra element from the stack, causing incorrect width calculation.

❓ Predict Output

advanced

Output with All Bars of Equal Height

What is the output of the largest rectangle area for the histogram with all bars of height 4: {4, 4, 4, 4}?

DSA Java

import java.util.Stack;

public class HistogramEqual {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.length) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, heights[top] * width);
            }
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, heights[top] * width);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] histogram = {4, 4, 4, 4};
        System.out.println(largestRectangleArea(histogram));
    }
}

A 4

B 12

C 8

D 16

💡 Hint

All bars have the same height, so the largest rectangle covers all bars.

The largest rectangle covers all 4 bars with height 4, area = 4 * 4 = 16.

🚀 Application

expert

Maximum Rectangle Area in a Binary Matrix Using Histogram Logic

Given a binary matrix, we can find the largest rectangle of 1s by treating each row as a histogram and applying the largest rectangle in histogram algorithm. Which step is NOT part of this approach?

A Convert each row into a histogram by accumulating heights of consecutive 1s from previous rows

B Apply the largest rectangle in histogram algorithm to each row's histogram

C Reset the histogram heights to zero after processing each row

D Keep track of the maximum area found across all rows

💡 Hint

Think about how histogram heights are updated row by row.

We do NOT reset histogram heights to zero after each row; instead, we accumulate heights of consecutive 1s to build histograms.

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 sort the histogram bars by height

C. To store the maximum area found so far

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand the role of the stack

   The stack stores indices of bars in increasing height order to efficiently find boundaries for rectangles.

2. Step 2: Why increasing order is important

   When a lower height bar is found, it signals the end of rectangles for taller bars, allowing area calculation.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option A

4. Quick Check:

   Stack tracks increasing bars = To keep track of bars' indices with increasing heights [OK]

Hint: Stack stores indices of increasing heights for area calculation [OK]

Common Mistakes:

• Thinking stack sorts bars by height
• Using stack to store areas directly
• Ignoring the order of bars in stack

2. Which of the following Java code snippets correctly initializes an empty stack to store integers for the histogram problem?

easy

A. Stack<Integer> stack = new Stack<int>();

B. Stack stack = new Stack<int>();

C. Stack<int> stack = new Stack<>();

D. Stack<Integer> stack = new Stack<>();

Solution

1. Step 1: Identify correct generic syntax in Java

   Java uses generics with angle brackets and wrapper classes like Integer, not primitive int.

2. Step 2: Check each option

   Stack<Integer> stack = new Stack<>(); uses Stack<Integer> stack = new Stack<>(); which is correct syntax for an empty integer stack.

3. Final Answer:

   Stack<Integer> stack = new Stack<>(); -> Option D

4. Quick Check:

   Correct generic syntax = Stack<Integer> stack = new Stack<>(); [OK]

Hint: Use wrapper class Integer with generics and diamond operator [OK]

Common Mistakes:

• Using primitive int in generics
• Missing diamond operator <>
• Not specifying generic type

3. What is the output of the following Java code snippet that calculates the largest rectangle area in histogram heights = {2, 1, 5, 6, 2, 3}?

public class Histogram {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, i = 0;
        while (i < heights.length) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, area);
            }
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(heights));
    }
}

medium

A. 12

B. 10

C. 8

D. 6

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 value

   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 of heights[top] * width during stack pops [OK]

Common Mistakes:

• Miscomputing width when stack is empty
• Not popping all remaining bars after loop
• Confusing indices with heights

4. Identify the bug in the following Java method for Largest Rectangle in Histogram and select the fix:

public static int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0, i = 0;
    while (i < heights.length) {
        if (stack.isEmpty() || heights[i] > heights[stack.peek()]) {
            stack.push(i++);
        } else {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }
    }
    while (!stack.isEmpty()) {
        int top = stack.pop();
        int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

medium

A. Initialize maxArea to Integer.MIN_VALUE instead of 0

B. Replace stack with a queue for correct order

C. Change '>' to '>=' in the if condition to handle equal heights

D. Remove the second while loop to avoid double counting

Solution

1. Step 1: Analyze the if condition in the main loop

   The condition uses '>' which skips pushing bars of equal height, causing incorrect area calculation.

2. Step 2: Fix by changing '>' to '>='

   Using '>=' ensures bars of equal height are pushed, maintaining correct stack order and area calculation.

3. Final Answer:

   Change '>' to '>=' in the if condition to handle equal heights -> Option C

4. Quick Check:

   Use '>=' to handle equal heights correctly [OK]

Hint: Use '>=' to push equal height bars to stack [OK]

Common Mistakes:

• Using '>' causes missing equal height bars
• Removing second loop causes incomplete area calculation
• Using queue breaks LIFO needed for stack

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 as smallest bar.

2. Step 2: Calculate largest area for given heights

   For {6,2,5,4,5,1,6}, largest rectangle area is 15 (bars at indices 0 and 6 with height 6 and width 1, or bars 2,3,4 with height 4 and width 3, but max is 15 from bars 0 to 0 or 6 to 6 or combined area 15 from bars 2,3,4 with height 5 and width 3).

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Stack helps find max area = 15 [OK]

Hint: Stack pops calculate max area using height * width [OK]

Common Mistakes:

• Not popping all bars after iteration
• Incorrect width calculation when stack is empty
• Ignoring bars with same height