A variant of the classic 'Largest Rectangle in Histogram' problem, but instead of finding the largest rectangle under a histogram (which uses a min-based approach), the task is modified to find the maximum area rectangle.
A variant of the classic 'Largest Rectangle in Histogram' problem, but instead of finding the largest rectangle under a histogram (which uses a min-based approach), the task is modified to find the maximum area rectangle. Concretely: given a set of points or columns with y-values, enumerate pairs of x-coordinates, identify common y-values between those two columns, and compute the maximum rectangle area achievable. The problem is framed as finding the largest (not smallest) rectangle satisfying some geometric constraint among given coordinate data.
How would you handle the case where the rectangle does not need to be axis-parallel?
What if no interior points are allowed inside the chosen rectangle?
| Approach | Notes |
|---|---|
| Brute force column-pair scan | Check all y-values for every x-pair without a set; simpler to implement but slower due to lack of O(1) lookup for common y-values. |
Common mistakes: Getting stuck on how to efficiently find common y-values between two columns — one candidate mentioned spending extra time here before settling on a set-based solution.
Interviewer hints: The interviewer was 'pretty quiet throughout' while the candidate coded, only beginning discussion after the solution was complete.; The second follow-up (non-axis-parallel rectangle) explicitly does not require implementation — discussion of approach is sufficient.
What passers do: Enumerating pairs of x-coordinates, finding common y-values between the two columns (using a set for efficiency), then computing the area. The candidate who passed noted getting stuck briefly on efficient common-y lookup but resolved it with a set approach.