Minimum Area Rectangle

Description

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.

 

Example 1:

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

Example 2:

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

 

Note:

1. 1 <= points.length <= 500
2. 0 <= points[i][0] <= 40000
3. 0 <= points[i][1] <= 40000
4. All points are distinct.

Solution(javascript)

/*
 * @lc app=leetcode id=939 lang=javascript
 *
 * [939] Minimum Area Rectangle
 */

// @lc code=start
/**
 * @param {number[][]} points
 * @return {number}
 */
const minAreaRect = function (points) {
  const map = points.reduce((acc, [x, y]) => {
    if (acc[x]) {
      acc[x].push(y)
    } else {
      acc[x] = [y]
    }
    return acc
  }, {})
  let min = Infinity
  for (const x1 of Object.keys(map)) {
    const ys = map[x1]
    for (let i = 0; i < ys.length; i++) {
      for (let j = i + 1; j < ys.length; j++) {
        for (const x2 of Object.keys(map)) {
          if (x1 !== x2) {
            if (map[x2].indexOf(ys[i]) > -1 && map[x2].indexOf(ys[j]) > -1) {
              min = Math.min(
                min,
                Math.abs(x2 - x1) * Math.abs(ys[i] - ys[j]),
              )
            }
          }
        }
      }
    }
  }
  return min === Infinity ? 0 : min
}
// @lc code=end