Leetcode 149 Solution

This article provides solution to leetcode question 149 (max-points-on-a-line)
Categories:
Tags:
Access this page by simply typing in "lcs 149" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/max-points-on-a-line

Solution

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        if (points.size() == 0)
            return 0;



        int max_val = 0;



        for (int i = 0; i < points.size(); i++)
        {
            const auto& pt1 = points[i];



            unordered_map<double, int> slope_cnt;
            int vertical_cnt = 0;
            int same_cnt = 0;
            int local_max = 0;



            for (int j = i + 1; j < points.size(); j++)
            {
                const auto& pt2 = points[j];



                if (pt1.x == pt2.x)
                {
                    if (pt1.y == pt2.y)
                        same_cnt++;
                    else
                    {
                        vertical_cnt++;
                        local_max = max(local_max, vertical_cnt);
                    }
                }
                else
                {
                    double slope = (pt1.y - pt2.y) * 1.0 / (pt1.x - pt2.x);
                    slope_cnt[slope]++;
                    local_max = max(local_max, slope_cnt[slope]);
                }
            }



            max_val = max(max_val, local_max + same_cnt + 1);
        }



        return max_val;
    }
};