DSA · Geometry / Hash Map · #110
Max Points on a Line
Module 74 · difficulty 4/5·⏱ 30:00starts on first keystroke
Given an array `points` where `points[i] = [xi, yi]` represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Implement the function `maxPoints(points)` that returns this integer.
Examples
points = [[1,1],[2,2],[3,3]]→3— All three points are collinear on the line y = x.points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]→4— The line through (1,1), (3,2), (5,3) plus one more aligned point gives 4.points = [[0,0]]→1— A single point trivially lies on a line by itself.
Constraints
- · 1 <= points.length <= 300
- · points[i].length == 2
- · -10^4 <= xi, yi <= 10^4
- · All the points are unique.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.