LeetCode Max Points on a Line: Hashing

Overview

LeetCode Max Points on a Line could be solved in O(N^2) time by find the maximum point set containing i in O(N) time (Hash) and get the maximum among all i’s.

LeetCode 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.

Analysis: Hashing

1) Naive solution: for each pair of nodes, we determine the line cross them, and test this line against all the points to check whether the point is on this line or not. Obviously, this is O(N^3) solution. Although not efficient, it could pass the LeetCode OJ anyways to solve Max Points on a Line problem:

class Line {
    public:
        Line() : a(0), b(0), c(0) {}
        Line(const Point &p1, const Point &p2) {
            a = p1.y - p2.y;
            b = p2.x - p1.x;
            c = (p1.x - p2.x) * p2.y - p2.x * (p1.y - p2.y);
        }
        ~Line() {}

        bool isOnMe(const Point &p) {
            return 0 == a * p.x + b * p.y + c;
        }

        int countPoints(const vector<Point> &ps) {
            int cnt = 0;
            for (int i = ps.size() - 1; i >= 0; --i)
                if (isOnMe(ps[i])) ++cnt;
            return cnt;
        }
    private:
        int a, b, c;
};

class Solution {
    public:
        int maxPoints(vector<Point> &points) { int n = points.size();
            if (n <= 2) return n;

            int cnt = -1;
            for (int i = n - 1; i > 1; --i) {
                for (int j = i - 1; j >= 0; --j) {
                    if (points[i].x != points[j].x || points[i].y != points[j].y) {
                        Line line(points[i], points[j]);
                        cnt = max(cnt, line.countPoints(points));
                    }
                    else {
                        int c = 0;
                        for (int k = 0; k < n; ++k) {
                            if (points[k].x == points[i].x && points[k].y == points[i].y) ++c;
                            cnt = max(cnt, c);
                        }
                    }
                }
            }
            return cnt;
        }
};

Special care should be taken of to handle the duplicated points in the input which is the very tricky part and such repeated points need to be counted into the results!

2) O(N^2) solution using Hashing: So can we come up with more efficient solution? Of course! The key is that we can actually find the maximum number of point set that contains point i in O(N) time. That is, for each point in the input, we can calculate the maximum number of points on the same line across point i, and this could be done in O(N) time by using Hashing table. And among all these “local” maximum points, we return the “global” maximum among them (really a bit of DP flavor), then we are good! So let’s see how can we determine the the maximum point set for point i in O(N) time.

We need some math concepts of lines. We know that a line could be determined by the slop and a point on that line. So for point i, we calculate the slope of the lines determined by point and any other point j != i and each time we store this slope into a hash table: if the slope determined by point and j is already in hash table, this means, the current point j is on the same line which is determined by point i and some previous point, so we update the value of the hash able entry (slope, count) where count just keeps the number of such points on the line with slope and point i. All of these could be done in constant time using the hash table, and we get the local maximum for point i.

The following is the source code accepted by LeetCode OJ to pass this Max Points on a Line problem:

class Slope {
    public:
        Slope(int x, int y) : a(x), b(y) {
            int c = a * b;
            a = abs(a);
            b = abs(b);
            int g = 0;
            if (a > b)
                g = gcd(a, b);
            else
                g = gcd(b, a);
            a = a / g;
            b = b / g;
            if (c < 0) a = -a;
        };
        Slope() : a(0), b(0) {};

        bool operator==(const Slope &other) const
        {
            return a == other.a && b == other.b;
        }
        bool operator<(const Slope &other) const
        {
            if (a != other.a)
                return a < other.a;
            return b < other.b;
        }

    private:
        int gcd(int a, int b) {
            if (b == 0) return a;
            return gcd(b, a % b);
        }
    private:
        int a;
        int b;
};

int maxPoints(vector<Point> &points) {
    int n = points.size();
    if (n <= 2) return n;

    int ret = -1;

    for (int i = 0; i < n; ++i) {
        int cnt = 1;
        map<Slope, int> slopes;

        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            if (points[i].x == points[j].x && points[i].y == points[j].y) {
                ++cnt;
                continue;
            }

            Slope k(points[i].y - points[j].y, points[i].x - points[j].x);
            auto it = slopes.find(k);
            if (it == slopes.end())
                slopes[k] = 2;
            else
                it->second += 1;
            cnt = max(cnt, slopes[k]);
        }
        ret = max(ret, cnt);
    }
    return ret;
}

Several noteworthy points are:

  1. I degined a customized class called Slope because using double as a map or hash table key is very dangrous for the double arithmatic is inaccurate and the results could actually be unpredictable.
  2. The above code using map is implemented by red black tree, so the real time complexity is O(N^2logN), the thing I did not use unordered_map is because it seems that LeetCode OJ does not support g++ –std=c++0x option.
  3. Again, the duplicated points in the input need to be handled carefully as special cases
  4. Do not be concerned with those vertical lines, think about why.
  5. There is even more efficient implementation by only examining the current testing point against all the other points on its right side in the input points array, I actually do not fully get that idea? You are welcome to leave your comment about this!

Summary

LeetCode Max Points on a Line could be solved in O(N^2) time by find the maximum point set containing i in O(N) time (Hash) and get the maximum among all i’s.

Written on December 20, 2014