Largest Rectangle in Histogram

📋

Largest Rectangle in Histogram

Edge cases:

</>

IDE

def largestRectangleArea(heights: list[int]) -> int:public int largestRectangleArea(int[] heights)int largestRectangleArea(vector<int>& heights)function largestRectangleArea(heights)

def largestRectangleArea(heights):
    # Write your solution here
    pass

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    // Write your solution here
    return 0;
}

function largestRectangleArea(heights) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty input due to missing or incorrect base case handling.✅ Add check to return 0 only if input array is empty; otherwise compute max area.

Wrong: 5Incorrectly calculating area by only considering single bars, ignoring wider rectangles.✅ Implement stack to find next smaller bars on both sides to calculate width properly.

Wrong: 8Failing to pop all bars after iteration, missing larger rectangles at the end.✅ After processing all bars, pop remaining bars from stack and calculate areas.

Wrong: 6Incorrect width calculation when bars have equal heights, popping too early.✅ Pop bars only when current height is strictly less than top of stack height.

Wrong: TLEUsing brute force O(n^2) nested loops approach on large input.✅ Use monotonic stack approach with O(n) time complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Review stack operations and boundary conditions to handle tricky sequences.

Optimize your solution to O(n) time using a monotonic stack to pass performance tests.

t1_01basic

Input{"heights":[2,1,5,6,2,3]}

Expected10

⏱ Performance - must finish in 2000ms

The largest rectangle has area 10 (bars with heights 5 and 6, width 2).

💡 Consider using a stack to track bars and their indices.

💡 Find the next smaller bar to the left and right for each bar to determine width.

💡 Calculate area as height * width using indices from the stack.

Why it failed: Incorrect output means the algorithm likely failed to correctly find the next smaller bars or compute widths. Fix by properly maintaining a monotonic stack and calculating areas when popping.

✓ Correctly computes largest rectangle area using stack-based approach.

t1_02basic

Input{"heights":[2,4,2,1]}

Expected6

⏱ Performance - must finish in 2000ms

Largest rectangle is height 2 spanning indices 0 to 2 (width 3), area 6.

💡 Check how the stack handles bars of equal or greater height.

💡 Ensure popping from stack when current bar is lower than top of stack.

💡 Calculate area using popped bar height and width between current index and stack top.

Why it failed: Wrong output indicates failure to handle bars with equal heights or incorrect width calculation. Fix by popping all bars taller than current and computing areas correctly.

✓ Handles varying heights and computes max area correctly.

t2_01edge

Input{"heights":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty histogram has no bars, so max area is 0.

💡 Check how your code handles empty input arrays.

💡 Make sure to return 0 when no bars are present.

💡 Add a base case for empty input before processing.

Why it failed: Code crashes or returns non-zero means no empty input check. Fix by returning 0 if heights is empty.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"heights":[7]}

Expected7

⏱ Performance - must finish in 2000ms

Single bar's height is the largest rectangle area.

💡 Test with only one bar to verify base case handling.

💡 Ensure code returns the bar height when only one element exists.

💡 No stack operations needed for single element, just return height.

Why it failed: Incorrect output means failure to handle single element arrays. Fix by returning heights[0] if length is 1.

✓ Correctly handles single bar input.

t2_03edge

Input{"heights":[2,2,2,2,2]}

Expected10

⏱ Performance - must finish in 2000ms

All bars same height 2, largest rectangle covers all bars: 2 * 5 = 10.

💡 Check if your stack handles equal height bars correctly.

💡 Ensure the width calculation includes all bars when heights are equal.

💡 Pop bars only when current bar is strictly less than top of stack height.

Why it failed: Wrong output means stack logic fails on equal heights, possibly popping too early. Fix by popping only when current height < top of stack height.

✓ Correctly computes area when all bars have equal height.

t2_04edge

Input{"heights":[0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All bars have zero height, so largest rectangle area is 0.

💡 Check how zero height bars affect area calculation.

💡 Ensure zero height bars do not cause incorrect width calculations.

💡 Return 0 if all bars are zero height.

Why it failed: Incorrect output means zero height bars are not handled properly. Fix by treating zero height bars as boundaries.

✓ Correctly returns 0 when all bars are zero height.

t3_01corner

Input{"heights":[1,2,3,4,5]}

Expected9

⏱ Performance - must finish in 2000ms

Strictly increasing heights; largest rectangle is bars 3,4,5 (height 3, width 3) area 9.

💡 Test how your stack handles strictly increasing sequences.

💡 Make sure to pop all remaining bars after iteration ends.

💡 Calculate area for each popped bar using correct width.

Why it failed: Incorrect output means failure to pop remaining bars after iteration. Fix by popping all bars in stack after processing input.

✓ Correctly handles strictly increasing heights and final stack cleanup.

t3_02corner

Input{"heights":[5,4,3,2,1]}

Expected9

⏱ Performance - must finish in 2000ms

Strictly decreasing heights; largest rectangle is bars 0,1,2 (height 3, width 3) area 9.

💡 Test how your stack handles strictly decreasing sequences.

💡 Ensure bars are popped when current bar is lower than stack top.

💡 Calculate area correctly using indices of popped bars.

Why it failed: Wrong output means failure to pop bars on decreasing heights or incorrect width calculation. Fix by popping bars while current height < stack top height.

✓ Correctly handles strictly decreasing heights.

t3_03corner

Input{"heights":[2,1,2,1,2]}

Expected5

⏱ Performance - must finish in 2000ms

Alternating heights; largest rectangle is bars 1 to 4 with height 1 (width 4), area 5 is incorrect, correct largest rectangle is 5 (bars 0 to 0 or 2 to 2 or 4 to 4 height 2 width 1 area 2, or bars 1 to 3 height 1 width 3 area 3, but actually largest rectangle is 3). Recalculated largest rectangle is 3 (single bar height 2 or two bars height 1).

💡 Check if your algorithm handles multiple local minima correctly.

💡 Verify stack pops and area calculations for repeated smaller bars.

💡 Calculate area for each popped bar with correct width boundaries.

Why it failed: Incorrect output means failure to handle multiple local minima or incorrect width calculation. Fix by correctly updating left boundaries when popping bars.

✓ Correctly handles alternating heights and local minima.

t4_01performance

Input{"heights":[1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 with all bars height 1,000,000 to test O(n) stack solution performance within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use a stack-based O(n) solution to pass performance constraints.

💡 Avoid nested loops; process each bar once with stack.

Why it failed: TLE indicates use of brute force O(n^2) approach. Fix by implementing O(n) stack-based algorithm.

✓ Algorithm runs in O(n) time confirming efficient complexity.

Practice

1. You need to evaluate a string expression containing non-negative integers and the operators +, -, *, and /, without any parentheses. The expression must respect operator precedence (multiplication and division before addition and subtraction). Which approach guarantees correct evaluation of such expressions?

easy

A. Use a stack to immediately evaluate multiplication and division, then sum the results for addition and subtraction.

B. Evaluate the expression strictly from left to right, ignoring operator precedence.

C. Use dynamic programming to store intermediate results for all subexpressions.

D. Sort the operators by precedence and evaluate all operators of the same precedence level in separate passes.

Solution

1. Step 1: Understand operator precedence

   Multiplication and division must be evaluated before addition and subtraction to get the correct result.

2. Step 2: Recognize stack-based immediate evaluation

   Using a stack to immediately compute * and / while postponing + and - ensures correct precedence without complex parsing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack-based immediate evaluation is the classic pattern for this problem [OK]

Hint: Stack handles precedence by immediate * and / evaluation [OK]

Common Mistakes:

• Ignoring operator precedence
• Trying to evaluate left to right
• Using DP unnecessarily

2. You are given a stream of daily stock prices. For each new price, you must find how many consecutive previous days (including today) had prices less than or equal to the current price. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Using a monotonic stack that stores indices and precomputed spans to skip redundant checks

B. Greedy approach selecting the maximum price seen so far without backtracking

C. Dynamic programming with memoization of maximum spans for subproblems

D. Brute force nested loops checking all previous days for each price

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding the span of consecutive days with prices less than or equal to the current price, which suggests a need to efficiently skip over previous days that are dominated by the current price.

2. Step 2: Identify the optimal approach

   A monotonic stack storing indices allows popping all previous days with prices less or equal to the current price in O(1) amortized time per element, enabling O(n) total time. This approach precomputes spans by using index differences, avoiding nested loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known to solve stock span in linear time [OK]

Hint: Monotonic stack skips redundant comparisons efficiently [OK]

Common Mistakes:

• Assuming greedy or DP solves this optimally
• Using nested loops for each price

3. What is the time complexity of the optimal monotonic stack solution that uses an explicit circular array copy (doubling the array) for the Next Greater Element II problem, and why?

medium

A. O(n) because each element is pushed and popped at most once despite doubling

B. O(n²) because the doubled array doubles the iterations

C. O(n log n) due to sorting implicit in stack operations

D. O(2n) which simplifies to O(n) but requires extra space

Solution

1. Step 1: Identify loop iterations

   The loop runs over doubled array of length 2n, so 2n iterations.

2. Step 2: Analyze stack operations

   Each element index is pushed once and popped once at most, so total stack operations are O(n). The doubling does not cause repeated pushes for the same index.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubling array length does not multiply complexity beyond linear [OK]

Hint: Each element pushed/popped once -> O(n) despite doubled array [OK]

Common Mistakes:

• Assuming doubling array doubles complexity to O(n²)
• Confusing stack operations with sorting complexity
• Ignoring that indices are pushed only once

4. The following code attempts to solve the Next Greater Element II problem using a monotonic stack and explicit circular array copy. Identify the line containing the subtle bug that causes incorrect results on some inputs.

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    doubled = nums + nums
    answer = [-1] * n
    stack = []
    for i, num in enumerate(doubled):
        while stack and doubled[stack[-1]] < num:
            idx = stack.pop()
            if idx < n:
                answer[idx] = num
        if i < n:
            stack.append(i)  # Bug here
    return answer

medium

A. Line pushing indices onto stack only when i < n

B. Line popping from stack while top element is less than current num

C. Line initializing answer array with -1

D. Line creating doubled array by concatenation

Solution

1. Step 1: Understand stack push condition

   Only pushing indices when i < n means indices from second pass (i ≥ n) are never pushed, so some elements' next greater values are missed.

2. Step 2: Identify correct push strategy

   To simulate circular array correctly, indices should be pushed for the entire doubled array, or a different approach used. Restricting push to i < n causes missing updates.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug is in restricting stack pushes to first pass only [OK]

Hint: Pushing indices only in first pass misses circular wrap [OK]

Common Mistakes:

• Not pushing indices in second pass causing incomplete updates
• Using values instead of indices in stack
• Not initializing answer array with -1

5. What is the time complexity of the optimal Remove K Digits algorithm using a monotonic stack on an input string of length n?

medium

A. O(n * k), because each digit can be popped up to k times

B. O(n), because each digit is pushed and popped at most once

C. O(n log n), due to sorting or priority queue operations inside the stack

D. O(n^2), because nested loops remove digits repeatedly

Solution

1. Step 1: Analyze push and pop operations

   Each digit is pushed exactly once onto the stack. Each digit can be popped at most once when a smaller digit arrives.

2. Step 2: Conclude overall complexity

   Since each digit is pushed and popped at most once, total operations are O(n), linear in input size.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack ensures linear time by amortized analysis [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Thinking sorting or nested loops are involved