You are given a set of points plotted on a 2D graph. Write code that returns the maximum number of points the line passes through.

The input array will contain points represented by an array of two integers which are a x-coordinate and a y-coordinate `[x, y]`

.

**Sample Input**

points = [ [1, 1], [2, 2], [3, 3], [0, 4], [-2, 6], [4, 0], [2, 1], ]

**Sample Output**

4 // A line passes through points: [-2, -6], [0, 4], [2, 2], [4, 0].

If two lines have the same slope and share a point, then they’re the same line. To store this information in a hash table, you will need to keep track of the slopes of all lines that pass through certain points.

Loop through every single pair of points, picking a `Point 2 (p2)`

for every `Point 1 (p1)`

in order to form a line. For every pair `(p1, p2)`

, Store the slope of a line segment in a hash table, and map it to the number of points on that line. If you ever find two identical slopes for lines that both use the same point `p1`

, you can consider these lines to be one and the same, meaning that points `p1, p2a, and p2b`

are all on the same line; in those cases, update the number of points on the slope in the hash table accordingly. You’ll need to reset the hash table at each change of `p1`

.

Time Complexity = `O(n^2)`

Space Complexity = `O(n)`

`n`

is the number of points

DEFINE FUNCTION lineThroughPoints(points): SET maxNumberOfPointsOnLine TO 1 FOR idx1, p1 IN enumerate(points): SET slopes TO {} FOR idx2 IN range(idx1 + 1, len(points)): SET p2 TO points[idx2] SET rise, run TO getSlopeOfLineBetweenPoints(p1, p2) SET slopeKey TO createHashableKeyForRational(rise, run) IF slopeKey not IN slopes: SET slopes[slopeKey] TO 1 slopes[slopeKey] += 1 SET maxNumberOfPointsOnLine TO max(maxNumberOfPointsOnLine, max(slopes.values(), default=0)) RETURN maxNumberOfPointsOnLine DEFINE FUNCTION getSlopeOfLineBetweenPoints(p1, p2): SET p1x, p1y TO p1 SET p2x, p2y TO p2 SET slope TO [1, 0] # slope of a vertical line IF p1x != p2x: # IF line is not vertical SET xDiff TO p1x - p2x SET yDiff TO p1y - p2y SET gcd TO getGreatestCommonDivisor(abs(xDiff), abs(yDiff)) SET xDiff TO xDiff // gcd SET yDiff TO yDiff // gcd IF xDiff < 0: xDiff *= -1 yDiff *= -1 SET slope TO [yDiff, xDiff] RETURN slope DEFINE FUNCTION createHashableKeyForRational(numerator, denominator): RETURN str(numerator) + ":" + str(denominator) DEFINE FUNCTION getGreatestCommonDivisor(num1, num2): SET a TO num1 SET b TO num2 WHILE True: IF a EQUALS 0: RETURN b IF b EQUALS 0: RETURN a SET a, b TO b, a % b

Previous Article

Longest Common SubsequenceNext Article

Levenshtein DistanceQuick Links

Legal Stuff