Max Points on a Line

This page explains Java solution to problem Max Points on a Line using Math.

Problem Statement

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class MaxPointsOnALine {
    public int maxPoints(int[][] points) {
        int max = 0;
        for(int i = 0; i < points.length; i++) {
            int[] p1 = points[i];

            HashMap<String, Integer> map = new HashMap<>();
            int overlap = 0;
            int maxInternal = 0;

            for(int j = i + 1; j < points.length; j++) {
                int[] p2 = points[j];

                int x = p1[0] - p2[0];
                int y = p1[1] - p2[1];

                if(x == 0 && y == 0) {
                    overlap++;
                    continue;
                }

                int gcd = gcd(x, y);
                if(gcd != 0) {
                    x = x / gcd;
                    y = y / gcd;
                }

                String key = x+"~"+y;
                map.put(key, map.getOrDefault(key, 0) + 1);
                maxInternal = Math.max(maxInternal, map.get(key));
            }
            max = Math.max(max, maxInternal + overlap + 1);
        }
        return max;
    }

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

Time Complexity

O(N2) Where
N is total number of points on a 2D Plane

Space Complexity

O(N) Where
N is total number of points on a 2D Plane