Max Points on a Line LeetCode solution in C++

1
class Solution {
2
 public:
3
  // DP solution
4
  // TC-O(N*N)
5
  // SC- ~ O(N*N)
6
  // Custom Sort
7
  bool static cmp(vector<int> p1, vector<int> p2) {
8
    if (p1[0] == p2[0]) return p1[1] < p2[1];
9
    return p1[0] < p2[0];
10
  }
11

12
  // Slope Calculating
13
  float calcSlope(int x1, int y1, int x2, int y2) {
14
    return (y2 - y1) / (float)(x2 - x1);
15
  }
16
  int maxPoints(vector<vector<int>> &points) {
17
    if (points.size() == 2 || points.size() == 1) return points.size();
18

19
    sort(points.begin(), points.end(), cmp);
20
    int ans = 1;
21
    // How much points having same slope at current index
22
    vector<unordered_map<float, int>> dp(points.size() + 1);
23
    for (int i = 1; i < points.size(); i++) {
24
      for (int j = 0; j < i; j++) {
25
        float slope = calcSlope(points[j][0], points[j][1], points[i][0], points[i][1]);
26
        if (dp[j].find(slope) != dp[j].end()) {
27
          dp[i][slope] = 1 + dp[j][slope];
28
          ans = max(ans, dp[i][slope]);
29
        } else {
30
          dp[i][slope] += 1;
31
        }
32
      }
33
    }
34
    // return ans
35

36
    return ans + 1;
37
  }
38
};