26 Aug 2025•PHP•Hard

Max Points on a Line

find maximum number of points that lie on the same line using slope calculation and hash map.

for each point, calculate slopes to all other points. use a hash map to count points with the same slope. handle vertical lines and duplicates separately.

use gcd to normalize slopes to avoid floating point precision issues. the maximum count for any point gives the answer.

key points

normalize slopes using gcd to avoid precision issues
handle vertical lines (infinite slope) separately
count duplicate points separately
for each point, find max collinear points

complexity

O(n²) time where n is number of points. O(n) space for the slope map.

Solution files

PHP•max-points-on-line/solution.php

class Solution {

function maxPoints($points) {
    $n = count($points);
    if ($n <= class="syntax-number">2) return $n;
    
    $maxPoints = class="syntax-number">1;

    for ($i = class="syntax-number">0; $i < $n; $i++) {
        $slopes = [];
        $duplicate = class="syntax-number">0;
        $currentMax = class="syntax-number">0;

        for ($j = $i + class="syntax-number">1; $j < $n; $j++) {
            $dx = $points[$j][class="syntax-number">0] - $points[$i][class="syntax-number">0];
            $dy = $points[$j][class="syntax-number">1] - $points[$i][class="syntax-number">1];

            if ($dx == class="syntax-number">0 && $dy == class="syntax-number">0) {
                $duplicate++;
                continue;
            }

            $g = $this->gcd($dx, $dy);
            $dx /= $g;
            $dy /= $g;

            $slope = $dy . class="syntax-string">'/' . $dx;
            if (!isset($slopes[$slope])) {
                $slopes[$slope] = class="syntax-number">0;
            }
            $slopes[$slope]++;
            $currentMax = max($currentMax, $slopes[$slope]);
        }

        $maxPoints = max($maxPoints, $currentMax + $duplicate + class="syntax-number">1);
    }

    return $maxPoints;
}

function gcd($a, $b) {
    if ($b == class="syntax-number">0) return $a;
    return $this->gcd($b, $a % $b);
}
}

$solution = new Solution();
echo $solution->maxPoints([[class="syntax-number">1,class="syntax-number">1],[class="syntax-number">2,class="syntax-number">2],[class="syntax-number">3,class="syntax-number">3]]);
echo $solution->maxPoints([[class="syntax-number">1,class="syntax-number">1],[class="syntax-number">3,class="syntax-number">2],[class="syntax-number">5,class="syntax-number">3],[class="syntax-number">4,class="syntax-number">1],[class="syntax-number">2,class="syntax-number">3],[class="syntax-number">1,class="syntax-number">4]]);