Minimum Area Rectangle LeetCode solution in Java

1
class Solution {
2
  public int minAreaRect(int[][] points) {
3
    HashMap<Integer, Set<Integer>> hm = new HashMap<>();
4
    int area = Integer.MAX_VALUE;
5

6
    for (int[] point : points) {
7
      if (!hm.containsKey(point[0])) hm.put(point[0], new HashSet());
8
      hm.get(point[0])
9
          .add(point[1]); // x-coordinate already exits, just add the y-coordinate to the set
10
    }
11

12
    for (int i = 0; i < points.length - 1; i++) {
13
      for (int j = i + 1; j < points.length; j++) {
14
        int x1 = points[i][0],
15
            x2 = points[j][0],
16
            y1 = points[i][1],
17
            y2 = points[j][1]; // this step reduced the time from 368ms to 186ms
18
        if (x1 != x2 && y1 != y2) // diagonal is not parallel to x or y axis
19
        {
20
          if (area
21
              > Math.abs(
22
                  (x2 - x1)
23
                      * (y2 - y1))) // pre-calulate the area to avoid unecessary lookup. This step
24
          // reduced the time from 186ms to 57ms.
25
          {
26
            if (hm.get(x1).contains(y2)
27
                && hm.get(x2).contains(y1)) // learnt from other leetcoders. Thank you.
28
            area = Math.abs((x2 - x1) * (y2 - y1));
29
          }
30
        }
31
      }
32
    }
33

34
    return area < Integer.MAX_VALUE ? area : 0;
35
  }
36
}