My code seems to work on VS2013, but got Time Limit Exceeded.


  • 0
    Z

    My submission is not accepted because time limit exceeded.
    What I am doing is actually fairly simple and takes O(N^2) time. I simply look at each pair of points and add then hash them according to slope and intercept.

    I have seen other people's people O(N^2) algorithm accepted? What is the problem that got me rejected?

    double impossible = -99999;
    
    struct Point {
    	int x;
    	int y;
    	Point() : x(0), y(0) {}
    	Point(int a, int b) : x(a), y(b) {}
    
    };
    
    double getSlope(Point A, Point B){
    	if (B.x == A.x){
    		return impossible;
    	}
    	else{
    		return (B.y - A.y) / (B.x - A.x);
    	}
    }
    
    double getIntercept(Point A, Point B){
    	if (B.x == A.x){
    		return impossible;
    	}
    	else{
    		return (A.x * B.y - B.x * A.y) / (A.x - B.x);
    	}
    }
    
    int maxPoints(vector<Point> &points) {
    	map<tuple<double, double>, vector<Point*>> map;\
    	int max = 0;
    	for (int i = 0; i < points.size(); i++){
    		for (int j = 0; j < i; j++){
    			double slope = getSlope(points[i], points[j]);
    			double cept = getIntercept(points[i], points[j]);
    			tuple<double, double> tmp(slope, cept);
    			vector<Point*> tmpVal;
    			if (map.find(tmp) == map.end()){
    				tmpVal.push_back(&points[i]);
    				tmpVal.push_back(&points[j]);
    				map[tmp] = tmpVal;
    			}
    			else{
    				tmpVal = map[tmp];
    				if (std::find(tmpVal.begin(), tmpVal.end(), &points[i]) == tmpVal.end()){
    					tmpVal.push_back(&points[i]);
    				}
    				if (std::find(tmpVal.begin(), tmpVal.end(), &points[j]) == tmpVal.end()){
    					tmpVal.push_back(&points[j]);
    				}
    				map[tmp] = tmpVal;
    			}
    			max = tmpVal.size() > max ? tmpVal.size() : max;
    		}
    	}
    	return max;
    }

  • 0
    M

    Your code is not O(N^2) algorithm.

    because using std::find function, this is over O(N^2)


Log in to reply
 

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