Max points on a line

Array Hash Table Math Geometry

30.3% acceptance

Jan 12, 2026

4505

582

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_points(points: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashMap;
    
    let n = points.len();
    if n <= 2 {
      return n as i32;
    }
    
    fn gcd(mut a: i32, mut b: i32) -> i32 {
      while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
      }
      a.abs()
    }
    
    let mut max_count = 0;
    
    for i in 0..n {
      let mut slopes: HashMap<(i32, i32), i32> = HashMap::new();
      let mut same = 1;
      let mut local_max = 0;
      
      for j in i + 1..n {
        let mut dx = points[j][0] - points[i][0];
        let mut dy = points[j][1] - points[i][1];
        
        if dx == 0 && dy == 0 {
          same += 1;
          continue;
        }
        
        let g = gcd(dx, dy);
        dx /= g;
        dy /= g;
        
        // Normalize the slope to ensure consistent representation
        if dx < 0 {
          dx = -dx;
          dy = -dy;
        } else if dx == 0 && dy < 0 {
          dy = -dy;
        }
        
        let slope = (dx, dy);
        *slopes.entry(slope).or_insert(0) += 1;
        local_max = local_max.max(slopes[&slope]);
      }
      
      max_count = max_count.max(same + local_max);
    }
    
    max_count
  }
}