leetcode

commit 0c8e2ec74a058cda17f411e95566b38b5a837b9a
parent ab4fef867852ac6485004582246c8a653dd58862
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  8 Jan 2023 19:18:16 +0100

Daily problem

Diffstat:
A
Problems/0149.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/0149.cpp b/Problems/0149.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+    int maxPoints(vector<vector<int>>& points) {
+        int n = points.size();
+        if (n == 1) return 1;
+
+        int res = 2;
+        for (int i = 0; i < n; i++) {
+            unordered_map<double, int> um;
+            for (int j = 0; j < n; j++) {
+                if (j == i) continue;
+                um[atan2(points[j][1] - points[i][1], points[j][0] - points[i][0])]++;
+            }
+            for (auto [_, count] : um) res = max(res, count + 1);
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -83,6 +83,7 @@ for solving problems.
 |  0142  |   Medium   | [Linked List Cycle II](Problems/0142.cpp)                                                        |
 |  0144  |   Medium   | [Binary Tree Preorder Traversal](Problems/0144.cpp)                                              |
 |  0145  |    Easy    | [Binary Tree Postorder Traversal](Problems/0145.cpp)                                             |
+|  0149  |    Hard    | [Max Points on a Line](Problems/0149.cpp)                                                        |
 |  0150  |   Medium   | [Evaluate Reverse Polish Notation](Problems/0150.cpp)                                            |
 |  0151  |   Medium   | [Reverse Words in a String](Problems/0151.cpp)                                                   |
 |  0155  |   Medium   | [Min Stack](Problems/0155.cpp)                                                                   |