939. Minimum Area Rectangle

/**

 * 939. Minimum Area Rectangle

 * Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes. If there isn’t any rectangle, return 0.

*/

See the solution to the problem on github here.

https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/MinAreaRectangle.java

The problem uses a line sweep approach.

  1. You store the y coordinates in a tree map, key as X coordinate and value as list of Y coordinates
  2. You create a new map that which has key as pair of Y coordinates, and value as the X coordinate. This map is storing the right most X coordinate location so far seen for a given set of Y coordinates.
  3. You iterate from left to right the X axis (via using map in 1). This is line sweep.
  4. You get the list of Y coordinates on the given X coordinate and convert them to pairs. Then you see the last location of the pair in the map, created in step 2. If the pair exists in map you calculate area and update the new area to be the min area if it is as such.
  5. You update the map in 2, to set the X coordinate location of the Y coordinate pair as the current X coordinate
public int minAreaRect(int[][] points) {
    //group the coordinates into a collections of y coordinates per each X axis
    for (int[] point : points) {
        List<Integer> yCoordinates = coordinateMap.computeIfAbsent(point[0], (l) -> new ArrayList<>());
        yCoordinates.add(point[1]);
    }
    HashMap<Pair<Integer, Integer>, Integer> xyMap = new HashMap<>();
    //move across the X axis from left to right
    for (Map.Entry<Integer, List<Integer>> entry : coordinateMap.entrySet()) {
        ArrayList<Pair<Integer, Integer>> ySides = convertYCoordinatesToPairs(entry.getValue());
        for (Pair<Integer, Integer> pair : ySides) {
            //for each y1,y2 pair see if that pair was previously seen, if seen calculate the area and update
            //if its the minimum area
            Integer priorX = xyMap.get(pair);
            if (priorX != null) {
                int area = ((entry.getKey() - priorX) * (pair.second - pair.first));
                minArea = Math.min(minArea, area);
            }
            xyMap.put(pair, entry.getKey());
        }
    }
    if (minArea == Integer.MAX_VALUE) {
        return 0;
    }
    return minArea;
}