Last updated on January 17th, 2025 at 01:00 am
Here, we see a Max Points on a Line LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table, Math
Companies
Apple, LinkedIn, Twitter
Level of Question
Hard
Max Points on a Line LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Geometry and Hashing”. The key idea is to calculate slopes between points and use them to determine if points lie on the same line.
3. Code Implementation in Different Languages
3.1 Max Points on a Line 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;
}
};
3.2 Max Points on a Line 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.3 Max Points on a Line 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;
};
3.4 Max Points on a Line 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n3) | O(1) |
| Java | O(n3) | O(1) |
| JavaScript | O(n2) | O(n) |
| Python | O(n2) | O(n) |
- The C++ and Java implementations are less efficient due to the triple nested loops, resulting in O(n3) time complexity.
- The JavaScript and Python implementations optimize the process by using a hash map or dictionary to store slopes/angles, reducing the time complexity to O(n2).
- Space complexity is higher in JavaScript and Python due to the use of additional data structures for slope/angle storage.