Solution For Max Points On A Line

The problem “Max Points on a Line” on LeetCode asks us to find the maximum number of points that are located on the same line given an array of points.

Approach: We can use a hashmap to store the slope of the line between each point and count the maximum number of points on the same line.

Algorithm:

1. Create a hashmap named as slopes, which will store the slope(value) of each point(key) in the given points array.

2. Iterate through each point in the given points array.

3. Initialize two counters, one for the duplicate points and the other for the maximum number of points on the same line containing the current point.

4. For each point, iterate through the remaining points in the array and calculate the slope of the line passing through the current point and the remaining point.

5. If the current point is same as the remaining point, then increment the duplicate points counter.

6. If the slope does not exist in the hashmap, then add it along with the count 2 (the current point and the remaining point).

7. If the slope already exists in the hashmap, then increment its count by 1.

8. Update the maximum number of points by comparing the current number of points with the maximum number of points so far.

9. Repeat steps 4-8 for each point in the given array.

10. Return the maximum number of points on the same line.

Code:

Here is the Java implementation of the above algorithm:

class Solution {
public int maxPoints(int[][] points) {
if (points.length == 0)
return 0;
int maxPoints = 1;
for(int i = 0; i < points.length; i++){
Map slopes = new HashMap<>();
int count = 1;
for(int j = i+1; j < points.length; j++){
int x1 = points[i][0];
int x2 = points[j][0];
int y1 = points[i][1];
int y2 = points[j][1];
if (x1 == x2 && y1 == y2) {
count++;
continue;
}
double k = (x1 == x2) ? Double.POSITIVE_INFINITY :
((double) (y2-y1) / (double) (x2-x1));
if (slopes.containsKey(k)) {
slopes.put(k, slopes.get(k)+1);
} else {
slopes.put(k, 2);
}
}
if (slopes.isEmpty()) {
maxPoints = Math.max(maxPoints, count);
} else {
for (int value: slopes.values()) {
maxPoints = Math.max(maxPoints, count+value-1);
}
}
}
return maxPoints;
}
}

Time Complexity: O(n^2) – As we need to traverse all the points and for each point, we need to traverse the remaining points.

Space Complexity: O(n) – As we are using a hashmap of space proportional to the number of points in the given array.

Step by Step Implementation For Max Points On A Line

/**
 * 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) {
        if (points == null || points.length == 0) return 0;
        if (points.length == 1) return 1;
        int max = 0;
        for (int i = 0; i < points.length - 1; i++) {
            Point p1 = points[i];
            int duplicate = 1;
            int localMax = 0;
            HashMap map = new HashMap();
            for (int j = i + 1; j < points.length; j++) {
                Point p2 = points[j];
                if (p1.x == p2.x && p1.y == p2.y) {
                    duplicate++;
                    continue;
                }
                double slope = 0.0;
                if (p1.x == p2.x) {
                    slope = Double.MAX_VALUE;
                } else {
                    slope = 1.0 * (p2.y - p1.y) / (p2.x - p1.x) + 0.0;
                }
                if (map.containsKey(slope)) {
                    map.put(slope, map.get(slope) + 1);
                } else {
                    map.put(slope, 1);
                }
                localMax = Math.max(localMax, map.get(slope));
            }
            max = Math.max(max, localMax + duplicate);
        }
        return max;
    }
}

def maxPoints(self, points):
        # create a map of slopes to count of points with that slope
        # for each point, iterate over all other points and calculate slope
        # if slope is the same, increment count for that slope
        # keep track of max count
        # time complexity: O(n^2), space complexity: O(n)
        
        slope_map = {}
        max_count = 0
        
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                # calculate slope
                # use float to avoid integer division
                slope = (points[j][1] - points[i][1]) / float((points[j][0] - points[i][0]))
                # use defaultdict to handle case where slope is not in map
                slope_map[slope] = slope_map.get(slope, 0) + 1
                # update max count
                max_count = max(max_count, slope_map[slope])
        
        return max_count

/**
 * @param {number[][]} points
 * @return {number}
 */
 
 // Solution:
 
 var maxPoints = function(points) {
    
    // edge case: if there are less than 3 points, then the max number of points on a line is equal to the number of points
    if (points.length < 3) {
        return points.length;
    }
    
    // create a map to store the slope of each line
    // the key is the slope, and the value is the number of points on that line
    let map = {};
    
    // create a variable to keep track of the max number of points on a line
    let max = 0;
    
    // iterate through each point
    for (let i = 0; i < points.length; i++) {
        
        // set the number of points on a line to 1 for each point
        let numPoints = 1;
        
        // iterate through each other point
        for (let j = i + 1; j < points.length; j++) {
            
            // calculate the slope of the line between the current point and the other point
            let slope = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]);
            
            // if the slope is not a number, set it to 0
            if (isNaN(slope)) {
                slope = 0;
            }
            
            // if the slope is already in the map, increment the number of points on that line
            if (map[slope]) {
                numPoints++;
            } 
            // otherwise, set the number of points on that line to 2
            else {
                numPoints = 2;
            }
            
            // update the map with the new slope and number of points
            map[slope] = numPoints;
            
            // update the max if necessary
            if (numPoints > max) {
                max = numPoints;
            }
        }
    }
    
    // return the max
    return max;
};

class Solution {
public:
    int maxPoints(vector& points) {
        int n = points.size();
        if (n <= 2) return n;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            map, int> mp;
            int same = 1;
            for (int j = i + 1; j < n; ++j) {
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    ++same;
                    continue;
                }
                int dx = points[i].x - points[j].x;
                int dy = points[i].y - points[j].y;
                int d = gcd(dx, dy);
                ++mp[{dx / d, dy / d}];
            }
            res = max(res, same);
            for (auto it : mp) {
                res = max(res, it.second + same);
            }
        }
        return res;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

/**
 * 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) {
        // check for edge cases
        if (points == null || points.Length == 0) {
            return 0;
        }
 
        // map to store the slope and number of points with same slope
        Dictionary map = new Dictionary();
 
        // max number of points on a line passing through a point
        int maxPoints = 1;
 
        // loop through all points
        for (int i = 0; i < points.Length; i++) {
            // reset map
            map.Clear();
 
            // current point
            Point p1 = points[i];
 
            // number of points with same x coordinate as p1
            int sameX = 1;
 
            // number of points with same y coordinate as p1
            int sameP = 0;
 
            // loop through all points again
            for (int j = i + 1; j < points.Length; j++) {
                // current point
                Point p2 = points[j];
 
                // if p1 and p2 have the same x coordinate
                if (p1.x == p2.x) {
                    // if p1 and p2 have the same y coordinate
                    if (p1.y == p2.y) {
                        // increment sameP
                        sameP++;
                    }
                    // otherwise, increment sameX
                    else {
                        sameX++;
                    }
                }
                // if p1 and p2 have different x coordinates
                else {
                    // calculate slope
                    double slope = (double)(p1.y - p2.y) / (double)(p1.x - p2.x);
 
                    // if slope is not in map, add it with value 1
                    if (!map.ContainsKey(slope)) {
                        map.Add(slope, 1);
                    }
                    // otherwise, increment the value
                    else {
                        map[slope]++;
                    }
                }
            }
 
            // update maxPoints
            maxPoints = Math.Max(maxPoints, sameX);
 
            // add points with same slope
            foreach (int value in map.Values) {
                maxPoints = Math.Max(maxPoints, value + sameP);
            }
        }
 
        return maxPoints;
    }
}