O(n ^ 3) solution can still pass test


  • 3
    L

    Admin,

    Following code, O(n ^ 3), can still pass test. Please add more test cases. Thanks!


    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
    		int ans = 0;
    		int n = points.size();
    		
    		for (int i = 0; i < n; ++i) {
    			int dup = 0;
    			for (int j = i + 1; j < n; ++j) {
    				if (points[i].x == points[j].x && points[i].y == points[j].y) {
    					++dup;
    					continue;
    				}
    				int cnt = 2;
    				for (int k = j + 1; k < n; ++k) {
    					if ((points[k].y - points[i].y) * (points[j].x - points[i].x) ==
    						(points[j].y - points[i].y) * (points[k].x - points[i].x)) {
    						++cnt;
    					}
    				}
    				ans = max(ans, cnt + dup);
    			}
    			ans = max(ans, dup + 1);
    		}
    
    		return ans;
        }
    };

Log in to reply
 

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