# Max Points on a Line

This page explains Java solution to problem `Max Points on a Line` using `Math`.

## Problem Statement

Given `n` points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class MaxPointsOnALine {
public int maxPoints(int[][] points) {
int max = 0;
for(int i = 0; i < points.length; i++) {
int[] p1 = points[i];

HashMap<String, Integer> map = new HashMap<>();
int overlap = 0;
int maxInternal = 0;

for(int j = i + 1; j < points.length; j++) {
int[] p2 = points[j];

int x = p1 - p2;
int y = p1 - p2;

if(x == 0 && y == 0) {
overlap++;
continue;
}

int gcd = gcd(x, y);
if(gcd != 0) {
x = x / gcd;
y = y / gcd;
}

String key = x+"~"+y;
map.put(key, map.getOrDefault(key, 0) + 1);
maxInternal = Math.max(maxInternal, map.get(key));
}
max = Math.max(max, maxInternal + overlap + 1);
}
return max;
}

private int gcd(int a, int b) {
if(b == 0) return a;
else return gcd(b, a % b);
}
}
``````

## Time Complexity

O(N2) Where
N is total number of points on a 2D Plane

## Space Complexity

O(N) Where
N is total number of points on a 2D Plane