Minimum Area Rectangle

• Store all points in a HashSet for efficient O(1) average time lookups.
• Initialize minArea to Integer.MAX_VALUE.
• Use three nested loops to iterate through all unique triplets of points (p1, p2, p3).
• For each triplet, check if they can form a right-angled corner. For example, if p1 and p2 are aligned vertically (p1.x == p2.x) and p1 and p3 are aligned horizontally (p1.y == p3.y), they form a right angle at p1.
• If they do, the fourth point p4 would have coordinates (p3.x, p2.y).
• Check if p4 exists in the HashSet.
• If p4 exists, calculate the area abs((p1.x - p3.x) * (p1.y - p2.y)) and update minArea.
• This check must be performed for all three points in the triplet acting as the corner.
• After checking all triplets, if minArea is still Integer.MAX_VALUE, return 0. Otherwise, return minArea.

First, to allow for quick lookups, all the given points are stored in a HashSet. A point (x, y) can be stored as a string "x,y" or by encoding it into a single integer x * 40001 + y since coordinates are non-negative and y <= 40000. The algorithm then uses three nested loops to pick three distinct points, p1(x1, y1), p2(x2, y2), and p3(x3, y3). For each triplet, we check if they form a right-angled corner. For example, if p1 and p2 are aligned vertically (x1 == x2) and p1 and p3 are aligned horizontally (y1 == y3), then they form a right angle at p1. The fourth point required to complete the rectangle would be p4(x3, y2). We then check if p4 exists in our HashSet. If it does, we have found a valid rectangle. We calculate its area as |x1 - x3| * |y1 - y2| and update our minimum area found so far. This process is repeated for all possible triplets and all possible corner configurations within the triplet.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int minAreaRect(int[][] points) {6        Set<Integer> pointSet = new HashSet<>();7        for (int[] point : points) {8            pointSet.add(point[0] * 40001 + point[1]);9        }10 11        int minArea = Integer.MAX_VALUE;12        int n = points.length;13 14        for (int i = 0; i < n; i++) {15            for (int j = i + 1; j < n; j++) {16                for (int k = j + 1; k < n; k++) {17                    int[] p1 = points[i];18                    int[] p2 = points[j];19                    int[] p3 = points[k];20 21                    // Check all 3 possibilities for the corner point22                    minArea = Math.min(minArea, check(p1, p2, p3, pointSet));23                    minArea = Math.min(minArea, check(p2, p1, p3, pointSet));24                    minArea = Math.min(minArea, check(p3, p1, p2, pointSet));25                }26            }27        }28 29        return minArea == Integer.MAX_VALUE ? 0 : minArea;30    }31 32    private int check(int[] p1, int[] p2, int[] p3, Set<Integer> pointSet) {33        int x1 = p1[0], y1 = p1[1];34        int x2 = p2[0], y2 = p2[1];35        int x3 = p3[0], y3 = p3[1];36 37        // Check if p2 and p3 form a right angle at p138        if (x1 == x2 && y1 == y3) {39            // Fourth point is (x3, y2)40            if (pointSet.contains(x3 * 40001 + y2)) {41                return Math.abs(x1 - x3) * Math.abs(y1 - y2);42            }43        }44        return Integer.MAX_VALUE;45    }46}

• Create a Map<Integer, List<Integer>> called columns to group points by x-coordinate.
• Iterate through the input points and populate columns.
• Get the unique x-coordinates from columns.keySet() and sort them.
• Initialize minArea to Integer.MAX_VALUE and a Map<String, Integer> called lastX.
• Iterate through the sorted x-coordinates (x).
• For each x, get the list of y-coordinates yList and sort it.
• Use two nested loops to iterate through all pairs (y1, y2) in yList where y1 < y2.
• Create a key for the pair, e.g., String key = y1 + "," + y2;.
• If lastX contains key, retrieve the previous x-coordinate x_prev = lastX.get(key).
• Calculate the area (x - x_prev) * (y2 - y1) and update minArea.
• Update lastX with the current x: lastX.put(key, x).
• After the loops, if minArea is Integer.MAX_VALUE, return 0, else return minArea.

First, we process the input points and group them by their x-coordinate. A HashMap<Integer, List<Integer>> is a suitable data structure, mapping an x-coordinate to a list of y-coordinates present at that x. For each list of y-coordinates in the map, we sort it. This makes it easier to find pairs and compare them later. We then iterate through the unique x-coordinates in sorted order. For each x, we iterate through all pairs of y-coordinates (y1, y2) in its sorted list. This pair of points (x, y1) and (x, y2) forms a vertical line segment. To find a rectangle, we need to find another x-coordinate, x_prev, that also has points at y1 and y2. To do this efficiently, we use another HashMap<String, Integer>, let's call it lastX. This map will store the most recently seen x-coordinate for a given vertical edge defined by a pair (y1, y2). If we find a match in lastX, we've found a rectangle. By iterating x in sorted order, we ensure that (x - x_prev) is the smallest possible width for any rectangle ending at x with that specific vertical edge, which is key to finding the minimum area.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.HashMap;4import java.util.List;5import java.util.Map;6 7class Solution {8    public int minAreaRect(int[][] points) {9        Map<Integer, List<Integer>> columns = new HashMap<>();10        for (int[] p : points) {11            columns.computeIfAbsent(p[0], k -> new ArrayList<>()).add(p[1]);12        }13 14        List<Integer> xCoords = new ArrayList<>(columns.keySet());15        Collections.sort(xCoords);16 17        int minArea = Integer.MAX_VALUE;18        Map<String, Integer> lastX = new HashMap<>();19 20        for (int x : xCoords) {21            List<Integer> yList = columns.get(x);22            Collections.sort(yList);23            for (int i = 0; i < yList.size(); i++) {24                for (int j = i + 1; j < yList.size(); j++) {25                    int y1 = yList.get(i);26                    int y2 = yList.get(j);27                    String key = y1 + "," + y2;28                    if (lastX.containsKey(key)) {29                        int prevX = lastX.get(key);30                        int area = (x - prevX) * (y2 - y1);31                        minArea = Math.min(minArea, area);32                    }33                    lastX.put(key, x);34                }35            }36        }37 38        return minArea == Integer.MAX_VALUE ? 0 : minArea;39    }40}

• Create a HashSet to store all points for fast lookups. A point (x, y) can be encoded as a single integer or string.
• Populate the HashSet with all points from the input array.
• Initialize minArea to Integer.MAX_VALUE.
• Use a nested loop to iterate through all pairs of points p1(x1, y1) and p2(x2, y2).
• Inside the loop, if p1 and p2 are aligned (x1 == x2 or y1 == y2), skip to the next pair as they cannot form a diagonal.
• Check if the other two corners, (x1, y2) and (x2, y1), exist in the HashSet.
• If both points exist, calculate the area: area = Math.abs(x1 - x2) * Math.abs(y1 - y2).
• Update minArea = Math.min(minArea, area).
• After the loops complete, if minArea is still Integer.MAX_VALUE, return 0. Otherwise, return minArea.

The core idea is that any two diagonally opposite points (x1, y1) and (x2, y2) in a rectangle (with sides parallel to axes) uniquely define the other two points: (x1, y2) and (x2, y1). To implement this, we first need a way to quickly check for the existence of a point. A HashSet is perfect for this, providing average O(1) time complexity for lookups. We pre-populate the HashSet with all the points from the input array. To store a 2D point in a 1D set, we can encode it into a single integer (e.g., x * 40001 + y, since y <= 40000). The algorithm then uses two nested loops to iterate through every unique pair of points, p1 and p2. For each pair p1(x1, y1) and p2(x2, y2), we check if they can form a diagonal. This is true if they are not aligned horizontally or vertically, i.e., x1 != x2 and y1 != y2. If they form a potential diagonal, we construct the coordinates of the other two required points: p3(x1, y2) and p4(x2, y1). We then query our HashSet to see if both p3 and p4 exist. If both points are found, we have identified a rectangle and calculate its area, updating the minimum area found so far.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int minAreaRect(int[][] points) {6        Set<Integer> pointSet = new HashSet<>();7        for (int[] point : points) {8            // Encode point (x, y) into a single integer.9            // Since y <= 40000, we can use a multiplier of 40001.10            pointSet.add(point[0] * 40001 + point[1]);11        }12 13        int minArea = Integer.MAX_VALUE;14        int n = points.length;15 16        for (int i = 0; i < n; i++) {17            for (int j = i + 1; j < n; j++) {18                int[] p1 = points[i];19                int[] p2 = points[j];20                int x1 = p1[0], y1 = p1[1];21                int x2 = p2[0], y2 = p2[1];22 23                // Check if they can form a diagonal (not aligned)24                if (x1 == x2 || y1 == y2) {25                    continue;26                }27 28                // Check if the other two corners exist29                // p3 is (x1, y2) and p4 is (x2, y1)30                if (pointSet.contains(x1 * 40001 + y2) && pointSet.contains(x2 * 40001 + y1)) {31                    int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);32                    minArea = Math.min(minArea, area);33                }34            }35        }36 37        return minArea == Integer.MAX_VALUE ? 0 : minArea;38    }39}