149. Max Points on a Line

leetcode hard

#array#csharp#hard#hash-table#leetcode#math

Task

Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

Output: 3

C# solution

matched/original

public class Solution {
    public int MaxPoints(int[][] points) {
        int n = points.Length;
        if (n == 1) {
            return 1;
        }
        int result = 2;
        for (int i = 0; i < n; i++) {
            Dictionary<double, int> cnt = new Dictionary<double, int>();
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    double key = Math.Atan2(points[j][1] - points[i][1],
                                            points[j][0] - points[i][0]);
                    if (cnt.ContainsKey(key)) {
                        cnt[key]++;
                    } else {
                        cnt[key] = 1;
                    }
                }
            }
            result = Math.Max(result, cnt.Values.Max() + 1);
        }
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxPoints(int[][] points) {
        int n = points.size();
        if (n == 1) {
            return 1;
        }
        int result = 2;
        for (int i = 0; i < n; i++) {
            unordered_map<double, int> cnt = new unordered_map<double, int>();
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    double key = Math.Atan2(points[j][1] - points[i][1],
                                            points[j][0] - points[i][0]);
                    if (cnt.count(key)) {
                        cnt[key]++;
                    } else {
                        cnt[key] = 1;
                    }
                }
            }
            result = max(result, cnt.Values.Max() + 1);
        }
        return result;
    }
}

Java solution

matched/original

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n == 1) {
            return 1;
        }
        int result = 2;
        for (int i = 0; i < n; i++) {
            Map<Double, Integer> cnt = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    cnt.merge(
                        Math.atan2(
                            points[j][1] - points[i][1],
                            points[j][0] - points[i][0]
                        ),
                        1,
                        Integer::sum
                    );
                }
            }
            result = Math.max(result, Collections.max(cnt.values()) + 1);
        }
        return result;
    }
}

JavaScript solution

matched/original

var maxPoints = function (points) {
    let n = points.length;
    if (n == 1) {
        return 1;
    }
    let result = 2;
    for (let i = 0; i < n; i++) {
        let cnt = {};
        for (let j = 0; j < n; j++) {
            if (j != i) {
                let key = Math.atan2(
                    points[j][1] - points[i][1],
                    points[j][0] - points[i][0],
                );
                cnt[key] = cnt[key] ? cnt[key] + 1 : 1;
            }
        }
        result = Math.max(result, Math.max(...Object.values(cnt)) + 1);
    }
    return result;
};

Python solution

matched/original

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n == 1:
            return 1
        result = 2
        for i in range(n):
            cnt = collections.defaultdict(int)
            for j in range(n):
                if j != i:
                    cnt[
                        math.atan2(
                            points[j][1] - points[i][1],
                            points[j][0] - points[i][0],
                        )
                    ] += 1
            result = max(result, max(cnt.values()) + 1)
        return result

Go solution

matched/original

func maxPoints(points [][]int) int {
    n := len(points)
    if n == 1 {
        return 1
    }
    result := 2
    for i := 0; i < n; i++ {
        cnt := make(map[float64]int)
        for j := 0; j < n; j++ {
            if j != i {
                key := math.Atan2(
                    float64(points[j][1]-points[i][1]),
                    float64(points[j][0]-points[i][0]),
                )
                cnt[key]++
            }
        }
        maxCnt := 0
        for _, v := range cnt {
            if v > maxCnt {
                maxCnt = v
            }
        }
        result = max(result, maxCnt+1)
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

1️⃣

Итерация по всем точкам:

Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов.

2️⃣

Расчёт углов и подсчёт:

Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу

3️⃣

Обновление ответа:

Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ).

😎