Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 8

Description

Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Solution

class Solution {
public:
  int maxPoints(vector<vector<int>>& points) {
    int len = points.size();
    if(len < 3) return len;
    int answer = 0;
    for(int i = 0; i < len - 1; ++i) {
      map<double, int> count;
      int overlap = 0;
      int y = 0;
      for(int j = 0; j < len; ++j) {
        if(i == j) continue;
        int dx = points[i][0] - points[j][0];
        int dy = points[i][1] - points[j][1];
        if(dx == 0 && dy == 0) {
          overlap += 1;
        }else if (dy == 0) {
          y += 1;
        } else {
          count[dx * 1.0 / dy] += 1;
        }
      }
      for(const auto &[_, c] : count) {
        answer = max(answer, 1 + overlap + c);
      }
      answer = max(answer, 1 + y);
    }
    return answer;
  }
};

// Accepted
// 35/35 cases passed (48 ms)
// Your runtime beats 80.56 % of cpp submissions
// Your memory usage beats 37.28 % of cpp submissions (17.4 MB)