# Solution For Max Points On A Line

The problem “Max Points on a Line” on LeetCode asks us to find the maximum number of points that are located on the same line given an array of points.

Approach: We can use a hashmap to store the slope of the line between each point and count the maximum number of points on the same line.

Algorithm:

1. Create a hashmap named as slopes, which will store the slope(value) of each point(key) in the given points array.

2. Iterate through each point in the given points array.

3. Initialize two counters, one for the duplicate points and the other for the maximum number of points on the same line containing the current point.

4. For each point, iterate through the remaining points in the array and calculate the slope of the line passing through the current point and the remaining point.

5. If the current point is same as the remaining point, then increment the duplicate points counter.

6. If the slope does not exist in the hashmap, then add it along with the count 2 (the current point and the remaining point).

7. If the slope already exists in the hashmap, then increment its count by 1.

8. Update the maximum number of points by comparing the current number of points with the maximum number of points so far.

9. Repeat steps 4-8 for each point in the given array.

10. Return the maximum number of points on the same line.

Code:

Here is the Java implementation of the above algorithm:

class Solution {
public int maxPoints(int[][] points) {
if (points.length == 0)
return 0;
int maxPoints = 1;
for(int i = 0; i < points.length; i++){
Map slopes = new HashMap<>();
int count = 1;
for(int j = i+1; j < points.length; j++){
int x1 = points[i];
int x2 = points[j];
int y1 = points[i];
int y2 = points[j];
if (x1 == x2 && y1 == y2) {
count++;
continue;
}
double k = (x1 == x2) ? Double.POSITIVE_INFINITY :
((double) (y2-y1) / (double) (x2-x1));
if (slopes.containsKey(k)) {
slopes.put(k, slopes.get(k)+1);
} else {
slopes.put(k, 2);
}
}
if (slopes.isEmpty()) {
maxPoints = Math.max(maxPoints, count);
} else {
for (int value: slopes.values()) {
maxPoints = Math.max(maxPoints, count+value-1);
}
}
}
return maxPoints;
}
}

Time Complexity: O(n^2) – As we need to traverse all the points and for each point, we need to traverse the remaining points.

Space Complexity: O(n) – As we are using a hashmap of space proportional to the number of points in the given array.

## Step by Step Implementation For Max Points On A Line

```/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) return 0;
if (points.length == 1) return 1;
int max = 0;
for (int i = 0; i < points.length - 1; i++) {
Point p1 = points[i];
int duplicate = 1;
int localMax = 0;
HashMap map = new HashMap();
for (int j = i + 1; j < points.length; j++) {
Point p2 = points[j];
if (p1.x == p2.x && p1.y == p2.y) {
duplicate++;
continue;
}
double slope = 0.0;
if (p1.x == p2.x) {
slope = Double.MAX_VALUE;
} else {
slope = 1.0 * (p2.y - p1.y) / (p2.x - p1.x) + 0.0;
}
if (map.containsKey(slope)) {
map.put(slope, map.get(slope) + 1);
} else {
map.put(slope, 1);
}
localMax = Math.max(localMax, map.get(slope));
}
max = Math.max(max, localMax + duplicate);
}
return max;
}
}```
```def maxPoints(self, points):
# create a map of slopes to count of points with that slope
# for each point, iterate over all other points and calculate slope
# if slope is the same, increment count for that slope
# keep track of max count
# time complexity: O(n^2), space complexity: O(n)

slope_map = {}
max_count = 0

for i in range(len(points)):
for j in range(i+1, len(points)):
# calculate slope
# use float to avoid integer division
slope = (points[j] - points[i]) / float((points[j] - points[i]))
# use defaultdict to handle case where slope is not in map
slope_map[slope] = slope_map.get(slope, 0) + 1
# update max count
max_count = max(max_count, slope_map[slope])

return max_count```
```/**
* @param {number[][]} points
* @return {number}
*/

// Solution:

var maxPoints = function(points) {

// edge case: if there are less than 3 points, then the max number of points on a line is equal to the number of points
if (points.length < 3) {
return points.length;
}

// create a map to store the slope of each line
// the key is the slope, and the value is the number of points on that line
let map = {};

// create a variable to keep track of the max number of points on a line
let max = 0;

// iterate through each point
for (let i = 0; i < points.length; i++) {

// set the number of points on a line to 1 for each point
let numPoints = 1;

// iterate through each other point
for (let j = i + 1; j < points.length; j++) {

// calculate the slope of the line between the current point and the other point
let slope = (points[j] - points[i]) / (points[j] - points[i]);

// if the slope is not a number, set it to 0
if (isNaN(slope)) {
slope = 0;
}

// if the slope is already in the map, increment the number of points on that line
if (map[slope]) {
numPoints++;
}
// otherwise, set the number of points on that line to 2
else {
numPoints = 2;
}

// update the map with the new slope and number of points
map[slope] = numPoints;

// update the max if necessary
if (numPoints > max) {
max = numPoints;
}
}
}

// return the max
return max;
};```
```class Solution {
public:
int maxPoints(vector& points) {
int n = points.size();
if (n <= 2) return n;
int res = 0;
for (int i = 0; i < n; ++i) {
map, int> mp;
int same = 1;
for (int j = i + 1; j < n; ++j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
++same;
continue;
}
int dx = points[i].x - points[j].x;
int dy = points[i].y - points[j].y;
int d = gcd(dx, dy);
++mp[{dx / d, dy / d}];
}
res = max(res, same);
for (auto it : mp) {
res = max(res, it.second + same);
}
}
return res;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
};```
```/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int MaxPoints(Point[] points) {
// check for edge cases
if (points == null || points.Length == 0) {
return 0;
}

// map to store the slope and number of points with same slope
Dictionary map = new Dictionary();

// max number of points on a line passing through a point
int maxPoints = 1;

// loop through all points
for (int i = 0; i < points.Length; i++) {
// reset map
map.Clear();

// current point
Point p1 = points[i];

// number of points with same x coordinate as p1
int sameX = 1;

// number of points with same y coordinate as p1
int sameP = 0;

// loop through all points again
for (int j = i + 1; j < points.Length; j++) {
// current point
Point p2 = points[j];

// if p1 and p2 have the same x coordinate
if (p1.x == p2.x) {
// if p1 and p2 have the same y coordinate
if (p1.y == p2.y) {
// increment sameP
sameP++;
}
// otherwise, increment sameX
else {
sameX++;
}
}
// if p1 and p2 have different x coordinates
else {
// calculate slope
double slope = (double)(p1.y - p2.y) / (double)(p1.x - p2.x);

// if slope is not in map, add it with value 1
if (!map.ContainsKey(slope)) {
}
// otherwise, increment the value
else {
map[slope]++;
}
}
}

// update maxPoints
maxPoints = Math.Max(maxPoints, sameX);

// add points with same slope
foreach (int value in map.Values) {
maxPoints = Math.Max(maxPoints, value + sameP);
}
}

return maxPoints;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]