Leetcode 2152, minimum Number of Lines to Cover Points. Fail at when x-axis is same

Question

Here is solution that able to pass all test cases. I tried to convert it to javascript, but it fails this test case. (When 2 points have the same x-axis)

[[-4,0],[0,4],[-1,-5],[2,3],[-4,1],[-4,3],[-1,5]]

output: 4
expect: 3

If you don't have access: may have a look at this https://www.geeksforgeeks.org/minimum-lines-cover-points/

class Solution:
    def minimumLines(self, points: List[List[int]]) -> int:
        slope_calc = lambda p1, p2: (p2[1] - p1[1]) / (p2[0] - p1[0]) if p2[0] != p1[0] else math.inf

        def helper(lines, points):
            if len(points) == 0:
                return len(lines)
            
            point = points[0]
            
            
            # add to existing line            
            for p, slope in lines:
                s = slope_calc(point, p)
                if s == slope:
                    return helper(lines, points[1:])
            
            # if we have a single point and it doesn't belong to an existing
            # line, we must have another line to cover it.
            if len(points) == 1:
                return len(lines) + 1

            # creating new line in the case we have two or more points
            # (cover two at once). iterating through all possibilities.
            best = math.inf
            for i in range(1, len(points)):
                p = points[i]
                slope = slope_calc(point, p)
                lines.append((point, slope))
                best = min(best, helper(lines, points[1:i] + points[i + 1:]))
                lines.pop(-1)
            
            return best

        return helper([], points) if len(points) > 1 else 1

Here is my javascript

var cal_slope = function(p2, p1) {
    if(p2 !== p1) {
        return (p2[1] - p1[1]) / (p2[0] - p1[0]);    
    } else {
        return Number.MAX_SAFE_INTEGER;
    }
}

var dfs = function(lines, pts) {
    // base
    if(pts.length === 0) {
        return lines.length;
    }
    
    const curr_pt = pts[0];
    
    // existing can cover?
    for(let i=0; i<lines.length; ++i) {
        const line_pt = lines[i][0];
        const line_slope = lines[i][1];
        
        const new_slope = cal_slope(line_pt, curr_pt);
        if(new_slope === line_slope) {
            // can cover
            return dfs(lines, pts.slice(1));
        }
    } // el
    
    // cannot cover
    if(pts.length === 1) {
        return lines.length + 1;
    }
    
    
    let best = Number.MAX_SAFE_INTEGER;
    
    // form new slope
    for(let i=1; i<pts.length; ++i) {
        const pt = pts[i];
        const new_slope = cal_slope(pt, curr_pt);
        
        const line1 = lines.slice(0);
        line1.push([curr_pt, new_slope]);
        
        const p1 = pts.slice(1, i);
        const p2 = pts.slice(i+1);
        const newPts = [...p1, ...p2];
        
        best = Math.min(best, dfs(line1, newPts));
    } // el
    
    return best
}

var minimumLines = function(pts) {
    if(pts.length === 1) {
        return 1;    
    } else {
        return dfs([], pts);
    }
};

Answer 1

The problem is in this line:

if(p2 !== p1) {

In your use of the function, p1 and p2 are arrays with x and y coordinates. Such a comparison is only true when p1 and p2 are the same array reference. This is never the case in your use cases.

You need this (as is also the case in the Python version):

if(p2[0] !== p1[0]) {