#149

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Max Points on a Line

Find the maximum number of points on a straight line in a 2D plane using array scanning and hash lookup.

Problem Statement

Given an array of points where each point is represented as [xi, yi], you need to return the maximum number of points that lie on the same straight line in a 2D plane. The solution requires you to evaluate the points and find the maximum number of collinear points, or those that lie along a single straight line.

For example, when given points like [[1,1],[2,2],[3,3]], the maximum number of points on a line is 3. You must efficiently process all points to find this maximum number of collinear points by considering line slopes and using hash tables for optimization.

Examples

Example 1

Input: points = [[1,1],[2,2],[3,3]]

Output: 3

Example details omitted.

Example 2

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Output: 4

Example details omitted.

Constraints

1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
All the points are unique.

Solution Approach

Array Scanning

Start by iterating through all points in the input array. For each point, compute the slope to every other point and track these slopes. This allows you to compare which slopes correspond to the maximum number of collinear points.

Hash Table Lookup

To efficiently count the number of points that share the same slope with a given point, use a hash table. Store each calculated slope as a key and the count of points with that slope as the value. This minimizes the time complexity of slope comparisons.

Handling Edge Cases

Handle vertical lines where the slope is undefined by using a special case in the hash table. Ensure that you consider all points and handle floating-point precision carefully when calculating slopes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the method used to process the points. In the worst case, the solution involves O(n^2) time complexity, where n is the number of points. Space complexity is also O(n) due to the storage of slope counts in a hash table for each point.

What Interviewers Usually Probe

Candidate shows a clear understanding of array scanning techniques.
Candidate can efficiently utilize hash tables for counting slopes.
Candidate identifies edge cases, such as vertical lines, and handles them properly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle vertical lines with an undefined slope.
Incorrectly handling floating-point precision when comparing slopes.
Not using a hash table, leading to a less efficient solution.

Follow-up variants

Consider optimizing the space complexity using different data structures for slope storage.
Alter the problem to include collinearity checks for points in higher dimensions.
Allow for duplicate points and adjust the solution to account for them.

FAQ

What is the main algorithm pattern in the Max Points on a Line problem?

The primary pattern for this problem involves array scanning combined with hash table lookup to efficiently count slopes between points.

How do you calculate the slope between two points?

The slope between two points [x1, y1] and [x2, y2] is calculated as (y2 - y1) / (x2 - x1), but you must handle vertical lines separately.

What are the edge cases to watch out for in this problem?

Be sure to handle vertical lines (undefined slope) and floating-point precision errors when calculating slopes.

What is the time complexity of the best solution for Max Points on a Line?

The best solution has a time complexity of O(n^2), where n is the number of points.

How can I improve the space complexity in this problem?

To reduce space complexity, consider using a more memory-efficient data structure for storing slopes, or explore optimization techniques.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 1
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                cnt = 2
                for k in range(j + 1, n):
                    x3, y3 = points[k]
                    a = (y2 - y1) * (x3 - x1)
                    b = (y3 - y1) * (x2 - x1)
                    cnt += a == b
                ans = max(ans, cnt)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 1
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                cnt = 2
                for k in range(j + 1, n):
                    x3, y3 = points[k]
                    a = (y2 - y1) * (x3 - x1)
                    b = (y3 - y1) * (x2 - x1)
                    cnt += a == b
                ans = max(ans, cnt)
        return ans

Continue Practicing

#391 perfect rectangle #939 minimum area rectangle #963 minimum area rectangle ii