Can someone spot the bug? passing 26/27 test cases, getting wrong output on last test


  • 0
    P
    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    bool point_comp(Point& a, Point& b) {
        return a.x < b.x;
    }
    
    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            int n = points.size();
            if (n == 0 || n == 1) {
                return n;
            }
            
            sort(points.begin(), points.end(), point_comp);
            unordered_map<double,int> main_map;
            int max_vertical = INT_MIN;
            for (int i = 0; i < n; ++i ) {
                Point& p1 = points[i];
                int vertical = 0;
                // corner case where the same point occurs more than once
                // each slope then increases by the number it repeats
                int same_point_count = 1;
                unordered_map<double, int> aux_map;
                for (int j = i+1; j < n; ++j) {
                    Point& p2 = points[j];
                    if (p1.x == p2.x && p1.y == p2.y) {
                        same_point_count++;
                        vertical++;
                    } else if (p1.x == p2.x) {
                        vertical++;
                    } else {
                        double m = (double)(p2.y-p1.y)/(p2.x-p1.x);
                        if (main_map.find(m) == main_map.end()) {
                            if (aux_map.find(m) == aux_map.end()) {
                                aux_map[m] = same_point_count;
                            }
                            aux_map[m]++;
                        }
                    }
                }
                main_map.insert(aux_map.begin(), aux_map.end());
                aux_map.clear();
                if (max_vertical < vertical && vertical > 0) {
                    max_vertical = vertical+1;
                }
            }
            
            int max = INT_MIN;
            for (unordered_map<double, int>::iterator it = main_map.begin(); it != main_map.end(); ++it) {
                if (max < it->second) {
                    max = it->second;
                }
            }
            return max > max_vertical ? max : max_vertical;
        }
    };

  • 0
    P

    The logic is : sort the points w.r.t. x, for each point i, caclulate all m values with points after that in the sorted list. So for point i, you will get all m values with number of points that make a line segment of m slope. Once done with point i, add it to the main map so that we wont consider points on the same line again for later points. Only add points if the m has not been seen before because if we get m that we have seen before then a another point would have taken all points , so no need to add again.


  • 1
    N

    I think the algorithm does work, but be careful with the double or float numbers, their precision are not so reliable in some conditions.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.