leetcode

commit c6f24b3b5331f4f026500d8df3100869b97c331a
parent a368c17075901e48b1497d86737b00da31a8c11d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 23 Mar 2024 12:01:58 +0000

1 Random Problem

Diffstat:
A
Problems/0939.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/0939.cpp b/Problems/0939.cpp
@@ -0,0 +1,23 @@
+class Solution {
+    static int hash(int x, int y) { return 40000 * x + y; }
+
+  public:
+    int minAreaRect(const vector<vector<int>> &points) const {
+        const int n = size(points);
+        unordered_set<int> us;
+        int res = INT_MAX;
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < i; j++) {
+                const int x1 = points[i][0], y1 = points[i][1];
+                const int x2 = points[j][0], y2 = points[j][1];
+                if (us.count(hash(x1, y2)) && us.count(hash(x2, y1))) {
+                    res = min(res, abs(x1 - x2) * abs(y2 - y1));
+                }
+            }
+            us.insert(hash(points[i][0], points[i][1]));
+        }
+
+        return res != INT_MAX ? res : 0;
+    }
+};
diff --git a/README.md b/README.md
@@ -552,6 +552,7 @@ for solving problems.
 |  0935  |   Medium   | [Knight Dialer](Problems/0935.cpp)                                                                 |
 |  0937  |   Medium   | [Reorder Data in Log Files](Problems/0937.cpp)                                                     |
 |  0938  |    Easy    | [Range Sum of BST](Problems/0938.cpp)                                                              |
+|  0939  |   Medium   | [Minimum Area Rectangle](Problems/0939.cpp)                                                        |
 |  0941  |    Easy    | [Valid Mountain Array](Problems/0941.cpp)                                                          |
 |  0944  |    Easy    | [Delete Columns to Make Sorted](Problems/0944.cpp)                                                 |
 |  0946  |   Medium   | [Validate Stack Sequences](Problems/0946.cpp)                                                      |