Maximum Rectangle from Coordinates | DSA Interview Patterns - Study Chapter | QuizMaker

Course

DSA Interview Patterns Roadmap

Topic

Company Asked Variants

Learning Outcome

Turn the Maximum Rectangle from Coordinates interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

Given points, find the maximum-area rectangle, including tilted rectangles.

Examples

Brute Force Approach

Check every quadruple and test rectangle properties.

Optimized Approach

Two diagonals of a rectangle share the same midpoint and length. Group point pairs by midpoint and squared length; combine pairs in each group.

Exact Pseudocode

for every pair of points:
  key = midpoint sum and dist2
  for previous pair with same key:
    area = abs(cross(p1-p3, p2-p3))
  add pair to group

Reference Code

from collections import defaultdict

def max_rectangle_area(points):
    groups = defaultdict(list)
    best = 0
    for i in range(len(points)):
        x1, y1 = points[i]
        for j in range(i + 1, len(points)):
            x2, y2 = points[j]
            key = (x1 + x2, y1 + y2, (x1 - x2) ** 2 + (y1 - y2) ** 2)
            for a, b in groups[key]:
                x3, y3 = points[a]
                x4, y4 = points[b]
                area2 = abs((x1 - x3) * (y2 - y3) - (y1 - y3) * (x2 - x3))
                best = max(best, area2)
            groups[key].append((i, j))
    return best

long long maxRectangleArea(vector<pair<int,int>>& points) {
    map<tuple<int,int,long long>, vector<pair<int,int>>> groups;
    long long best = 0;
    for (int i = 0; i < points.size(); i++) {
        auto [x1, y1] = points[i];
        for (int j = i + 1; j < points.size(); j++) {
            auto [x2, y2] = points[j];
            long long d2 = 1LL * (x1 - x2) * (x1 - x2) + 1LL * (y1 - y2) * (y1 - y2);
            auto key = make_tuple(x1 + x2, y1 + y2, d2);
            for (auto [a, b] : groups[key]) {
                auto [x3, y3] = points[a];
                long long area2 = llabs(1LL * (x1 - x3) * (y2 - y3) - 1LL * (y1 - y3) * (x2 - x3));
                best = max(best, area2);
            }
            groups[key].push_back({i, j});
        }
    }
    return best;
}

public static long maxRectangleArea(int[][] points) {
    Map<String, List<int[]>> groups = new HashMap<>();
    long best = 0;
    for (int i = 0; i < points.length; i++) {
        int x1 = points[i][0], y1 = points[i][1];
        for (int j = i + 1; j < points.length; j++) {
            int x2 = points[j][0], y2 = points[j][1];
            long d2 = 1L * (x1 - x2) * (x1 - x2) + 1L * (y1 - y2) * (y1 - y2);
            String key = (x1 + x2) + "#" + (y1 + y2) + "#" + d2;
            List<int[]> list = groups.computeIfAbsent(key, k -> new ArrayList<>());
            for (int[] pair : list) {
                int x3 = points[pair[0]][0], y3 = points[pair[0]][1];
                long area2 = Math.abs(1L * (x1 - x3) * (y2 - y3) - 1L * (y1 - y3) * (x2 - x3));
                best = Math.max(best, area2);
            }
            list.add(new int[]{i, j});
        }
    }
    return best;
}

Complexity

Edge Cases

• Duplicate points
• Axis-aligned rectangle
• Tilted rectangle
• Zero area

Follow-ups

• Minimum area rectangle
• Return coordinates

Nearest Practice References

• Minimum Area Rectangle II
• Valid Square

Common Mistakes

• Copying the nearest LeetCode solution without checking the changed rule.
• Skipping duplicate or boundary cases.
• Not stating the brute force before the optimized approach.

Tags

• dsa
• coding interview
• java
• c++
• python
• no-js
• company-asked-variants