149. Max Points on a Line

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

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.

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn max_points(points: Vec<Vec<i32>>) -> i32 {
        let n = points.len();
        if n == 0 {
            return 0;
        }
        let mut res = 1;
        for i in 0..n {
            res = res.max(Self::from_point(i, &points));
        }
        res as i32
    }

    fn from_point(i: usize, points: &[Vec<i32>]) -> usize {
        let n = points.len();
        let x1 = points[i][0];
        let y1 = points[i][1];
        let mut hm: HashMap<(i32, i32), usize> = HashMap::new();
        let mut origin = 0;
        for j in 0..n {
            let x2 = points[j][0];
            let y2 = points[j][1];
            let mut dx = x2 - x1;
            let mut dy = y2 - y1;
            if dx == 0 && dy == 0 {
                origin += 1;
            } else {
                if dx == 0 {
                    *hm.entry((0, 1)).or_default() += 1;
                    continue;
                }
                if dy == 0 {
                    *hm.entry((1, 0)).or_default() += 1;
                    continue;
                }
                if dy < 0 {
                    dy *= -1;
                    dx *= -1;
                }
                let z = Self::gcd(dx, dy);
                dy /= z;
                dx /= z;
                *hm.entry((dx, dy)).or_default() += 1;
            }
        }
        hm.values().max().unwrap_or(&0) + origin
    }

    fn gcd(mut m: i32, mut n: i32) -> i32 {
        while m != 0 {
            let temp = m;
            m = n % temp;
            n = temp;
        }
        n.abs()
    }
}

#[test]
fn test() {
    let points = vec_vec_i32![[1, 1], [2, 2], [3, 3]];
    let res = 3;
    assert_eq!(Solution::max_points(points), res);
    let points = vec_vec_i32![[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]];
    let res = 4;
    assert_eq!(Solution::max_points(points), res);
}

Having problems with this solution? Click here to submit an issue on github.