[LeetCode] 149. Max Points on a Line

Posted on | In

Problem

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

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o
+------------->
0  1  2  3  4

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Explanation

  1. This method use a hash map of key equals to slope and value equals to number of point on that slope to solve. We can use two for loops. First, we fix a number, then we find this number with every other number’s slope and put the slope and increment the hashmap’s corresponding slope’s value.

  2. Some special case is if two points has same x value, it means they have the maximum slope. If two points have the same position, then we increment the duplicate. We need to clear the map and reset dupliate and tempMax in each fix point.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    double getSlope(int[] a, int[] b) {
        if (a[0] == b[0]) return Double.MAX_VALUE;
        return 10 * (double) (a[1] - b[1]) / (double) (a[0] - b[0]); // multiple 10 to avoid overflow
    }

    public int maxPoints(int[][] points) {
        if (points == null || points.length == 0) return 0;
        int res = 1;
        Map<Double, Integer> slopeFreq = new HashMap<>();

        for (int i = 0; i < points.length; i++) {
            int duplicate = 1;
            int tempMax = 0;
            double slope = 0;
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
                    duplicate += 1;
                } else {
                    slope = getSlope(points[i], points[j]);
                    slopeFreq.put(slope, slopeFreq.getOrDefault(slope, 0) + 1);
                    tempMax = Math.max(tempMax, slopeFreq.get(slope));
                }
            }
            slopeFreq.clear();
            res = Math.max(res, tempMax + duplicate);
        }

        return res;
    }
}