[C++] Time Limit Exceeded Problem


  • 0
    F

    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 :
    [(29,87),(145,227),(400,84),(800,179),(60,950),(560,122),(-6,5),(-87,-53),(-64,-118),(-204,-388),(720,160),(-232,-228),(-72,-135),(-102,-163),(-68,-88),(-116,-95),(-34,-13),(170,437),(40,103),(0,-38),(-10,-7),(-36,-114),(238,587),(-340,-140),(-7,2),(36,586),(60,950),(-42,-597),(-4,-6),(0,18),(36,586),(18,0),(-720,-182),(240,46),(5,-6),(261,367),(-203,-193),(240,46),(400,84),(72,114),(0,62),(-42,-597),(-170,-76),(-174,-158),(68,212),(-480,-125),(5,-6),(0,-38),(174,262),(34,137),(-232,-187),(-232,-228),(232,332),(-64,-118),(-240,-68),(272,662),(-40,-67),(203,158),(-203,-164),(272,662),(56,137),(4,-1),(-18,-233),(240,46),(-3,2),(640,141),(-480,-125),(-29,17),(-64,-118),(800,179),(-56,-101),(36,586),(-64,-118),(-87,-53),(-29,17),(320,65),(7,5),(40,103),(136,362),(-320,-87),(-5,5),(-340,-688),(-232,-228),(9,1),(-27,-95),(7,-5),(58,122),(48,120),(8,35),(-272,-538),(34,137),(-800,-201),(-68,-88),(29,87),(160,27),(72,171),(261,367),(-56,-101),(-9,-2),(0,52),(-6,-7),(170,437),(-261,-210),(-48,-84),(-63,-171),(-24,-33),(-68,-88),(-204,-388),(40,103),(34,137),(-204,-388),(-400,-106)]

    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();
                    }
                    else
                    {
                        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
                    {
                        found->second++;
                        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.