4
\$\begingroup\$

The following is my submission for LeetCode's Max Points on a Line:

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1:

Leetcode reference of the example graph

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

I looked at other answers in the discussion forum and I'm not at all sure why my code runs so terribly in comparison to other answers, as it seems the general approach is the correct one(?).

enter image description here

public static int maxPoints(int[][] points) {
    Map<String, Set<int[]>> lines = new HashMap<>();
    for (int i = 0; i < points.length; i++) {
        int x1 = points[i][0];
        int y1 = points[i][1];
        for (int j = 0; j < points.length; j++) {
            if (i == j) continue;

            int x2 = points[j][0];
            int y2 = points[j][1];
            double m = x2 - x1 == 0 ? Integer.MAX_VALUE : ((double) (y2 - y1)) / (x2 - x1);
            double c = y2 - m * x2;

            String eq = m + "x+" + c;
            Set<int[]> pointsOnLine = lines.getOrDefault(eq, new HashSet<>());

            pointsOnLine.add(points[i]);
            pointsOnLine.add(points[j]);

            lines.put(eq, pointsOnLine);
        }
    }

    int max = 1;
    for (Set<int[]> value : lines.values()) {
        max = Math.max(value.size(), max);
    }
    return max;
}

I would appreciate feedback since I'm assuming I am misunderstanding/not realising how bad something that seems fairly normal to me is written.

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

Can a pair of points (i,j) yield a line that is any different to the line given by the pair of points (j,i)? Definitely not. And so you should avoid searching through all the pairs.

for (int i = 0; i < points.length - 1; i++) {
        int x1 = points[i][0];
        int y1 = points[i][1];
        for (int j = i + 1; j < points.length; j++) {
...

Which also makes the statement if (i == j) continue; useless.

The string String eq = m + "x+" + c; is probably inefficient to build and also to use as lookup. Consider making the key a tuple (m,c). I'm not sure if Java can use tuples as map keys, if not, use a map (with keys m) of maps (with keys c), or the other way around.

Also consider not converting the ratio to double, all the ratios will be integer fractions, you just have to reduce them to the simplest form. Although I'm not sure whether this will help.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks! I used a set for this reason to not double up--I barely even considered that doubling up would be as expensive as it was. And for clarification (I forgot to include it in the question), the constraints on the question included that there will always be at least one point and thus the smallest answer is one. \$\endgroup\$ Commented Nov 23, 2022 at 10:50
  • \$\begingroup\$ And to the tuple comment, I originally used a record--LinEq(double m, double c)--as a tuple but I was assuming that was the less efficient way and changed it to the string last minute! Turns out string concatenation creates a new StringBuilder object etc. anyway? Really interesting. Thanks again \$\endgroup\$ Commented Nov 23, 2022 at 10:53
  • 1
    \$\begingroup\$ Yeah I guess it could be 1 for input of 1 point, although I could argue about it :) But if that's part of specification than no argument there.... Anyway, by using a set you avoid doubling but you still process them. By halving the searched space from the beginning you literally halve the time it takes to run. \$\endgroup\$ Commented Nov 23, 2022 at 10:56
  • 1
    \$\begingroup\$ For the string I'm not quite sure how this works in Java, I would say that actually using StringBuilder should be faster then simple concatenation. But probably using map of maps with int keys could still be faster. But you better benchmark that to be sure. \$\endgroup\$ Commented Nov 23, 2022 at 10:58
  • \$\begingroup\$ Map can use any object as a key, though in some cases (this is one) you may want to implement a good hashcode() and equals() method.... \$\endgroup\$ Commented Nov 23, 2022 at 18:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.