Am I misinterpreting the problem?


  • 0
    M

    My code is hitting a time limit exceeded, but I don't see a way to do this with any fewer loops. I took a look at some of the other solutions in the discussions here and they do not seem to be solving the same question/problem in my eyes, so then I'm wondering if I am misinterpreting the question?

    In my interpretation of the question, we need to iterate over all possible combinations of end points and then look at the remaining points and count how many would fall on the line defined by the end points. If that number exceeds the maximum count so far, we update the maximum count. Then we choose two new end points and repeat. So it is an O(n^3) problem by nature.

    I have posted my code below. I added the map to add some caching to try and eliminate the time exceeded, but it still exceeds the time.

    Am I misinterpreting the question/problem?

    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            if(points.size() < 3) {
                return points.size();
            }
            int maxCount = 0;
            // choose two points and then given those two points, iterate over all
            // of the others and count how many would be on the line given by the
            // two chosen points.  if that count is greater than the max count so
            // far, update the max count.
            for(size_t i = 0; i < points.size(); i++) {
                for(size_t j = 0; j < points.size(); j++) {
                    if(i != j) {
                        int count = 0;
                        for(size_t k = 0; k < points.size(); k++) {
                            if ((k != i) && (k != j))
                            {
                                if(onLineMap.find(tuple<int,int,int>(i,j,k)) != onLineMap.end()) {
                                    if(onLineMap[tuple<int,int,int>(i,j,k)]) {
                                        count++;
                                    }
                                }
                                else if(onLineMap.find(tuple<int,int,int>(i,k,j)) != onLineMap.end()) {
                                    if(onLineMap[tuple<int,int,int>(i,k,j)]) {
                                        count++;
                                    }
                                }
                                else if(onLineMap.find(tuple<int,int,int>(j,i,k)) != onLineMap.end()) {
                                    if(onLineMap[tuple<int,int,int>(j,i,k)]) {
                                        count++;
                                    }
                                }
                                else if(onLineMap.find(tuple<int,int,int>(j,k,i)) != onLineMap.end()) {
                                    if(onLineMap[tuple<int,int,int>(j,k,i)]) {
                                        count++;
                                    }
                                }
                                else if(onLineMap.find(tuple<int,int,int>(k,i,j)) != onLineMap.end()) {
                                    if(onLineMap[tuple<int,int,int>(k,i,j)]) {
                                        count++;
                                    }
                                }
                                else if(onLineMap.find(tuple<int,int,int>(k,j,i)) != onLineMap.end()) {
                                    if(onLineMap[tuple<int,int,int>(k,j,i)]) {
                                        count++;
                                    }
                                }
                                else {
                                    if(onLine(points[i], points[j], points[k])) {
                                        onLineMap[tuple<int,int,int>(i,j,k)] = true;
                                        count++; 
                                    } else {
                                        onLineMap[tuple<int,int,int>(i,j,k)] = false;
                                    }
                                }
    
                            }
                        }
                        if(count > maxCount ) {
                            maxCount = count;
                        }
                    }
                }
            }
            return maxCount;
        }
    
        bool onLine(const Point& a, const Point& b, const Point& p) {
            if(a.x == b.x) {
                // vertical
                if(p.x == a.x) {
                    return true;
                }
            } else if (a.y == b.y) {
                // horizontal
                if(p.y == a.y) {
                    return true;
                }
            } else {
                double m = (b.y - a.y) / (b.x - a.x);
                // y = mx + b
                // b = y - mx
                double b = a.y - m * a.x;
                return (p.y == ((m * p.x) + b));
            }
        }
    
        map<tuple<int, int, int>, bool> onLineMap;
    };

  • 2
    S

    You understand the question correctly and your solution is valid. However, with a slightly more clever thinking, the running time can be brought down to O(n^2): For each point pi, calculate the slope of each line it forms with all other points with greater indices, i.e. pi+1, pi+2, ..., and use a hashtable to record how many lines have the same slope (If two lines have the same slope and share a common point, then the two lines must be the same one). By doing so, you can easily find how many points are on the same line that ends at pi in O(n).Thus the amortized running time of the whole algorithm is O(n^2). Of course, you also need to handle two special cases: (1) when two points are on a vertical line, i.e. slope = INF; (2) when two points are the same.


  • 0
    M

    Ok, thank you for this thought. I will think about it and then try again.


Log in to reply
 

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