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.

This is tough as a line can have slope. My solution is O(n^2):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//
//  main.cpp
//  Max Points on a Line
//
//  Created by Yingbo Miao on 2014-08-30.
//  Copyright (c) 2014 miao.fm. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Point {
public:
     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) {
        int ret = 0;
       
        if (points.empty()) {
            return 0;
        } else if (points.size() == 1) {
            return 1;
        }
       
        typedef unordered_map<double, int> LineCnt;
        LineCnt line_cnt;
        LineCnt::iterator it_find;
       
       
       
        double slope = std::numeric_limits<double>::infinity();
        int this_line = 0;
        int point_a_max = 0;
        int dup = 0;
        for(unsigned long i = 0; i < points.size(); ++i) {
            line_cnt.clear();
            const Point& point_a = points.at(i);
            point_a_max =  1;
            dup = 0;
            for(unsigned long j = i+1; j < points.size(); ++j) {
                if (j == i) {
                    continue;
                }
                const Point& point_b = points.at(j);
               
               
               
                if (point_b.x != point_a.x) {
                   
                    slope = double(point_b.y - point_a.y) / (point_a.x - point_b.x);
                } else {
                    if (point_b.y == point_a.y) {
                        ++dup;
                        continue;
                    }
                    slope = std::numeric_limits<double>::infinity();
                }

                it_find = line_cnt.find(slope);
               
//                cout << slope << " " << (it_find == line_cnt.end()) << endl;
               
                if (it_find == line_cnt.end()) {
                    line_cnt[slope]=2;
                    this_line = 2;
                } else {
                    //this_line = ++(it_find->second);
                    this_line = ++(line_cnt[slope]);
                   
                }
               
                if (this_line > point_a_max) {
                    point_a_max = this_line;
                }
            }
           
            point_a_max += dup;
            if (point_a_max > ret) {
                ret = point_a_max;
            }
        }
        return ret;
       
    }
};

int main(int argc, const char * argv[]) {
    vector<Point> points;
    Point point;
    point.x = 4;
    point.y = 0;
    points.push_back(point);
   
    point.x = 4;
    point.y = -1;
    points.push_back(point);
   
    point.x = 4;
    point.y = 5;
    points.push_back(point);
   
   
   
    Solution r;
    cout << r.maxPoints(points) << endl;    
}

Leave a Comment