The round is one problem with one graded follow-up and one spoken one, on the onsite coding round. Two reports. Both candidates recognized the shape of a known histogram problem and both note the twist: it asks for the largest rectangle, not the smallest, and it is a points problem, not a bars problem. The interviewer stays quiet until you finish.
You are given points as [x, y] pairs. Find the largest-area axis-parallel rectangle whose four corners are all given points. Return 0 if none exists.
Given — the function to write
def max_rectangle_area(points: list[list[int]]) -> int: ...
Part 1 — the largest rectangle
Map each x to the set of its y values. For every pair of columns, intersect the two sets; any two shared y values form a rectangle of width times height. One candidate stalled on finding the shared y values efficiently before reaching for a set, and passed.
Part 2 — no other point inside
Reported follow-up: no other given point may lie inside the rectangle. Clarify the border before coding: the report says "inside", but the LeetCode problem it was compared to also forbids points on the border. Reject a candidate rectangle if a point lies strictly between its columns and rows (and, under the stricter reading, on its edges).
Discussion — rectangles that are not axis-parallel. The second follow-up was talk only, no code: treat each ordered pair of points as one side, derive the other two corners, and look them up.
The reported wall — the intersection. The enumeration is obvious; how you find common y values between two columns is where the time went.
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.