HARD Math & Geometry
149. Max Points on a Line
š Problem
Given an array of 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.
š§ Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- ā¢Array methods (`push`, `pop`, `shift`, `slice`)
- ā¢Object/Map/Set usage patterns
- ā¢Function parameter and return typing
Logical Thinking Concepts
- ā¢Define invariants before coding
- ā¢Check edge cases first (`[]`, single element, duplicates)
- ā¢Estimate time/space before implementation
š” Approach
- ā For each point, calculate slope with every other point
- ā Use hash map to count points with same slope
- ā Max points = max(slope_count + duplicates + 1) for each point
- ā Time: O(nĀ²), Space: O(nĀ²)
š§ Prerequisites
š ļø Hints & Pitfalls
Hints
- ā¢For each point, calculate slope with every other point
- ā¢Use hash map to count points with same slope
- ā¢Max points = max(slope_count + duplicates + 1) for each point
Common Pitfalls
- ā¢Time: O(nĀ²), Space: O(nĀ²)
š§Ŗ Test Cases
Test Case 1
Not run Input:
maxPoints(points: number[][]); Expected:
Computed from hidden reference Test Case 2
Not run Input:
maxPoints([[1,1],[2,2],[3,3]]); Expected:
Computed from hidden reference Test Case 3
Not run Input:
maxPoints([[1,1],[3,2],[4,1],[2,3],[1,4]]); Expected:
Computed from hidden reference š Code Editor
š¤ Output