LeetCode OJ: Max Points on a Line

This LeetCode problem has the second lowest AC rate. It deserves some attention as it asks for the use of hash table and choice of hash function that requires some thought.

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

A naive O(n^3) algorithm will consider all pairs of points (p_i, p_j), then for all k != i or j, check whether p_k is on the line defined by p_i and p_j. Identical points needs to be taken care of. An implementation of O(n^3) algorithm is as follows:

	/**
	* 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.length == 0) {
	return 0;
	}
	Arrays.sort(points, new PointComparator());
	int cur = 0;
	int i = 1;
	int[] counts = new int[points.length];
	counts[0] = 1;
	while (i < points.length) {
	if (points[cur].x == points[i].x && points[cur].y == points[i].y) {
	i++;
	counts[cur]++;
	} else {
	cur++;
	points[cur].x = points[i].x;
	points[cur].y = points[i].y;
	i++;
	counts[cur] = 1;
	}
	}
	return maxDistinct(points, counts, cur + 1);
	}
	private static class PointComparator implements Comparator<Point> {
	public int compare (Point p1, Point p2) {
	if (p1.x > p2.x) {
	return 1;
	} else if (p1.x < p2.x) {
	return -1;
	} else if (p1.y > p2.y) {
	return 1;
	} else if (p1.y < p2.y) {
	return -1;
	} else {
	return 0;
	}
	}
	}
	public int maxDistinct(Point[] points, int[] counts, int n) {
	if (points.length == 0) {
	return 0;
	} else if (n == 1) {
	return counts[0];
	} else if (n == 2) {
	return counts[0] + counts[1];
	}
	int max = 2;
	for (int i = 0; i < n; i++) {
	Point p1 = points[i];
	for (int j = i + 1; j < n; j++) {
	Point p2 = points[j];
	int val = counts[i] + counts[j];
	for (int k = j + 1; k < n; k++) {
	Point p3 = points[k];
	if ((p3.y - p2.y) * (p2.x - p1.x) == (p3.x - p2.x) * (p2.y - p1.y)) {
	val += counts[k];
	}
	}
	if (val > max) {
	max = val;
	}
	}
	}
	return max;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

A better O(n^2) solution is possible by using hash tables. Notice that this problem is known to be 3SUM-hard so a non-parallel, non-randomized algorithm is unlikely to be better than O(n^2).

To implement a O(n^2) algorithm, one need to create a hash table whose key is encoding of line. One way to encode a line in 2D plan is using slope-intercept form: y = mx + b. However, a and b could be float numbers even if x and y are integers and it is well-known that equality test for float number is error-prone. Instead, I choose to use the standard form: ax + by + c = 0. If we have two distinct points (x1, y1) and (x2, y2), then we can set a = y2 - y1, b = x1 - x2, c = y2 * x1 - y1 * x2, and all of a, b and c will be integers. However, this (a, b, c) is not unique as any integral multiple of it represents the same line. To guarantee uniqueness, we require b to be nonnegative. If b is zero, i.e. the line is vertical, then we require a to be positive. Notice that a and b can not both be zero.

We need to find a good hash function in order to use this (a, b, c) representation as key of hash table. The hash function for hashing integer vectors mentioned in my last post is a good candidate. In particular for the problem at hand, I used:

h(a, b, c) = a + b * 31 + c * 31 ^ 2.

The algorithm itself is straightforward. For each point p_i, we consider all points after it {p_i+1, ..., p_n}. We create a hash table whose key is (a, b, c) tuple and whose value is the number of points in {p_i+1, ..., p_n} that connects to p_i by the line represented by the corresponding key. The the largest value in the constructed hash table is the maximum number of points that lie on the same straight line if the smallest index of those points is i. An implementation is as follows:

	/**
	* 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 {
	private class Line {
	int a;
	int b;
	int c;
	public Line(Point p1, Point p2) {
	this(p2.y - p1.y, p1.x - p2.x, p2.y * p1.x - p2.x * p1.y);
	}
	public Line(int a, int b, int c) {
	if (b != 0) {
	if (b < 0) {
	a = -a;
	b = -b;
	c = -c;
	}
	int gcd1 = gcd(b, Math.abs(a));
	int gcd2 = gcd(gcd1, Math.abs(c));
	this.a = a / gcd2;
	this.b = b / gcd2;
	this.c = c / gcd2;
	} else {
	if (a != 0) {
	if (a < 0) {
	a = -a;
	c = -c;
	}
	int gcd1 = gcd(a, Math.abs(c));
	this.a = a / gcd1;
	this.b = 0;
	this.c = c / gcd1;
	} else {
	this.a = 0;
	this.b = 0;
	this.c = 0;
	}
	}
	}
	private int gcd(int x, int y) {
	// Assume x >= 0, y >= 0.
	if (x > y) {
	return gcd(y, x);
	} else if (x == 0) {
	return y;
	} else {
	return gcd(y % x, x);
	}
	}
	public boolean equals(Object o) {
	if (o instanceof Line) {
	Line l = (Line)o;
	return (a == l.a && b == l.b && c == l.c);
	} else {
	return false;
	}
	}
	public int hashCode() {
	return a * 31 * 31 + b * 31 + c;
	}
	}
	public int maxPoints(Point[] points) {
	if (points.length <= 2) {
	return points.length;
	}
	Arrays.sort(points, new PointComparator());
	Map<Line, Integer> m = new HashMap<Line, Integer>();
	int max = 0;
	for (int i = 0; i < points.length; ) {
	m.clear();
	int sameCount = 1;
	for (int j = i+1; j < points.length; j ++) {
	if (points[i].x == points[j].x && points[i].y == points[j].y) {
	sameCount ++;
	} else {
	Line l = new Line(points[i], points[j]);
	if (m.containsKey(l)) {
	m.put(l, m.get(l) + 1);
	} else {
	m.put(l, sameCount + 1);
	}
	}
	}
	m.put(new Line(0, 0, 0), sameCount);
	for (int v : m.values()) {
	max = Math.max(max, v);
	}
	i += sameCount;
	}
	return max;
	}
	private static class PointComparator implements Comparator<Point> {
	public int compare (Point p1, Point p2) {
	if (p1.x > p2.x) {
	return 1;
	} else if (p1.x < p2.x) {
	return -1;
	} else if (p1.y > p2.y) {
	return 1;
	} else if (p1.y < p2.y) {
	return -1;
	} else {
	return 0;
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Interestingly, the running time of O(n^2) and O(n^3) solutions are not very different on LeetCode OJ, which is probably due to large overhead and small testing cases.