LeetCode - Algorithms - 149. Max Points on a Line

Problem

149. Max Points on a Line

Java

1

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

class Solution {    
    public int maxPoints(int[][] points) {
        int n = 0;
        for (int i = 0; i < points.length; i++) {
            int m = maxCollinearPoints(points, i);
            if (m > n)
                n = m;
        }
        return n;        
    }
    
    private int maxCollinearPoints(int[][] points, int idx) {
        Map<BigDecimal, Integer> map = new HashMap<BigDecimal, Integer>();
        int x0 = points[idx][0];
        int y0 = points[idx][1];
        int x = 0, y = 0;
        int duplicate = 1;
        int vertical = 0;
        for (int i = 0; i < points.length; i++) {
            if (i != idx) {
                x = points[i][0];
                y = points[i][1];
                if (x == x0) {
                    if (y == y0) {
                        duplicate++;
                    }
                    else {
                        vertical++;
                    }
                } else {
                    BigDecimal deltaY = BigDecimal.valueOf(y - y0);
                    BigDecimal deltaX = BigDecimal.valueOf(x - x0);
                    BigDecimal slope = deltaY.divide(deltaX, 16, RoundingMode.FLOOR);
                    if (map.containsKey(slope)) {
                        map.put(slope, map.get(slope) + 1);
                    } else {
                        map.put(slope, 1);
                    }
                }

            }
        }
        int max = 0;
        for (Integer num : map.values()) {
            if (num + duplicate > max)
                max = num + duplicate;
        }
        if ( (vertical + duplicate) > max )
            max = vertical + duplicate;
        return max;
    }
}

Submission Detail

  • 41 / 41 test cases passed.
  • Runtime: 14 ms, faster than 72.08% of Java online submissions for Max Points on a Line.
  • Memory Usage: 39.6 MB, less than 41.21% of Java online submissions for Max Points on a Line.

programcreek

© https://www.programcreek.com/2014/04/leetcode-max-points-on-a-line-java/

This problem can be solve by counting points that have the same slope for each point. When counting, we need to be careful about the duplicate points and points on the vertical lines.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

class Solution {    
    public int maxPoints(int[][] points) {
        HashMap<BigDecimal, Integer> result = new HashMap<BigDecimal, Integer>();
        int max = 0;

        for (int i = 0; i < points.length; i++) {
            int duplicate = 1;
            int vertical = 0;
            for (int j = i + 1; j < points.length; j++) {
                //handle duplicates and vertical
                if (points[i][0] == points[j][0]) {
                    if (points[i][1] == points[j][1]) {
                        duplicate++;
                    } else {
                        vertical++;
                    }
                } else {
                    BigDecimal slope =
                            points[j][1] == points[i][1] ? BigDecimal.valueOf(0.0) : BigDecimal.valueOf(1.0 * (points[j][1] - points[i][1])).divide(BigDecimal.valueOf(points[j][0] - points[i][0]), 16,
                                            RoundingMode.FLOOR);
                    if (result.get(slope) != null) {
                        result.put(slope, result.get(slope) + 1);
                    } else {
                        result.put(slope, 1);
                    }
                }
            }

            for (Integer count : result.values()) {
                if (count + duplicate > max) {
                    max = count + duplicate;
                }
            }

            max = Math.max(vertical + duplicate, max);
            result.clear();
        }

        return max;       
    }
}

Submission Detail

  • 41 / 41 test cases passed.
  • Runtime: 25 ms, faster than 42.00% of Java online submissions for Max Points on a Line.
  • Memory Usage: 40.4 MB, less than 20.64% of Java online submissions for Max Points on a Line.