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[1] - p1[1]) * (p3[0] - p1[0]) == (p3[1] - p1[1]) * (p2[0] - p1[0])) {
                        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)