Last updated on July 21st, 2024 at 03:43 am
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
Topics
Hash Table, Math
Companies
Apple, LinkedIn, Twitter
Level of Question
Hard
![Max Points on a Line LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
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:
![plane1](https://i0.wp.com/assets.leetcode.com/uploads/2021/02/25/plane1.jpg?w=1400&ssl=1)
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
![plane2](https://i0.wp.com/assets.leetcode.com/uploads/2021/02/25/plane2.jpg?w=1400&ssl=1)
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
1. 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; } };
2. 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; } }
3. 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; };
4. 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