# Question

Formatted question description: https://leetcode.ca/all/149.html

149	Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

@tag-hashtable
@tog-top100


# Algorithm

A slope can be calculated between two given points. Each slope represents a straight line. For each straight line, bring in all the points to see if they are collinear and calculate the number.

Two special cases need to be considered.

• One is that when two points coincide, a straight line cannot be determined, but this is also a collinear case and requires special treatment.
• The second is the case where the slope does not exist. Since the slope k of the two points (x1, y1) and (x2, y2) is expressed as (y2-y1) / (x2-x1), then the slope does not exist when x1 = x2, This collinear situation requires special treatment

TreeMap is used to record the mapping between the slope and the number of collinear points. The first case of coincident points assumes its slope is INT_MIN, and the second case assumes its slope is INT_MAX, so TreeMap can be used for mapping. A variable duplicate is also needed to record the number of coincident points, and finally only needs to be added to the number in the TreeMap to get the total number of collinear points.

# Code

Java

• import java.util.HashMap;
import java.util.Map;

public class Max_Points_on_a_Line {

public static void main(String[] args) {

double a = 0.0 / (-1);
System.out.println("a:" + a);

double b = 0.0 / (1);
System.out.println("b:" + b);

System.out.println("a == b ? " + (a == b)); // output: true

HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
hm.put(a, 1);
hm.put(b, 1);
// @note:@memorize: so, different keys
System.out.println("hashmap keys: " + (hm.keySet())); // output: [-0.0, 0.0]

}

/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0)
return 0;

// line slope => number of points
HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
int max = 0;

// have to touch every possible line, so O(logN)
for (int i = 0; i < points.length; i++) {
int duplicate = 1;
int vertical = 0;
for (int j = i + 1; j < points.length; j++) {
// @note:@memorize: handle duplicates and vertical
if (points[i].x == points[j].x) {
if (points[i].y == points[j].y) {
duplicate++; // itself
} else {
vertical++; // vertical line at the same x position
}
} else {
double slope = points[j].y == points[i].y ? 0.0 : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x);

hm.merge(slope, 1, (a, b) -> a + b);
}
}

// record max number of points for one line
for (Integer count : hm.values()) {
if (count + duplicate > max) {
max = count + duplicate;
}
}

// @note:@memorize: special case for vertical line points
max = Math.max(vertical + duplicate, max);

hm.clear(); // @note: api, better than create a new hashmap?
}

return max;
}

}
}

• // OJ: https://leetcode.com/problems/max-points-on-a-line/
// Time: O(N^3)
//   In worse case, when visiting ith point, there will be O(i^2)
//   lines, but all the lines are of constant size 2. So in
//   sum it's O(N^3), not O(N^4).
// Space: O(N^2)
namespace std {
template <> struct hash<Point> {
std::size_t operator () (const Point &p) const {
return hash<int>()(p.x) ^ hash<int>()(p.y);
}
};
}

bool operator==(const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}

class Solution {
private:
bool onSameLine(Point &a, Point &b, Point &c) {
return (long long)(a.x - b.x) * (a.y - c.y) == (long long)(a.x - c.x) * (a.y - b.y);
}
public:
int maxPoints(vector<Point>& points) {
if (points.size() <= 2) return points.size();
unordered_map<Point, int> m;
for (auto p : points) m[p]++;
vector<pair<Point, int>> ps(m.begin(), m.end());
vector<vector<int>> lines(1, vector<int>{ 0, 1 });
int N = ps.size();
for (int i = 2; i < N; ++i) {
auto &p = ps[i].first;
for (auto &line : lines) {
auto &p1 = ps[line[0]].first, &p2 = ps[line[1]].first;
if (!onSameLine(p1, p2, p)) continue;
for (int neighbor : line) bad[neighbor] = 0;
line.push_back(i);
}
for (int j = 0; j < i; ++j) {
if (bad[j]) lines.emplace_back(vector<int>{ j, i });
}
}
int ans = 2;
for (auto line : lines) {
int cnt = 0;
for (auto i : line) cnt += ps[i].second;
ans = max(ans, cnt);
}
return ans;
}
};

• # Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""

def gcd(a, b):
while b:
a, b = b, a % b
return a

ans = 1
d = {}
points.sort(key=lambda p: (p.x, p.y))
for i in range(0, len(points)):
if i > 0 and (points[i].x, points[i].y) == (points[i - 1].x, points[i - 1].y):
continue
overlap = 1
for j in range(i + 1, len(points)):
x1, y1 = points[i].x, points[i].y
x2, y2 = points[j].x, points[j].y
ku, kd = y2 - y1, x2 - x1
if (x1, y1) != (x2, y2):
kg = gcd(ku, kd)
ku /= kg
kd /= kg
d[(ku, kd, x1, y1)] = d.get((ku, kd, x1, y1), 0) + 1
else:
overlap += 1
ans = max(ans, overlap)
ans = max(ans, d.get((ku, kd, x1, y1), 0) + overlap)
return min(ans, len(points))