939. Minimum Area Rectangle (Medium)

https://leetcode.com/problems/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.

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Solutions

class Solution {
    public int minAreaRect(int[][] points) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] p : points) {
            if (!map.containsKey(p[0])) {
                map.put(p[0], new HashSet<>());
            }

            map.get(p[0]).add(p[1]);
        }

        int min = Integer.MAX_VALUE;

        // since four edges are either parallel to x or axis, we can form a rectangle
        // with two diagonal points, then the rest 2 points are determined. The followup
        // operation is to check out whether both points are present in the set.

        // following method adopts a brute-force way
        for (int[] p1 : points) {
            for (int[] p2 : points) {
                // the link line of two points are not parallel to neither x or y axis
                if (p1[0] == p2[0] || p1[1] == p2[1]) {
                    continue;
                }

                // make sure that other two points also exists in the set
                // absence of either will not do
                if (!map.get(p1[0]).contains(p2[1]) || !map.get(p2[0]).contains(p1[1])) {
                    continue;
                }

                // compute the minimum area and substitute the old one if the new is smaller
                int area = Math.abs(p1[0] - p2[0]) * Math.abs(p1[1] - p2[1]);
                min = Math.min(min, area);
            }
        }

        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

Incorrect Solutions

References