Introduction

In this blog post, we will explore how to solve the LeetCode problem "149" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Iterate and Calculate Slopes: For each point, iterate through the remaining points and calculate the slope between them.

• Use a Dictionary to Count Slopes: Store the slopes in a dictionary (hash map). The keys will be the slopes, and the values will be the number of points that have that slope with the current point. Use greatest common divisor to simplify slope representation to avoid floating-point precision issues and treat vertical lines separately.

• Track Maximum Count: Keep track of the maximum number of points found on a line for each starting point. Update a global maximum as you iterate through all points.

• Runtime & Storage Complexity:

  • Runtime: O(n^2), where n is the number of points.
  • Storage: O(n), where n is the number of points (in the worst case, all slopes from a single point are unique).

Code

    from collections import defaultdict
import math

def max_points_on_a_line(points):
    """
    Finds the maximum number of points that lie on the same straight line.

    Args:
        points: A list of lists, where each inner list represents a point [x, y].

    Returns:
        The maximum number of points on a line.
    """

    n = len(points)
    if n <= 2:
        return n

    max_points = 0
    for i in range(n):
        slopes = defaultdict(int)
        same_points = 1  # Count of points identical to points[i]
        vertical = 0

        for j in range(i + 1, n):
            if points[i] == points[j]:
                same_points += 1
            elif points[i][0] == points[j][0]:
                vertical += 1
            else:
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                gcd = math.gcd(dx, dy)
                dx //= gcd
                dy //= gcd
                slopes[(dx, dy)] += 1

        max_slopes = 0
        if slopes:
            max_slopes = max(slopes.values())
        max_slopes = max(max_slopes, vertical)

        max_points = max(max_points, same_points + max_slopes)

    return max_points