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. Consider the following Python code implementing the optimal Alien Dictionary solution. Given the input words = ["wrt", "wrf", "er", "ett", "rftt"], what is the final output string returned by the function?

easy

A. "wrtef"

B. "wert"

C. "wertf"

D. "wretf"

Solution

1. Step 1: Build graph edges from adjacent words

   Edges: w->e (from "wrt" and "wrf"), e->r ("wrf" and "er"), r->t ("er" and "ett"), t->f ("ett" and "rftt")

2. Step 2: Perform topological sort using Kahn's algorithm

   Start with nodes with zero in-degree: w; order: w -> e -> r -> t -> f

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output "wertf" matches topological order from graph [OK]

Hint: Trace edges and zero in-degree queue carefully [OK]

Common Mistakes:

• Off-by-one in queue processing
• Ignoring some edges
• Returning partial order

2. Consider the following Python code implementing the optimal DP solution for the stock problem with k transactions. What is the final output when calling maxProfit(1, [1, 5, 2])?

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

print(maxProfit(1, [1, 5, 2]))

easy

A. 4

B. 5

C. 3

D. 1

Solution

1. Step 1: Trace dp for i=2 (price=2), t=1

   Initialize next_dp and curr_dp with zeros. At i=2, curr_dp[1][0] = max(-2 + next_dp[1][1], next_dp[1][0]) = max(-2 + 0, 0) = 0; curr_dp[1][1] = max(2 + next_dp[0][0], next_dp[1][1]) = max(2 + 0, 0) = 2.

2. Step 2: Trace dp for i=1 (price=5), t=1

   curr_dp[1][0] = max(-5 + next_dp[1][1], next_dp[1][0]) = max(-5 + 2, 0) = 0; curr_dp[1][1] = max(5 + next_dp[0][0], next_dp[1][1]) = max(5 + 0, 2) = 5.

3. Step 3: Trace dp for i=0 (price=1), t=1

   curr_dp[1][0] = max(-1 + next_dp[1][1], next_dp[1][0]) = max(-1 + 5, 0) = 4; curr_dp[1][1] = max(1 + next_dp[0][0], next_dp[1][1]) = max(1 + 0, 5) = 5.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Maximum profit with 1 transaction is buying at 1 and selling at 5 -> profit 4 [OK]

Hint: Trace dp arrays backward to find max profit [OK]

Common Mistakes:

• Confusing holding and not holding states
• Off-by-one errors in indexing transactions
• Misreading the final dp state to return

3. You are given an array nums and multiple queries, each query containing two integers x and m. For each query, you want to find the maximum XOR of x with any element in nums that is less than or equal to m. Which algorithmic approach guarantees an optimal solution for large inputs?

easy

A. Greedy approach selecting the largest element less than or equal to m for XOR

B. Brute force nested loops checking all pairs for each query

C. Dynamic programming with memoization over all possible XOR values

D. Sorting nums and queries, then using a bitwise trie with offline queries and two pointers

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; greedy fails because max element ≤ m does not guarantee max XOR.

2. Step 2: Identify optimal approach

   Sorting and offline queries allow incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting + trie + offline queries is known optimal [OK]

Hint: Offline queries + trie + sorting -> optimal [OK]

Common Mistakes:

• Assuming greedy max element ≤ m yields max XOR
• Trying DP over XOR values
• Using brute force for large inputs

4. Consider the following Python code implementing the optimal solution for the envelope nesting problem. Given the input [[5,4],[6,4],[6,7],[2,3]], what is the value of the tails list after processing all heights?

easy

A. [3, 4, 7]

B. [3, 4]

C. [2, 3, 4, 7]

D. [2, 3, 7]

Solution

1. Step 1: Sort envelopes and extract heights

   Sorted envelopes: [[2,3],[5,4],[6,7],[6,4]] -> heights = [3,4,7,4]

2. Step 2: Trace tails updates

   Insert 3 -> tails=[3]; Insert 4 -> tails=[3,4]; Insert 7 -> tails=[3,4,7]; Insert 4 replaces tails[1] -> tails=[3,4,7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final tails length is 3 with values [3,4,7] [OK]

Hint: Trace tails updates carefully with bisect_left [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Not replacing tails element on equal height
• Misordering envelopes before LIS

5. What is the time complexity of adding a number to the MedianFinder implemented with two balanced heaps (max-heap and min-heap) and lazy removal for extended use cases?

medium

A. O(n) per insertion due to heap rebalancing and pruning

B. O(log n) per insertion due to heap push/pop and pruning operations

C. O(1) per insertion because heaps are balanced incrementally

D. O(n log n) per insertion because of sorting delayed removals

Solution

1. Step 1: Analyze heap operations

   Insertion involves pushing into one heap (O(log n)) and possibly popping from the other heap (O(log n)) to rebalance.

2. Step 2: Consider lazy removal pruning

   Pruning removes delayed elements lazily, each removal is O(log n), but amortized over many operations remains O(log n) per insertion.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap push/pop and pruning dominate, each O(log n) [OK]

Hint: Heap push/pop and pruning dominate, O(log n) per insertion [OK]

Common Mistakes:

• Assuming O(1) insertion ignoring heap operations
• Confusing pruning cost as O(n)
• Thinking sorting is needed each insertion