Points on the Straight Line

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

Sample Input :

(1, 1)
(2, 2)

Sample Output :

2

You will be given 2 arrays X and Y. Each point is represented by (X[i], Y[i])

Method:

Two points are the same line if y = ax + c

Solution:

Time: O(n^2)
Space: O(n)

public class Solution {
    static class Pair {
        double x;
        double y;

        public Pair(double x, double y) {
            this.x = x;
            this.y = y;
        }
        
        @Override
        public int hashCode() {
            double hash = 17;
            hash = hash * 31 + this.x;
            hash = hash * 31 + this.y;
            return (int) hash;
        }
        
        @Override
        public boolean equals(Object o) {
            Pair p = (Pair) o;
            return p.x == this.x && p.y == this.y;
        }
    }
    
    public int maxPoints(ArrayList<Integer> a, ArrayList<Integer> b) {
        if (b.size() <= 1) return b.size();
        Map<Pair, Set<Pair>> map = new HashMap<>();
        Map<Pair, Integer> points = new HashMap<>();
        for (int i = 0; i < b.size(); i ++) {
            Pair p = new Pair(a.get(i), b.get(i));
            if (points.containsKey(p)) {
                points.put(p, points.get(p) + 1);
            } else {
                points.put(p, 1);
            }
        }
        for (int j = 1; j < b.size(); j ++) {
            for (int i = 0; i < j; i ++) {
                int Ax = a.get(i);
                int Ay = b.get(i);
                int Bx = a.get(j);
                int By = b.get(j);
                double slope = 0;
                double c = 0;
                if (Ax == Bx) {
                    // vertical line
                    slope = Double.POSITIVE_INFINITY;
                    c = Ax;
                } else if (Ay == By) {
                    // horizontal line
                    slope = 0;
                    c = Ay;
                } else {
                    slope = (double) (By - Ay) / (double) (Bx - Ax);
                    c = Ay - slope * Ax;
                }
                Pair s = new Pair(slope, c);
                Set<Pair> pairs = map.getOrDefault(s, new HashSet<Pair>());
                pairs.add(new Pair(Ax, Ay));
                pairs.add(new Pair(Bx, By));
                map.put(s, pairs);
            }
        }
        int max = 0;
        for (Map.Entry<Pair, Set<Pair>> entry : map.entrySet()) {
            Set<Pair> pairs = entry.getValue();
            int val = 0;
            for (Pair p : pairs) {
                int freq = points.get(p);
                val += freq;
            }
            max = Math.max(max, val);
        }
        return max;
    }
}