Formatted question description: https://leetcode.ca/all/939.html
939. Minimum Area Rectangle (Medium)
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 <= points.length <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000- All points are distinct.
Solution 1.
// OJ: https://leetcode.com/problems/transpose-matrix/
// Time: O(N^2logN)
// * each point is visited only once with another point -> O(N^2)
// * ys2.find(y) -> O(logN)
// Space: O(N)
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
int ans = INT_MAX;
unordered_map<int, set<int>> m;
for (auto &p : points) m[p[0]].insert(p[1]);
for (auto i = m.begin(); i != m.end(); ++i) {
auto &ys1 = i->second;
for (auto j = next(i); j != m.end(); ++j) {
auto &ys2 = j->second;
int xDist = abs(i->first - j->first);
int prevY = INT_MIN;
int minYDist = INT_MAX;
for (auto &y : ys1) {
if (ys2.find(y) == ys2.end()) continue;
if (prevY != INT_MIN) {
minYDist = min(minYDist, y - prevY);
}
prevY = y;
}
if (minYDist != INT_MAX) ans = min(ans, xDist * minYDist);
}
}
return ans == INT_MAX ? 0 : ans;
}
};
Java
class Solution {
public int minAreaRect(int[][] points) {
TreeMap<Integer, List<Integer>> treeMap = new TreeMap<Integer, List<Integer>>();
for (int[] point : points) {
int x = point[0], y = point[1];
List<Integer> list = treeMap.getOrDefault(x, new ArrayList<Integer>());
list.add(y);
treeMap.put(x, list);
}
int minArea = Integer.MAX_VALUE;
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
Set<Integer> xValuesSet = treeMap.keySet();
for (int x : xValuesSet) {
List<Integer> list = treeMap.get(x);
Collections.sort(list);
int size = list.size();
for (int i = 0; i < size; i++) {
int y1 = list.get(i);
for (int j = i + 1; j < size; j++) {
int y2 = list.get(j);
String positionKey = Arrays.toString(new int[]{y1, y2});
if (hashMap.containsKey(positionKey))
minArea = Math.min(minArea, (x - hashMap.get(positionKey)) * (y2 - y1));
hashMap.put(positionKey, x);
}
}
}
return minArea == Integer.MAX_VALUE ? 0 : minArea;
}
}