@@ -0,0 +1,2596 @@
+package com.interview.geometry;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * Date 03/21/2016%0A * @author Tushar Roy%0A *%0A * Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.%0A *%0A * Time complexity O(n%5E2) %0A * Space complexity O(n)%0A *%0A * https://leetcode.com/problems/max-points-on-a-line/%0A */%0Apublic class MaximumPointsOnSameLine %7B%0A%0A    static class Point %7B%0A        int x;%0A        int y;%0A        Point() %7B x = 0; y = 0; %7D%0A        Point(int a, int b) %7B x = a; y = b; %7D%0A    %7D%0A%0A    class Pair %7B%0A        int a;%0A        int b;%0A%0A        @Override%0A        public boolean equals(Object o) %7B%0A            if (this == o) return true;%0A            if (o == null %7C%7C getClass() != o.getClass()) return false;%0A%0A            Pair pair = (Pair) o;%0A%0A            if (a != pair.a) return false;%0A            return b == pair.b;%0A%0A        %7D%0A%0A        @Override%0A        public int hashCode() %7B%0A            int result = a;%0A            result = 31 * result + b;%0A            return result;%0A        %7D%0A    %7D%0A%0A    public int maxPoints(Point%5B%5D points) %7B%0A        int result = 0;%0A        for (int i = 0; i %3C points.length; i++) %7B%0A            Map%3CPair, Integer%3E map = new HashMap%3C%3E();%0A            int verticalLine = 1;%0A            int onePointMax = 1;%0A            int samePoint = 0;%0A            for (int j = i + 1; j %3C points.length; j++) %7B%0A                //same point repeated again. Just increment samePoint count%0A                if (points%5Bi%5D.x == points%5Bj%5D.x && points%5Bi%5D.y == points%5Bj%5D.y) %7B%0A                    samePoint++;%0A                %7D else if (points%5Bi%5D.x == points%5Bj%5D.x) %7B //vertical line%0A                    verticalLine++;%0A                    onePointMax = Math.max(onePointMax, verticalLine);%0A                %7D else %7B%0A                    int gcd = gcd(points%5Bi%5D.y - points%5Bj%5D.y, points%5Bi%5D.x - points%5Bj%5D.x);%0A                    Pair p = new Pair();%0A                    p.a = (points%5Bi%5D.y - points%5Bj%5D.y)/gcd;%0A                    p.b = (points%5Bi%5D.x - points%5Bj%5D.x)/gcd;%0A                    int count = 2;%0A                    if (map.containsKey(p)) %7B%0A                        count = map.get(p);%0A                        count++;%0A                        map.put(p, count);%0A                    %7D else %7B%0A                        map.put(p, count);%0A                    %7D%0A                    onePointMax = Math.max(onePointMax, count);%0A                %7D%0A            %7D%0A            result = Math.max(result, onePointMax + samePoint);%0A        %7D%0A        return result;%0A    %7D%0A%0A    int gcd(int a, int b) %7B%0A        if(b==0) return a;%0A        else return gcd(b, a %25 b);%0A    %7D%0A%7D%0A

Find line with maximum points