Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

We can always draw a straight using 2 points. But can we include the third point on it? 

This can be solved by calculating the slope of the points. Three points (X1,Y1),(X2,Y2) and (X3,Y3) are co-linear if slopes of lines with any two points are the same. The slope of 2 points can be calculated by the following formula:

Point 1 = (X1,Y1) 
Point 2 = (X2,Y2)

Slope = change in Y / change in X
Slope = (Y2-Y1) / (X2-X1)

So by applying the same formula three points (X1,Y1),(X2,Y2) and (X3,Y3) are co-linear if :

The Algorithm is:

  1. Iterate over each pair of points.
  2. Calculate the slope for each pair of points, say Slope = X`/Y` = (X1 - X2 ) / (Y1 - Y2).
  3. Group all the points together which share the same slope value X`/Y`. They are co-linear or in other words, each of these groups represents a straight line.
  4. The group with maximum points is our answer. This line has a maximum number of points.
import java.util.HashMap;
import java.util.Map;

public class MaxPointInLine {

  public static int maxPoints(int[][] points) {
    if (points == null || points.length == 0) {
      return 0;
    }
    if (points.length < 3) {
      return points.length;
    }
    Map<Integer, Map<Integer, Integer>> pointCountBySlopeYBySlopeX = new HashMap<>();
    int result = 0;
    for (int i = 0; i < points.length; i++) {
      //Reset map when considering for every point
      pointCountBySlopeYBySlopeX.clear();
      int x_1 = points[i][0];
      int y_1 = points[i][1];

      //Reset overlap and max declaration to 0 when
      // considering for every fresh point
      int max = 0;
      int overlap = 0;
      for (int j = i + 1; j < points.length; j++) {
        int x_2 = points[j][0];
        int y_2 = points[j][1];

        //compute the slope numerator and denominator
        int slope_x = (x_2 - x_1);
        int slope_y = (y_2 - y_1);

        //If both x and y == 0 then both the points in consideration are same.
        // These can be duplicate or overlapping points.So increment overlap
        //and continue the loop since there is no slope for overlapping or
        // duplicate points
        if (slope_x == 0 && slope_y == 0) {
          overlap++;
          continue;
        }
        //Compute the gcd of x and y; so that 2/4 is considered same as 1/2
        int gcd = generateGCD(slope_x, slope_y);
        if (gcd != 0) {
          slope_x = slope_x / gcd;
          slope_y = slope_y / gcd;
        }

        Map<Integer,Integer> pointCountBySlopeY = pointCountBySlopeYBySlopeX.get(slope_x);
        if (pointCountBySlopeY == null) {
          pointCountBySlopeY = new HashMap < > ();
          pointCountBySlopeYBySlopeX.put(slope_x, pointCountBySlopeY);
        }
        Integer count = pointCountBySlopeY.get(slope_y);
        if (count == null) {
          count = 1;
          pointCountBySlopeY.put(slope_y, count);
        } else {
          count = count + 1;
          pointCountBySlopeY.put(slope_y, count);
        }
        //Local max
        max = Math.max(max, count);
      }
      //global maximum
      result = Math.max(max + overlap + 1, result);
    }
    return result;
  }

  private static int generateGCD(int a, int b) {
    if (b == 0) return a;
    else return generateGCD(b, a % b);
  }

  public static void main(String[] args) {
	int[][] points = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
	System.out.println(maxPoints(points));
  }
}
  • Time Complexity: O(N2)
  • Space ComplexityO(N) to track down not more than N - 1 lines.
Arrays Algorithm