Max Points on a Line (Hard)

Description:

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Solution:

func maxPoints(_ points: [[Int]]) -> Int {
    var cont = 2
    var max = 2
    if (points.count < 3){
        return points.count
    }else{
        for i in 0...points.count-3{
            for j in i+1...points.count-2{
                let dx = points[i][0]-points[j][0]
                let dy = points[i][1]-points[j][1]
                for k in j+1...points.count-1{
                    if (points[i][0]-points[j][0] == 0){
                        if (points[i][0] == points[k][0]){
                            cont += 1
                        }
                    }else{
                        let y = dy * (points[k][0] - points[i][0]) + (points[i][1] * dx)
                        if ((y == dx * (points[k][1]) )){
                            cont += 1
                        }
                    }
                }
                if (cont > max){
                    max = cont
                }
                cont = 2
                
            }
            
            
        }

        return max
    }
    
    
}

Explanation

At first, this problem doesn’t look so hard, you just have to calculate the line equation, using two pints and the slope you can check if the points are the line or not. 

But the main problem is the precision of the variables and how each language calculates the divisions, you will face some cases like var a = X.0000000001. 

This problem tests your technical knowledge and not your coding abilities. 

To solve this problem we must avoid mankind’s divisions or use operators like gcd to be sure that the slope and the point are multiples. 

Using some clever math we can cheche if the point is in the line or not only using multiplications. 

Logic: 

I use a triple for because we need two different points to make a line and see if the rest are on it or not. 

The first to fors select the bigging and end pint and the third one check for the rest of the pints.

By checking if the las exportin is true we can confirm if the point is on the line

Performance

Leave a Comment

Your email address will not be published.