Teaching Kids Programming: Videos on Data Structures and Algorithms
You are given a two-dimensional list of integers coordinates. Each list contains two integers [x, y] representing a point on the Cartesian plane. Return the maximum number of points that lie on some line.
Constraints
n ≤ 1,000 where n is the length of coordinates
Example 1
Input
1 2 3 4 5 6 7 8 9 coordinates = [ [5, 1], [7, 2], [9, 3], [0, 0], [1, 1], [5, 5], [6, 6] ]coordinates = [ [5, 1], [7, 2], [9, 3], [0, 0], [1, 1], [5, 5], [6, 6] ]Output
4
Explanation
The points [[0, 0], [1, 1], [5, 5], [6, 6]] all fall in a line.
Max Number of Points on a Line
We need to bruteforce all pairs of points, and count the pair who has the same slope. If delta x is zero, i.e. horizontal line, the slope is infinity. Line equations are and we can compute k as delta y divided by delta x.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: def maxPointsOnLine(self, cords): n = len(cords) if n < 3: return n ans = 0 for i in range(1, n): slopes = defaultdict(int) x1, y1 = cords[i] for j in range(i): x2, y2 = cords[j] s = (y2 - y1) / (x2 - x1) if x1 != x2 else math.inf slopes[s] += 1 ans = max(ans, max(slopes.values())) return ans + 1 |
class Solution: def maxPointsOnLine(self, cords): n = len(cords) if n < 3: return n ans = 0 for i in range(1, n): slopes = defaultdict(int) x1, y1 = cords[i] for j in range(i): x2, y2 = cords[j] s = (y2 - y1) / (x2 - x1) if x1 != x2 else math.inf slopes[s] += 1 ans = max(ans, max(slopes.values())) return ans + 1
The time complexity is O(N^2) where N is the number of coordinates. The space complexity is O(N) – as we are using a hash table to store the unique slopes.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The Java Method to Read Content of File into a String
Next Post: Input Password Function in Console Using Java