# Leetcode 149 Solution

This article provides solution to leetcode question 149 (max-points-on-a-line)

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;
}
};
``````