Max Points on a Line
Problem Description
Question
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.
Example 1:
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Constraints:
- 1 <= points.length <= 300
- points[i].length == 2
- -104 <= xi, yi <= 104
- All the points are unique.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
This approach considers all combinations of pairs to determine every possible line. For each line, we check how many points from the input lie on it.
Steps:
- Iterate over each pair of points.
- For each pair, calculate the slope.
- Count how many points lie on the line defined by this slope.
- Keep track of the maximum count.
Code:
Complexity Analysis
- Time Complexity: O(N^3), where N is the number of points. This is due to the triply nested loops.
- Space Complexity: O(1), no extra space is used.
2. Optimized Approach Using HashMap
Intuition:
Instead of evaluating every pair by brute force, leverage the properties of the slope of lines and use a HashMap to optimize the counting of points on a similar slope from a given point.
Steps:
- Iterate over each point and treat it as the base point.
- Use a HashMap to store the slope of lines that include the base point.
- For each other point, calculate the simplified form of the slope and use it as the key in the HashMap.
- Determine the highest count of points that lie on any line based from the current base point.
- Keep track of the maximum count across all base points.
Code:
Complexity Analysis
- Time Complexity: O(N^2), because we iterate through each point and calculate the slope against every other point.
- Space Complexity: O(N), because we use a HashMap to store slopes information for each base point.