Sharing my simple solution with explanation


  • 77
    Z
    int maxPoints(vector<Point> &points) {
        int result = 0;
        for(int i = 0; i < points.size(); i++){
            int samePoint = 1;
            unordered_map<double, int> map;
            for(int j = i + 1; j < points.size(); j++){
                if(points[i].x == points[j].x && points[i].y == points[j].y){
                    samePoint++;
                }
                else if(points[i].x == points[j].x){
                    map[INT_MAX]++;
                }
                else{
                    double slope = double(points[i].y - points[j].y) / double(points[i].x - points[j].x);
                    map[slope]++;
                }
            }
            int localMax = 0;
            for(auto it = map.begin(); it != map.end(); it++){
                localMax = max(localMax, it->second);
            }
            localMax += samePoint;
            result = max(result, localMax);
        }
        return result;
    }
    

    First, let's talk about mathematics.

    How to determine if three points are on the same line?

    The answer is to see if slopes of arbitrary two pairs are the same.

    Second, let's see what the minimum time complexity can be.

    Definitely, O(n^2). It's because you have to calculate all slopes between any two points.

    Then let's go back to the solution of this problem.

    In order to make this discussion simpler, let's pick a random point A as an example.

    Given point A, we need to calculate all slopes between A and other points. There will be three cases:

    1. Some other point is the same as point A.

    2. Some other point has the same x coordinate as point A, which will result to a positive infinite slope.

    3. General case. We can calculate slope.

    We can store all slopes in a hash table. And we find which slope shows up mostly. Then add the number of same points to it. Then we know the maximum number of points on the same line for point A.

    We can do the same thing to point B, point C...

    Finally, just return the maximum result among point A, point B, point C...


  • 25
    Z

    did this get accepted ?

    using slope as key will cause problems under radical scenarios where float precision are challenged


  • -2
    G

    This solution may have redundant computations.
    For example, if you have 10 points on the same line.
    i=0: you compare the first point with the other 9 points, ie. computing (0,1),(0,2),..(0,9).
    i=1: you pick the 2nd point and compare it with points in [2..9], which is redundant. Because we know points in [2,..9] are on the same line of Point 0.


  • -3
    U

    /hand it without map/

    static bool cmp(const Point & a,const Point & b)
    {
    return (a.x > b.x);
    }

    inline bool onLine(const Point & a,const Point & b,const Point & c)
    {
    return ((b.y-a.y)(c.x-a.x) == (c.y-a.y)(b.x-a.x));
    }

    class Solution {
    public:
    int maxPoints(vector<Point> &points) {
    if(points.size()<=2) return points.size();
    int i,j,k,maxpt=2,t;
    int maxarr[points.size()][points.size()];
    sort(points.begin(),points.end(),cmp);
    for(i=0;i<points.size()-1;i++)
    maxarr[i][i+1]=2;
    for(k=3;k<=points.size();k++)
    for(i=0;i<=points.size()-k;i++)
    {
    t = 1;
    for(j=i+1;j<i+k-1;j++)
    {
    if(onLine(points[i],points[i+k-1],points[j]))
    {
    t = max(maxarr[i][j],t);
    }
    }
    maxarr[i][i+k-1]=t+1;
    maxpt = max(maxarr[i][i+k-1],maxpt);
    }
    return maxpt;
    }
    };


  • 3
    R

    I have one question. for parallel lines, the slopes are the same, but we can have different points on the lines. can you explain how you handle this case?


  • 1
    C

    If two parallel lines cross the same point, they are the same.

    In the algorithm, we are using one point as a base, and then find the max num of lines with the same slope. There is an implicit assumption: all the lines cross the current point.


  • 5
    J

    Two things I observed about your solution -

    1. You can keep track of the local_max in the for(int j) loop so you don't need to go through the entire hash table at end of each for loop.
    2. You can't assume MAX_INT index for points on line with infinite slope. There can be an actual line with slope = MAX_INT value. Since the test cases don't cover this case your solution is accepted. You need to track points with infinite slope value separately.

    Code snippet as below -

        for(int i = 0; i < points.size(); i++) {
            unordered_map<double,int> slope_map;
            int duplicate_pts = 1;
            int infinite_slope_pts = 1;
            double slope = 0.0;
            int local_max = 0;
            for(int j = i+1; j < points.size(); j++) {
                struct Point a = points[i];
                struct Point b = points[j];
                
                if(a.x == b.x && a.y == b.y) {
                    duplicate_pts++;
                }
                else if(a.x == b.x) {
                    infinite_slope_pts++;
                }
                else {
                    slope = (double)(b.y - a.y)/(a.x-b.x);
                    slope_map[slope]++;
                    local_max = max(local_max,slope_map[slope]);
                }
            }
            result = max(result, local_max+duplicate_pts);
            result = max(result,infinite_slope_pts);
        }
    

  • 1
    T

    This method doesn't address the case where the points lie in two parallel lines. I think a good strategy is to have a Map<int,Map<int,int>> where the outer map's key is the slope and inner's maps key is the y-intercept. Of course we need to handle vertical lines separately.


  • 1
    X

    If you want people to read, mark up the code!

    @usherhuangfly said in Sharing my simple solution with explanation:

    /hand it without map/

    static bool cmp(const Point & a,const Point & b)
    {
    return (a.x > b.x);
    }

    inline bool onLine(const Point & a,const Point & b,const Point & c)
    {
    return ((b.y-a.y)(c.x-a.x) == (c.y-a.y)(b.x-a.x));
    }

    class Solution {
    public:
    int maxPoints(vector<Point> &points) {
    if(points.size()<=2) return points.size();
    int i,j,k,maxpt=2,t;
    int maxarr[points.size()][points.size()];
    sort(points.begin(),points.end(),cmp);
    for(i=0;i<points.size()-1;i++)
    maxarr[i][i+1]=2;
    for(k=3;k<=points.size();k++)
    for(i=0;i<=points.size()-k;i++)
    {
    t = 1;
    for(j=i+1;j<i+k-1;j++)
    {
    if(onLine(points[i],points[i+k-1],points[j]))
    {
    t = max(maxarr[i][j],t);
    }
    }
    maxarr[i][i+k-1]=t+1;
    maxpt = max(maxarr[i][i+k-1],maxpt);
    }
    return maxpt;
    }
    };


  • 0
    M

    @zinking
    I agree with you. So it might be better to use two integers to represent the slope and convert them to a string to look up the map.

    int A = points[j].y - y0;
    int B = points[j].x - x0;
    int g = gcd(abs(A), abs(B));
    A /= g;
    B /= g;
    if (A < 0) {
        A = -A;
        B = -B;
    }
    ostringstream str;
    str << A << "," << B;
    localMax = max(localMax, ++pointsOnLine[str.str()]);
    

  • 0
    S

    @jayesch said in Sharing my simple solution with explanation:

    Please someone help me with a doubt.

    result = max(result, local_max+duplicate_pts);
    result = max(result,infinite_slope_pts);

    Shouldn't this be?

    result = max(result, local_max+duplicate_pts);
    result = max(result,infinite_slope_pts+duplicate_pts);


  • 0

    GREAT SIMPLE CLEAR Explain!

    But need take care of float type slope as key issue:
    "Fraction to recurring Decimal" can be used as key here.
    https://leetcode.com/problems/fraction-to-recurring-decimal/


  • 0

    Great Solution
    Python Implementation

    class Solution(object):
        def maxPoints(self, points):
            """
            :type points: List[Point]
            :rtype: int
            """
            ans = 0
            for i in range(len(points)):
                x1, y1 = points[i].x, points[i].y
                h, samePoint = {}, 1
                for j in range(i+1,len(points)):
                    x2, y2 = points[j].x, points[j].y
                    if x2 == x1 and y2 == y1:
                        samePoint += 1
                    elif x2 == x1:
                        h['-'] = h.get('-', 0) + 1
                    else:
                        slope = (y2-y1)*1.0 / (x2-x1)
                        h[slope] = h.get(slope, 0) + 1
                ans = max(ans, samePoint+max(h.values()+[0]))
            return ans

  • 0
    K

    in the first loop we reset the hashmap every time, why in the inner for loop we don't need to calculate with the points before points[i]. how's the logic behind this.


  • 0

    Hi,

    It looks like your code is failing for this test case.

    Input:
    [[0,0],[94911151,94911150],[94911152,94911151]]
    Output:
    3
    Expected:
    2

    @lilixu said in Sharing my simple solution with explanation:

    class Solution(object):
    def maxPoints(self, points):
    """
    :type points: List[Point]
    :rtype: int
    """
    ans = 0
    for i in range(len(points)):
    x1, y1 = points[i].x, points[i].y
    h, samePoint = {}, 1
    for j in range(i+1,len(points)):
    x2, y2 = points[j].x, points[j].y
    if x2 == x1 and y2 == y1:
    samePoint += 1
    elif x2 == x1:
    h['-'] = h.get('-', 0) + 1
    else:
    slope = (y2-y1)*1.0 / (x2-x1)
    h[slope] = h.get(slope, 0) + 1
    ans = max(ans, samePoint+max(h.values()+[0]))
    return ans


  • 1

    @shiyan2
    Thank you for pointing out. That's because of the float precision in python. Use fraction instead.

    class Solution(object):
        def maxPoints(self, points):
            ans = 0
            for i, p1 in enumerate(points):
                h, same_p = {}, 1
                for j, p2 in enumerate(points[i+1:]):
                    if p1.x == p2.x and p1.y == p2.y:
                        same_p += 1
                    elif p1.x == p2.x:
                        h['-'] = h.get('-', 0) + 1
                    else:
                        slope = str(Fraction(p1.y-p2.y, p1.x-p2.x))
                        h[slope] = h.get(slope, 0) + 1
                ans = max(ans, same_p + max([h[x] for x in h] + [0]))
            return ans

  • 0

    Refer to:
    http://www.geeksforgeeks.org/count-maximum-points-on-same-line/
    treat slope as pair ((y2 – y1), (x2 – x1)) instead of ratio and reduce pair by their gcd before inserting into map in case of precision problem.


  • 0
    M

    @zinking Yes, you are right, that is my concern too.
    In my opinion, if we express a line in y = kx + b. we should store the k and b using fraction.
    That is, we should store a numerator and a denominator for a number.

    In C++, I use this as a key.

    bitset<64> line = (bitset<64>(kup) << 32) |
    (bitset<64>(kdwn))

    I did not realize that the 'b' in line can be ignored.


  • 0
    T

    why do you increment INT_MAX ?


  • 1
    M

    Can your solution pass the test case
    [[0,0],[94911151,94911150],[94911152,94911151]] ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.