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
Table of Contents
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