## DEV Community # 149. Max Points on a Line

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

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Solution:

Algorithm:

1. Create a variable max to store the maximum number of points on the same line.
2. Traverse through the points array and for each point, traverse through the points array again and for each point, traverse through the points array again and for each point, check if the three points lie on the same line.
3. If the three points lie on the same line, increment the count variable.
4. Update the max variable with the maximum of max and count.
5. Return max.

Code:

``````public class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n < 3) {
return n;
}
int max = 0;
for (int i = 0; i < n; i++) {
int[] p1 = points[i];
for (int j = i + 1; j < n; j++) {
int[] p2 = points[j];
int count = 0;
for (int k = 0; k < n; k++) {
int[] p3 = points[k];
if ((p2 - p1) * (p3 - p1) == (p3 - p1) * (p2 - p1)) {
count++;
}
}
max = Math.max(max, count);
}
}
return max;
}

}

``````

Complexities:

1. - Time complexity: O(n^3) where n is the length of points array.
2. - Space Complexity: O(1)

DEV Community

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course. 