TLE for O(n^2) solution. May anyone help me to optimize it?


  • 1
    H

    I have got a TLE error on my solution. Why? Too many integer multiplying?
    Introduction to algorithm: The line in X-Y dimension can be expressed as ax+by+c=0, where a is (y0-y1), b is (x1-x0) and c is (x0y1-x1y0).
    If two lines are the same, there must be a1/a2==b1/b2==c1/c2. That's implemented in the Equals function of class Triple.

    I've got (a,b,c) triple for each line determined by two points in the given array. Then I calculated the count of each "equal" triple. The maximum count is the return value.

    But I've got a TLE error.

    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
        public int maxPoints(Point[] points) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            class Triple
            {
                //Line can be expressed as ay+bx+c = 0
                private int a,b,c;
                public Triple(int va, int vb, int vc)
                {
                   
                    a = va; b = vb; c = vc;
                   
                }
                public boolean Equal(Triple in)
                {
                    //If two lines equal, then a1*b2 = a2*b1 && a1*c2= a2*c1 
                    return in.a*b == in.b*a && in.a*c == in.c*a;
                }
            }
            int nLineCount = points.length*(points.length-1)/2;
            Triple lineTriple[] = new Triple[nLineCount];
            int nIdx = 0;
            for(int i = 0; i < points.length; i++)
            {
                for(int j = i+1; j < points.length; j++)
                {
                    //Calculate the triple for the line
                    lineTriple[nIdx] = new Triple(points[j].x-points[i].x,
                        points[i].y-points[j].y,
                        points[i].x*points[j].y-points[j].x*points[i].y  );
                    nIdx++;
                }
            }
    
            //aCnt is the array containing the count of corresponding line lineTriple
            // or -1 if it is the same line with a line before it. 
            int aCnt[] = new int[nLineCount];
            for(int i = 0; i < nLineCount; i++)
            {
                aCnt[i] = 1;
            }
            int nMax = 1;
            for(int i = 0; i < nLineCount; i++)
            {
               
                if(aCnt[i] == -1) continue;
                for(int j = i+1; j < nLineCount; j++)
                {
                    if(aCnt[j] != -1 && lineTriple[j].Equal(lineTriple[i]) )
                    {
                        aCnt[i]++;
                        //Set aCnt[j] to -1 to avoid re-calculate it in outer cycle.
                        aCnt[j] = -1;
                    }
                }
                if(aCnt[i] > nMax)
                {
                    nMax = aCnt[i];
                }
            }
            return nMax;
        }
    }

  • 0
    S

    Could you please update your post? Telling some words about your algorithm, making comments in your code. People barely help on raw code. Thanks.


  • 0
    H

    Thank you. I've updated my question and commented the code.


  • 1
    S

    Your solution is not O(n^2) but O(n^3). You saved all possible lines make of 2 points, the scale is already O(n^2). Then, you enumerate all lines to count how many points on the line, the whole process is O(n^3).

    A good solution is using hash to count same lines, complexity is O(n^2). You can find some hint in the discuss of this problem.


  • 0
    D

    If using hash, complexity is O(n^2)?I think they are the same ==> O(n^3)


  • 0
    S

    No, the find method of hash can consider as O(1) or O(log N), it depends which collector you use.


Log in to reply
 

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