149. Max Points on a Line LeetCode Solution

In this guide, you will get 149. Max Points on a Line LeetCode Solution with the best time and space complexity. The solution to Max Points on a Line problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Max Points on a Line solution in C++
Max Points on a Line solution in Java
Max Points on a Line solution in Python
Additional Resources

149. Max Points on a Line LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

149. Max Points on a Line LeetCode Solution in 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;  // the 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>& p, const vector<int>& q) {
    const int dx = p[0] - q[0];
    const int dy = p[1] - q[1];
    if (dx == 0)
      return {0, p[0]};
    if (dy == 0)
      return {p[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;
    }
  };
};
/* code provided by PROGIEZ */

149. Max Points on a Line LeetCode Solution in 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; // the 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[] p, int[] q) {
    final int dx = p[0] - q[0];
    final int dy = p[1] - q[1];
    if (dx == 0)
      return new Pair<>(0, p[0]);
    if (dy == 0)
      return new Pair<>(p[1], 0);
    final int d = gcd(dx, dy);
    return new Pair<>(dx / d, dy / y);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
// code provided by PROGIEZ

149. Max Points on a Line LeetCode Solution in 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(p: list[int], q: list[int]) -> tuple[int, int]:
      dx = p[0] - q[0]
      dy = p[1] - q[1]
      if dx == 0:
        return (0, p[0])
      if dy == 0:
        return (p[1], 0)
      d = gcd(dx, dy)
      return (dx // d, dy // d)

    for i, p in enumerate(points):
      slopeCount = collections.defaultdict(int)
      samePoints = 1
      maxPoints = 0  # the maximum number of points with the same slope
      for j in range(i + 1, len(points)):
        q = points[j]
        if p == q:
          samePoints += 1
        else:
          slope = getSlope(p, q)
          slopeCount[slope] += 1
          maxPoints = max(maxPoints, slopeCount[slope])
      ans = max(ans, samePoints + maxPoints)

    return ans
 # code by PROGIEZ