Monday, February 2, 2015

Max Points on a Line -- Leetcode

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

[Analysis]
The points on a line share the same slope: i.e. if point (x,y) is on the line formed by point (x1, y1) and (x2, y2), (y-y1) / (x-x1) = (y2-y1)/(x2-x1). For a given point, explore each slope (with other points) then we can find the result.

Corner cases to consider: 1) duplicated points; 2) points in a horizontal line, i.e. x1 = x2.

[Solution]
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        if (points.size()<3) return points.size();
     
        int num = 2;
     
        for (int i=0; i<points.size(); i++) {
            unordered_map<float, int> slopes;
            int horizonal_cnt =0;
            int same_points = 1;
            for (int j=i+1; j<points.size(); j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    same_points ++;
                }
                else
                if (points[j].x == points[i].x) {
                    horizonal_cnt++;
                }
                else {
                    float sl = (float) (points[j].y - points[i].y) / (points[j].x - points[i].x);
                    slopes[sl] ++;
                }
            }
            num = max(num, same_points);
            num = max(num, horizonal_cnt + same_points);
            for (auto pair: slopes) {
                num = max(num, pair.second + same_points);
            }
        }
        return num;
    }
};

No comments:

Post a Comment