[C++] Time Limit Exceeded Problem

  • 0

    Hi could someone please help me?

    I first use two loops to iterate each pair of points, and calculate the slope m and intercept b to get the line y=mx+b. Then I represent each as a string. EX: y=2x+3 ==> "m2b3"

    During the iteration, I store the lines in a hash table where the key is the string representing the line and the value is a counter that counts how many time the line appears.

    I think the way I do should only have O(n^2) time complexity, but the result is "Time Limit Exceeded". I don't know where does my code go wrong. The only thing I can guess is that there are too many collisions in my hash table and slow down the program. Could someone please help me? Thanks a lot.

    Lastly, the last executed input is :

    int maxPoints(vector<Point> &points) {
            unordered_map<string, int> hashPoints; //record how many times the lines appear
            int maxPointInALine = -1;
            if(points.size() < 2)
                return points.size();
            for(int i=0; i<points.size(); i++)
                for(int j=i+1; j<points.size(); j++)
                    double m,b;
                    string line = "";
                    ostringstream osline;
                    //calculate the slope m and the intercept b for line y=mx+b
                    if(points[i].x == points[j].x) // vertical line
                        osline << "mINFINITEx" << points[i].x;
                        line = osline.str();
                        m = (double)(points[i].y - points[j].y) / (double)(points[i].x - points[j].x);
                        b = (double)points[i].y - m * (double)points[i].x;
                        osline << "m" << m << "b" << b;
                        line = osline.str();
                    //use a string to represent each unique line
                    unordered_map<string, int>::iterator found = hashPoints.find(line);
                    int numPoints;
                    if(found!=hashPoints.end())//if the line exists, increment the counter
                        numPoints = found->second;
                    else    //if the line does not exist, inset into the hash table and set the counter to 1
                        hashPoints[line] = 1;
                        numPoints = 1;
                    //update the number of max points within a line
                    if(numPoints > maxPointInALine)
                        maxPointInALine = numPoints;

Log in to reply

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