Max Points on a Line LeetCode Solution | Easy Approach

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.

Max Points on a Line Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  int maxPoints(vector<vector<int>>& points) {
    int ans = 0;

    for (int i = 0; i < points.size(); ++i) {
      unordered_map<pair<int, int>, int, pairHash> slopeCount;
      const vector<int> p1{points[i]};
      int samePoints = 1;
      int maxPoints = 0;  // maximum number of points with the same slope
      for (int j = i + 1; j < points.size(); ++j) {
        const vector<int> p2{points[j]};
        if (p1 == p2)
          ++samePoints;
        else
          maxPoints = max(maxPoints, ++slopeCount[getSlope(p1, p2)]);
      }
      ans = max(ans, samePoints + maxPoints);
    }

    return ans;
  }

 private:
  pair<int, int> getSlope(const vector<int>& p1, const vector<int>& p2) {
    const int dx = p2[0] - p1[0];
    const int dy = p2[1] - p1[1];
    if (dx == 0)
      return {0, p1[0]};
    if (dy == 0)
      return {p1[1], 0};
    const int d = __gcd(dx, dy);
    return {dx / d, dy / d};
  }

  struct pairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};

Java

 class Solution {
  public int maxPoints(int[][] points) {
    int ans = 0;

    for (int i = 0; i < points.length; ++i) {
      Map<Pair<Integer, Integer>, Integer> slopeCount = new HashMap<>();
      int[] p1 = points[i];
      int samePoints = 1;
      int maxPoints = 0; // maximum number of points with the same slope
      for (int j = i + 1; j < points.length; ++j) {
        int[] p2 = points[j];
        if (p1[0] == p2[0] && p1[1] == p2[1])
          ++samePoints;
        else {
          Pair<Integer, Integer> slope = getSlope(p1, p2);
          slopeCount.merge(slope, 1, Integer::sum);
          maxPoints = Math.max(maxPoints, slopeCount.get(slope));
        }
      }
      ans = Math.max(ans, samePoints + maxPoints);
    }

    return ans;
  }

  private Pair<Integer, Integer> getSlope(int[] p1, int[] p2) {
    final int dx = p2[0] - p1[0];
    final int dy = p2[1] - p1[1];
    if (dx == 0)
      return new Pair<>(0, p1[0]);
    if (dy == 0)
      return new Pair<>(p1[1], 0);
    final int d = gcd(dx, dy);
    return new Pair<>(dx / d, dy / d);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

Python

class Solution:
  def maxPoints(self, points: List[List[int]]) -> int:
    ans = 0

    def gcd(a: int, b: int) -> int:
      return a if b == 0 else gcd(b, a % b)

    def getSlope(p1: List[int], p2: List[int]) -> Tuple[int, int]:
      dx = p2[0] - p1[0]
      dy = p2[1] - p1[1]
      if dx == 0:
        return (0, p1[0])
      if dy == 0:
        return (p1[1], 0)
      d = gcd(dx, dy)
      return (dx // d, dy // d)

    for i, p1 in enumerate(points):
      slopeCount = defaultdict(int)
      samePoints = 1
      maxPoints = 0
      for j in range(i + 1, len(points)):
        p2 = points[j]
        if p1 == p2:
          samePoints += 1
        else:
          slope = getSlope(p1, p2)
          slopeCount[slope] += 1
          maxPoints = max(maxPoints, slopeCount[slope])
      ans = max(ans, samePoints + maxPoints)

    return ans

Watch Tutorial

Checkout more Solutions here