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 are given an integer array and need to determine if there exists a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force triple nested loops checking all triplets

B. Greedy approach scanning from left to right picking local minima and maxima

C. Using a monotonic stack to track potential '3' and '2' values while iterating backwards

D. Dynamic programming with prefix minimum and suffix maximum arrays

Solution

1. Step 1: Understand the 132 pattern condition

   The problem requires finding a subsequence i < j < k with nums[i] < nums[k] < nums[j], which is the 132 pattern.

2. Step 2: Identify the approach that achieves O(n) time

   The monotonic stack approach iterates from right to left, maintaining candidates for the '3' and '2' elements efficiently, achieving linear time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is known optimal for 132 pattern detection [OK]

Hint: Monotonic stack solves 132 pattern in O(n) [OK]

Common Mistakes:

• Thinking brute force is acceptable for large inputs
• Confusing greedy with monotonic stack
• Assuming DP is needed

2. You are given two arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, you want to find the first greater element to its right in nums2. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a monotonic stack to precompute the next greater element for all elements in nums2, then map results for nums1.

B. Use nested loops to check each element of nums1 against all elements to its right in nums2.

C. Use dynamic programming to store the next greater element for each index in nums2.

D. Sort nums2 and use binary search to find the next greater element for each element in nums1.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the next greater element for each element in nums1 based on their positions in nums2, which is a classic next greater element problem.

2. Step 2: Identify the optimal approach

   Using a monotonic stack to precompute next greater elements for all nums2 elements allows O(n) processing, then mapping results for nums1 is O(m), leading to an overall O(n + m) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is well-known for next greater element problems [OK]

Hint: Monotonic stack precomputes next greater efficiently [OK]

Common Mistakes:

• Using nested loops leads to O(m*n) time, too slow for large inputs
• Sorting nums2 loses original order, invalidating next greater logic
• Dynamic programming is not applicable here as no overlapping subproblems

3. Given the following code for the stock span problem, what is the return value of the third call to next with input prices [100, 80, 60]?

easy

A. 3

B. 2

C. 0

D. 1

Solution

1. Step 1: Trace the first two calls

   Call 1 with price=100: stack empty, span=1, stack=[0], prices=[100]. Call 2 with price=80: top price=100 > 80, no pop, span=2-0=1, stack=[0,1], prices=[100,80].

2. Step 2: Trace the third call with price=60

   Top price=80 > 60, no pop, span=3-1=1, stack=[0,1,2], prices=[100,80,60]. Return 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each price less than previous yields span 1 [OK]

Hint: Span resets to 1 when price is less than previous [OK]

Common Mistakes:

• Confusing index difference calculation
• Off-by-one errors in span computation

4. You are given a numeric string num and an integer k. The task is to remove exactly k digits from num to produce the smallest possible number. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Greedy algorithm using a monotonic increasing stack to remove digits that are greater than the next digit

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest lexicographically

C. Simple greedy approach removing the largest digits from left to right without considering order

D. Brute force generating all combinations of digits to remove and selecting the minimal result

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach that considers digit order.

2. Step 2: Identify the optimal approach

   Using a monotonic increasing stack allows removing digits that are larger than the next digit, ensuring the smallest possible number in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack greedily removes bigger digits before smaller ones [OK]

Common Mistakes:

• Assuming simple greedy removing largest digits left to right is optimal
• Thinking DP is needed for minimal number subsequence

5. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character might be compared multiple times during matching

B. O(n) because each character is processed once with constant-time stack operations

C. O(n log n) due to sorting or ordering operations on the stack

D. O(n) for time but O(n^2) for space due to stack growth in worst case

Solution

1. Step 1: Identify complexity of outer loop

   The algorithm iterates over each character exactly once, so the loop is O(n).

2. Step 2: Check stack operations

   Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant-time stack ops -> O(n) time [OK]

Hint: Each character processed once with O(1) stack ops [OK]

Common Mistakes:

• Confusing with brute force O(n^2) approach