Algorithm


Problem Name: 149. 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:

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

Example 2:

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

 

Constraints:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • All the points are unique.
 

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct slope_s {
    int x;
    int y;
    int n;
    struct slope_s *next;
} slope_t;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int maxPoints(struct Point* points, int pointsSize) {
    int i, j, k, s, v, m;
    int x, y, d;
    slope_t *list, *tail, *buff, *node;
    
    m = 0;
    list = tail = buff = NULL;
    for (i = 0; i  <  pointsSize; i ++) {
       k = s = v = 0;
       if (tail != NULL) tail->next = buff;
       buff = list;
       list = tail = NULL;
       for (j = i + 1; j  <  pointsSize; j ++) {
         x = points[j].x - points[i].x;
         y = points[j].y - points[i].y;
         if (x == 0) {
              if (points[j].y == points[i].y) {
                  s ++;
             } else {
                  v ++;
             }
             } else {
              d = gcd(y, x); // greatest common divider
              x = x / d;
              y = y / d;
              node = list;
              while (node && (node->x != x || node->y != y)) node = node-> next;
              if (node) node->n ++;
              else {
                  if (buff) {
                     node = buff;
                     buff = buff->next;
                 } else {
                     node = malloc(sizeof(slope_t));
                     //assert(node);
                 }
                  node->x = x;
                  node->y = y;
                  node->n = 1;
                  if (!tail) {  // first node of the list
                     node->next = NULL;  // cut if off from buff
                     list = tail = node;
                 } else {
                     node->next = list;  // chain it to the list
                     list = node;
                 }
             }
             }
         }
       if (k  <  v + s) k = v + s;
       node = list;
       while (node) {
         if (k  <  node->n + s) k = node->n + s;
         node = node->next;
         }
       k ++;
    
       if (m  <  k) m = k;
     }
    
    while (list) {
       node = list;
       list = list->next;
       free(node);
     }
    
    while (buff) {
       node = buff;
       buff = buff->next;
       free(node);
     }
    
    return m;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
points = [[1,1],[2,2],[3,3]]

Output

x
+
cmd
3

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int maxPoints(int[][] points) {
    int max = 0;
    for (int i = 0; i  <  points.length - 1; i++) {
      Map map = new HashMap<>();
      for (int j = i + 1; j  <  points.length; j++) {
        double slope = calculateSlope(points[i], points[j]);
        map.put(slope, map.getOrDefault(slope, 0) + 1);
        max = Math.max(max, map.get(slope));
      }
    }
    return max + 1;
  }
  
  private double calculateSlope(int[] p1, int[] p2) {
    double y = (p2[1] - p1[1]) * 1.0;
    double x = (p2[0] - p1[0]) * 1.0;
    if (x == 0) {
      return Double.NaN;
    }
    if(y == 0) {
      return 0.0;
    }
    return ((double) y * 1.0) / x;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
points = [[1,1],[2,2],[3,3]]

Output

x
+
cmd
3

#3 Code Example with Javascript Programming

Code - Javascript Programming


const maxPoints = function (points) {
  if (points.length < 2 || points == null) return points.length
  let max = 2
  for (let i = 0; i  <  points.length; i++) {
    let [p1x, p1y] = points[i]
    let samePoint = 1,
      map = { base: 0 } // to avoid when map = {}, the max value is -Infinity
    for (let j = i + 1; j  <  points.length; j++) {
      if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
        samePoint++
      } else {
        let [p2x, p2y] = points[j]
        let slope = (1000000.0 * (p2y - p1y)) / (p2x - p1x)
        if (!Number.isFinite(slope)) slope = 'v'
        else if (Number.isNaN(slope)) slope = 'h'
        map[slope] = map[slope] + 1 || 1
      }
    }
    max = Math.max(Math.max(...Object.values(map)) + samePoint, max)
  }
  return max
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Output

x
+
cmd
4

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def maxPoints(self, points):
        m, res, roots = {}, 0, set()
        for i, p1 in enumerate(points):
            if (p1.x, p1.y) not in roots:
                roots.add((p1.x, p1.y))
                m.clear()
                dup = path = 0
                for j, p2 in enumerate(points):
                    if i != j:
                        try:
                            cur = (p1.y - p2.y) * 100 / (p1.x - p2.x)
                        except:
                            if p1.y == p2.y:
                                dup += 1
                                continue
                            else:
                                cur = "ver"
                        m[cur] = m.get(cur, 0) + 1
                        if m[cur] > path:
                            path = m[cur]
                if path + dup + 1 > res:
                    res = path + dup + 1
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Output

x
+
cmd
4
Advertisements

Demonstration


Previous
#148 Leetcode Sort List Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#150 Leetcode Evaluate Reverse Polish Notation Solution in C, C++, Java, JavaScript, Python, C# Leetcode