HomeOur TeamContact
Arrays
Line Through Points
Nisar
May 20, 2021
1 min

# .css-10kjd3a{box-sizing:border-box;margin:0;min-width:0;display:block;color:var(--theme-ui-colors-heading,#2d3748);font-weight:900;-webkit-text-decoration:none;text-decoration:none;margin-bottom:1rem;font-size:1.875rem;position:relative;}@media screen and (min-width:640px){.css-10kjd3a{font-size:2.25rem;}}@media screen and (min-width:1024px){.css-10kjd3a{font-size:3rem;}}Line Through Points

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`.

## Optimal Space & Time Complexity

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
```

## Tags

#Difficulty Very Hard#Algorithm
Previous Article
Longest Common Subsequence

## Related Posts

Inorder Tree Traversal with No Recursion
September 08, 2022
1 min