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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= points.length &lt;= 300
	points[i].length == 2
	-104 &lt;= xi, yi &lt;= 104
	All the points are unique.


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ans = 0
        n = len(points)
        
        for i in range(n):
            d = collections.defaultdict(int)
            for j in range(n):
                if i != j:
                    slope = float("inf")
                    if (points[j][1] - points[i][1] != 0):
                        slope = (points[j][0] - points[i][0]) / (points[j][1] - points[i][1])
                    d[slope] += 1
            if d:
                ans = max(ans, max(d.values())+1)
            else:
                ans = max(ans, 1)
        
        return ans
class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n == 1) return n;
        int result = 0;
        for(int i = 0; i< n; i++){
            for(int j = i+1; j< n; j++){
                result = Math.max(result, getPoints(i, j, points));
            }
        }
        return result;
    }
    private int getPoints(int pt1, int pt2, int[][] points){
        int[] point1 = points[pt1], point2 = points[pt2];
        double slope = (point1[1] - point2[1])/(double)(point1[0] - point2[0]);
        int result = 0;
        for(int i = 0; i<points.length; i++){
            if((points[i][0] == point1[0] && points[i][1] == point1[1]) ||
               (slope == Double.POSITIVE_INFINITY && (point1[1] - points[i][1])/(double)(point1[0] - points[i][0]) == Double.POSITIVE_INFINITY) ||
               ((double)(point1[1] - points[i][1])/(double)(point1[0] - points[i][0]) == slope))
                result++;
        }
        return result;
    }
}
class Solution {
public:

    //DP solution
    //TC-O(N*N)
    //SC- ~ O(N*N)
    //Custom Sort
    bool static cmp(vector<int> p1,vector<int> p2){
        if(p1[0]==p2[0])
            return p1[1]<p2[1];
        return p1[0]<p2[0];
    }

    //Slope Calculating
    float calcSlope(int x1,int y1,int x2,int y2){
       return (y2-y1)/(float)(x2-x1);
    }
    int maxPoints(vector<vector<int>>& points) {
        if(points.size()==2 || points.size()==1)
            return points.size();

        sort(points.begin(),points.end(),cmp);
        int ans=1;
        //How much points having same slope at current index
        vector<unordered_map<float,int>> dp(points.size()+1);
        for(int i=1;i<points.size();i++){
            for(int j=0;j<i;j++){
                float slope=calcSlope(points[j][0],points[j][1],points[i][0],points[i][1]);
                if(dp[j].find(slope)!=dp[j].end()){
                    dp[i][slope]=1+dp[j][slope];
                    ans=max(ans,dp[i][slope]);
                }else{
                    dp[i][slope]+=1;
                }
            }
        }
        //return ans

        return ans+1;

    }
};
/**
 * @param {number[][]} points
 * @return {number}
 */

var maxPoints = function(points) {
    if (points.length === 1) {
        return 1;
    }
    
    const slopes = {};
    let dx, dy;
    let xbase, ybase;
    let xref, yref, key;
    const INFINITE_SLOPE = 'infinite';
    
    for(let i = 0; i < points.length; i++) {
        [xbase, ybase] = points[i];
        
        for(let j = i + 1; j < points.length; j++) {                       
            
            [xref, yref] = points[j];
            
            if (xref === xbase) {
                key = `x = ${xref}`;
                
            } else {
                dx = xref - xbase;
                dy = yref - ybase;
                
                let m = dy / dx;
                let c = yref - m * xref;
                
                m = m.toFixed(4);
                c = c.toFixed(4);
                
                key = `y = ${m}x + ${c}`;                
            }
            
            slopes[key] || (slopes[key] = 0);
            slopes[key]++;
        }
    }
    
    const maxPairs = Math.max(...Object.values(slopes));
    
    if (maxPairs === 2) {
        return 2;
    }
    
    for(let i = 1; i <= 300; i++) {
        if (i * (i - 1) / 2 === maxPairs) {
            return i;
        }
    }
    
    return 0;
};
Max Points on a Line