Here, We see Max Points on a Line LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Max Points on a Line LeetCode Solution

Problem Statement

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

Max Points on a Line Solution C++

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int ans=2;
        int n= points.size();
        if (n<=2)return n;
        for (int i=0; i<n; i++){
            for (int j=i+1; j<n; j++){
                int dx1 = (points[i][0]-points[j][0]);
                int dy1 = (points[i][1]-points[j][1]);
                int y= __gcd(dx1,dy1);
                if(y!=0)dx1/= y;
                if(y!=0)dy1/= y;
                int curr=2;
                for (int k=0; k<n; k++){
                    if (k==i || k==j)continue;
                    int dx2= (points[k][0]-points[j][0]);
                    int dy2= (points[k][1]-points[j][1]);
                    int x= __gcd(dx2,dy2);
                    if(x!=0)dx2= dx2/x;
                    if(x!=0)dy2= dy2/x;
                    if (dx1==dx2 && dy1==dy2)curr++;
                }
                ans= max(ans,curr);
            }
        }
        return ans;
    }
};Code language: PHP (php)

Max Points on a Line Solution Java

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n <= 2) return n;
        int ans = 2;
        for(int i = 0 ;i < n; i++){
            for(int j = i+1; j < n ; j++){
                int temp = 2;
                for(int k = j+1 ; k<n ; k++ ){
                    int x = (points[j][1] - points[i][1]) * (points[k][0] - points[i][0]);
                    int y = (points[k][1] - points[i][1]) * (points[j][0] - points[i][0]);
                    if(x == y){
                        temp++;
                    }
                }
                if(temp > ans){
                    ans = temp;
                }
            }
        }
        return ans;
    }
}Code language: PHP (php)

Max Points on a Line Solution JavaScript

var maxPoints = function (points) {
    const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

    const getSlopeKey = ([x1, y1], [x2, y2]) => {
        const [dx, dy] = [x1 - x2, y1 - y2];
        const g = gcd(dx, dy);
        return `${dy / g}, ${dx / g}`;
    };
    let max = 1;
    for (let i = 0; i < points.length; i++) {
        const o = {};
        for (let j = i + 1; j < points.length; j++) {
            const key = getSlopeKey(points[i], points[j]);
            o[key] = (o[key] || 0) + 1;
        }
        const count = Math.max(...Object.values(o)) + 1;
        max = Math.max(count, max);
    }
    return max;
};Code language: JavaScript (javascript)

Max Points on a Line Solution Python

class Solution(object):
    def maxPoints(self, points):
        n = len(points)
        if n == 1:
            return 1
        result = 2
        for i in range(n):
            cnt = collections.defaultdict(int)
            for j in range(n):
                if i != j:
                    cnt[math.atan2(points[j][1]-points[i][1], points[j][0]-points[i][0])] += 1
            result = max(result, max(cnt.values())+1)
        return result